python小练习（022）：count-and-say

jerryxjr1220

python小练习（021），传送门

再来看一个有趣的题目：count-and-say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

稍稍解释一下字符串的生成规律：字符串从“1”开始，第i+1个字符串是第i个字符串数字形式的读法。

求这个序列的第30项是什么？

冬雪雪冬

我怎么得到这么长的值，算错了吗？

3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321223112111311222112132113213221133122211311221122111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112112322211322311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113121113122122311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312211322311211133112111312211213211311123113223112111321322123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111312211322311211133112111312212221121123222112132113213221133112132123222113223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211

SixPy

import re
def fn(n=30):
    s = ['1']
    ptn=re.compile(r'((\d)\2*)')
    for x in range(n+1):
        ls=ptn.findall(s[-1])
        s.append(''.join((str(len(a))+b for a,b in ls)))
    return ','.join(s[:5]),s[-1]

a,b = fn()
print(a,'\n',b)

jerryxjr1220

SixPy 发表于 2016-11-26 00:41

应该是对的吧，用了正则匹配，比我的解法好！

jerryxjr1220

我的解答：

# -*- coding: utf-8 -*-

a = ['1','11','21','1211','111221']
for i in range(30):
    s, e, next = 0, 1, ''
    for j in range(len(a[-1])):
        if j != len(a[-1])-1:
            if a[-1][j] != a[-1][j+1]:
                next += str(e-s)+a[-1][j]
                s, e = j, j+1
            else:
                e += 1
        else:
            if a[-1][j] != a[-1][j-1]:
                next += '1'+a[-1][j]
            else:
                next += str(e-s)+a[-1][j]
    a.append(next)
print (a[30])

jerryxjr1220

冬雪雪冬 发表于 2016-11-25 23:31
我怎么得到这么长的值，算错了吗？

是我题目写得不好，写出第30项的长度就可以了，不然看得眼花

余欲渔

def lianjie(zhi):
    if zhi==['1']:return ('11')
    weishu=1
    strr=''
    shouwei=zhi[0]
    zhi=zhi[1:]
    while zhi!=[]:
        if zhi[0]==shouwei:
            weishu+=1
        else:
            strr+=str(weishu)
            strr+=shouwei
            weishu=1
            shouwei=zhi[0]
        zhi=zhi[1:]
    strr+=str(weishu)
    strr+=shouwei
    return(strr)
x='1'
for i in range(29):
    x=lianjie(list(x))
print(len(x))

 RESTART: C:/Users/ASUS/AppData/Local/Programs/Python/Python35-32/count-and-say.py 
4462
>>> 

1141429506

#递归算法1
def f(c):
    a = []
    j = 0
    for i in range(len(c)):
        j += 1
        if i == len(c) - 1:
            a.append(j)
            a.append(c[i])
            break
        if c[i+1] != c[i]:
            a.append(j)
            a.append(c[i])
            j = 0
    return a

c = [1,]
for i in range(5):
    c = f(c)
    print(c)

1141429506

#递归算法２
def out(n):
    if n == 1:
        return ['1']
    else:
        i = 0
        j = 1
        k = []
        str1 = out(n-1)
        while i < len(str1):
            while i < len(str1)-1:
                if str1[i] == str1[i+1]:
                    j += 1
                    i += 1
                else:
                    break
            k.append(str(j))
            k.append(str(str1[i]))
            j = 1
            i += 1
        return k

   
while 1:
    n = int(input('please input an number(end of 0):'))
    if n == 0:
        print('End,Thanks--')
        break
    print('out(%d) = %s'%(n,repr("".join(out(n)))))

小贤啊哦