算。那很容易想到如果我们把计算的结果全都保存下来,按照一定的顺序推出n项,就可以提升效率
解法2:
def f1(n): if n==1 or n==2: return 1 l=[0]*n #保存结果 l[0],l[1]=1,1 #赋初值 for i in range(2,n): l[i]=l[i-1]+l[i-2] #直接利用之前结果 return l[-1] 可以看出,时间o(n),空间o(n)。
继续思考,既然只求第n项,而斐波那契又严格依赖前两项,那我们何必记录那么多值浪费空间呢?只记录前两项就可以了。
解法3:
def f2(n): a,b=1,1 for i in range(n-1): a,b=b,a+b return a 补充:
pat、蓝桥杯等比赛原题:求的n很大,F(N)模一个数。应每个结果都对这个数取模,否则:第一,计算量巨大,浪费时间;第二,数据太大,爆内存, 对于有多组输入并且所求结果类似的题,可以先求出所有结果存起来,然后直接接受每一个元素,在表中查找相应答案 此题有快速幂算法,但是碍于篇幅和同学们水平有限,不再叙述,可以自行学习。
例2:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
依旧是找递推关系:
1)跳一阶,就一种方法
2)跳两阶,它可以一次跳两个,也可以一个一个跳,所以有两种
3)三个及三个以上,假设为n阶,青蛙可以是跳一阶来到这里,或者跳两阶来到这里,只有这两种方法。
它跳一阶来到这里,说明它上一次跳到n-1阶,
同理,它也可以从n-2跳过来 ———————————————— 版权声明:本文为CSDN博主「一只大白兔兔兔兔兔」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。 原文链接:https://blog.csdn.net/hebtu666/article/details/100585136
|