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项是什么？

冬雪雪冬

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

1. 3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321223112111311222112132113213221133122211311221122111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112112322211322311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113121113122122311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312211322311211133112111312211213211311123113223112111321322123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111312211322311211133112111312212221121123222112132113213221133112132123222113223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211

复制代码

SixPy

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

复制代码

jerryxjr1220

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

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

jerryxjr1220

我的解答：

1. # -*- coding: utf-8 -*-
   
2. 
   
3. a = ['1','11','21','1211','111221']
   
4. for i in range(30):
   
5.     s, e, next = 0, 1, ''
   
6.     for j in range(len(a[-1])):
   
7.         if j != len(a[-1])-1:
   
8.             if a[-1][j] != a[-1][j+1]:
   
9.                 next += str(e-s)+a[-1][j]
   
10.                 s, e = j, j+1
    
11.             else:
    
12.                 e += 1
    
13.         else:
    
14.             if a[-1][j] != a[-1][j-1]:
    
15.                 next += '1'+a[-1][j]
    
16.             else:
    
17.                 next += str(e-s)+a[-1][j]
    
18.     a.append(next)
    
19. print (a[30])

复制代码

jerryxjr1220

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

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

余欲渔

1. def lianjie(zhi):
   
2.     if zhi==['1']:return ('11')
   
3.     weishu=1
   
4.     strr=''
   
5.     shouwei=zhi[0]
   
6.     zhi=zhi[1:]
   
7.     while zhi!=[]:
   
8.         if zhi[0]==shouwei:
   
9.             weishu+=1
   
10.         else:
    
11.             strr+=str(weishu)
    
12.             strr+=shouwei
    
13.             weishu=1
    
14.             shouwei=zhi[0]
    
15.         zhi=zhi[1:]
    
16.     strr+=str(weishu)
    
17.     strr+=shouwei
    
18.     return(strr)
    
19. x='1'
    
20. for i in range(29):
    
21.     x=lianjie(list(x))
    
22. print(len(x))

复制代码

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

复制代码

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)))))

小贤啊哦