玩蛇网提供最新Python编程技术信息以及Python资源下载!
您现在的位置: 玩蛇网首页 > 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]

玩蛇网文章,转载请注明出处和文章网址:http://www.iplaypy.com/code/algorithm/a1892.html

相关文章 Recommend

玩蛇网Python互助QQ群,欢迎加入-->: 106381465 玩蛇网Python新手群
修订日期:2017年01月10日 - 09时51分03秒 发布自玩蛇网

我要分享到:
尚未注册畅言帐号,请到后台注册

必知PYTHON教程 Must Know PYTHON Tutorials

必知PYTHON模块 Must Know PYTHON Modules