玩蛇网提供最新Python编程技术信息以及Python资源下载!
python零基础培训

python du熊学斐波那契实现

python 培训
 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]

站长推荐阅读相关内容:
linux基础入门教程

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



微信扫描下图可直接关注Python公众号

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

我要分享到:
评论列表(网友评论仅供网友表达个人看法,并不表明本站同意其观点或证实其描述)
相关文章推荐
别人正在看
特别推荐
站长推荐:
去顶部去底部