python du熊学斐波那契实现，python熊学,python du熊学斐

python du熊学斐波那契实现，python熊学,python du熊学斐

python du熊学斐波那契实现du熊对数学一直都非常感兴趣。最近在学习斐波那契数列的它，向你展示了一个数字串，它称之为“斐波那契”串：
11235813471123581347112358........

聪明的你当然一眼就看出了这个串是这么构造的：
1.先写下两位在0~9范围内的数字a, b，构成串ab；
2.取串最后的两位数字相加，将和写在串的最后面。
上面du熊向你展示的串就是取a = b = 1构造出来的串。
显然，步骤1之后不停地进行步骤2，数字串可以无限扩展。现在，du熊希望知道串的第n位是什么数字。
Input
输入数据的第一行为一个整数T（1 <= T <= 1000）, 表示有T组测试数据；
每组测试数据为三个正整数a, b, n（0 <= a, b < 10, 0 < n <= 10^9）。

Output
对于每组测试数据，输出一行“Case #c: ans”（不包含引号）
c是测试数据的组数，从1开始。
Sample Input
3

1 1 2
1 1 8
1 4 8
Sample Output
Case #1: 1
Case #2: 3
Case #3: 9
Hint
对于第一、二组数据，串为112358134711235......
对于第三组数据，串为14591459145914......

1.[代码][Python]较简洁

def f1(a,b,n):    intDigits=lambda n: map(int, str(n))    return reduce(lambda x,y: x+intDigits(sum(x[-2:])), range(n-2), [a,b])[n-1]test=[[1,1,2],[1,1,8],[1,4,8]]print [f1(*i) for i in test]

2.[代码][Python] 较高效

partition=lambda L: [L[i:i+2] for i in range(len(L)-1)]intDigits=lambda n: map(int, str(n))def f2(a,b,n):    r=[a,b]    while r[-2:] not in partition(r[:-2]):        r=r+intDigits(r[-2]+r[-1])    pos= partition(r).index(r[-2:])    return r[n-1 if n<pos else (n-1-pos)%(len(r)-pos-2) + pos]test=[[1,1,2],[1,1,8],[1,4,8],[2,4,100],[1,5,10**8-1],[1,7,10**8]]print [f2(*i) for i in test]

编橙之家文章，