第十关是一张牛的图片和一行字:len(a[30])=?。图片中的牛是一个链接,点开后进入一个新页面,只有一行字:

a = [1, 11, 21, 1211, 111221,

看来要知道第31个数多长,首先得算出第31个数是多少。

我开始以为只是简单的找规律,各种方法试了个遍,怎么都算不出来,无奈只好搜索之,一搜搜到一个维基百科:Look-and-say sequence。看完才明白自己完全走错了路。

这个数列的规律是,后一个数用来描述前一个数,比如第一个数是1,第二个数描述1就是1个1,也就是11,第三个数描述11就是2个1也就是21,第四个数描述21就是1个2和1个1也就是1211,以此类推。

维基百科页面给了一段 Python 代码,用来生成这个数列:

def look_and_say(member):
while True:
yield member
breakpoints = ([0] + [i for i in range(1, len(member)) if member[i - 1] != member[i]] + [len(member)])
groups = [member[breakpoints[i - 1]:breakpoints[i]] for i in range(1, len(breakpoints))]
member = ''.join(str(len(group)) + group[0] for group in groups) # Print the 10-element sequence beginning with "1"
sequence = look_and_say("")
for i in range(10):
print sequence.next()

这段代码是把数列中的每个数当做一个字符串来求解。首先求的不相同数字间的起始位置的一个列表:

breakpoints = ([0] + [i for i in range(1, len(member)) if member[i - 1] != member[i]] + [len(member)])

这里,列表的第一个数为0,也就是起始位置。后面存储的断点为相邻两个数不相等的位置。最后加上一个前一个数的长度。比如输入的数为 ‘1211’,得到的 breakpoints 就是 [0, 1, 2, 4]。第一个数为0,第二个数为2和1不相等的位置也就是1,第三个数为1和2不相等的位置就是2,后面两个1相等,就直接加上数字的长度4。

求得断点后,根据断点,把前一个数字分为不同部分组成的列表:

groups = [member[breakpoints[i - 1]:breakpoints[i]] for i in range(1, len(breakpoints))]

仍然以 ‘1211’ 作为输入例子,这里 i 是 [1, 2, 3],i=1时,列表的第一项为 member[0:1] = '1',i=2时,列表第二项为 member[1:2] = '2',i=3时,列表第三项为 member[2:4] = '11'。也就是说,groups 为 ['1', '2', '11']。

最后一步,根据 groups,算出下一个数:

member = ''.join(str(len(group)) + group[0] for group in groups)

join()方法的参数中是一个列表解析,对 groups 中的每一项,算出长度,并转换为字符串,然后加上每一项的第一个字符也就是这个数组成一组,然后把整个列表 join 成一个字符串,得到下一个数。对于上一步得出的 groups = ['1', '2', '11'],列表解析 [str(len(group)) + group[0] for group in groups] 得出的结果为:['11', '12', '21'],连接起来就是 ‘111221’,也就是下一个数。

这个代码使用生成器写的,输入是数列中的一个数,可以稍微修改一下,输入为数列的索引,输出为该位置的数:

def look_and_say(index):
if index == 0:
return ''
member = ''
for i in xrange(index):
breakpoints = ([0] + [i for i in range(1, len(member)) if member[i - 1] != member[i]] + [len(member)])
groups = [member[breakpoints[i - 1]:breakpoints[i]] for i in range(1, len(breakpoints))]
member = ''.join(str(len(group)) + group[0] for group in groups)
return member

这样我们直接输入 print len(look_and_say(30)) 就可以得到答案:5808,修改 url,就可以进入下一关:http://www.pythonchallenge.com/pc/return/5808.html

05-11 22:34