斐波那契数列
标签: 机试攻略 - 高分篇
学习人数: 17.4k


高清播放
赞赏支持

定义

斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368........
这个数列从第3项开始,每一项都等于前两项之和。

 

公式

F(n) = F(n-1) + F(n-2)

 

斐波那契一般不会作为一个直接考点出现,都会结合一些规律让你去推导,然后发现题目的规律原来是一个斐波那契数列。

在本章最后一个小节中,用了一个斐波那契的题目作为例子。


我们需要注意的考点是

1、这个数列的上升速度非常快,很容易超过int和long long的范围

2、如果对答案取模,题目就可能要求我们计算第10000000项的值,我们就可以直接使用公式求解,后面的章节也会讲到用矩阵快速幂求解的方法。

3、如果给你一个数列:a(1) = 1, a(n+1) = 1 + 1/a(n)。
那么它的通项公式为:a(n) = fib(n+1) / fib(n)。

 

登录查看完整内容


课后作业

了解斐波那契数列


登录后开始许愿

暂无评论,来抢沙发