算法-斐波那契数列 「爱情、让人受尽委屈。」 2022-06-10 13:07 174阅读 0赞 **题目:** 写一个函数,输入为n,求斐波那契(Fibonacci)数列的第n项。斐波那契数列定义如下: ![这里写图片描述][SouthEast] **解题思路:** 斐波那契问题是个非常经典的递归问题,比如我们想要求得f(8),f(8)=f(7)+f(6),而f(7)=f(6)+f(5),……,直到n=1或n=0时递归结束,那么我们很容易就编出来下面的代码: #include "iostream" using namespace std; long long Fibonacci(unsigned int n) { if(n <= 0) return 0; if(n == 1) return 1; return Fibonacci(n - 1) + Fibonacci(n - 2); } int main() { int sum = Fibonacci(8); cout<<sum<<endl; getchar(); return 0; } 但是递归真的适合这个问题吗?我们可以分析下上面的代码,n=8时,需要求f(7)和f(6),而求f(7)时需要求f(6)和(5),所以这就造成了相求f(8),但是递归的深度却远远不止8层,在执行`return Fibonacci(n - 1) + Fibonacci(n - 2);`代码时,递归总是先进入左边的函数,当左边函数满足退出条件时(n=1),递归才会逐层退出,退出一层后又进入右边的函数,这其中产生了大量的冗余计算,所以在n=8时,递归的层数是32层,这个效率其实是很低的。 所以我们需要考虑如何用循环完成这个任务,我们只需要在每次进入循环并执行相加操作后,保存相加的结果作为下次使用,循环有一个优势在于,n与循环的次数是相等的。 **代码实现:** #include "iostream" using namespace std; long long Fibonacci(unsigned int n) { int result[2] = { 0, 1}; if(n < 2) return result[n]; long long fibNMinusOne = 1; long long fibNMinusTwo = 0; long long fibN = 0; for(unsigned int i = 2; i <= n; ++ i) { fibN = fibNMinusOne + fibNMinusTwo; fibNMinusTwo = fibNMinusOne; fibNMinusOne = fibN; } return fibN; } int main() { long long sum = Fibonacci(8); cout<<sum<<endl; getchar(); return 0; } 我们可以对代码效率做个测试,为了让效果明显,令n=40: #include "iostream" #include <time.h> using namespace std; // ====================方法1:递归==================== long long Fibonacci_Solution1(unsigned int n) { if(n <= 0) return 0; if(n == 1) return 1; return Fibonacci_Solution1(n - 1) + Fibonacci_Solution1(n - 2); } // ====================方法2:循环==================== long long Fibonacci_Solution2(unsigned n) { int result[2] = { 0, 1}; if(n < 2) return result[n]; long long fibNMinusOne = 1; long long fibNMinusTwo = 0; long long fibN = 0; for(unsigned int i = 2; i <= n; ++ i) { fibN = fibNMinusOne + fibNMinusTwo; fibNMinusTwo = fibNMinusOne; fibNMinusOne = fibN; } return fibN; } int main() { clock_t start1,finish1,start2,finish2; double totaltime1,totaltime2; start1=clock(); long long sum1 = Fibonacci_Solution1(40); finish1=clock(); totaltime1=(double)(finish1-start1)/CLOCKS_PER_SEC; cout<<"结果:"<<sum1<<endl<<"时间:"<<totaltime1<<endl; start2=clock(); long long sum2 = Fibonacci_Solution2(40); finish2=clock(); totaltime2=(double)(finish2-start2)/CLOCKS_PER_SEC; cout<<"结果:"<<sum2<<endl<<"时间:"<<totaltime2<<endl; getchar(); return 0; } 结果:102334155 时间:5.06 结果:102334155 时间:0 最后,关于斐波那契数列有很多应用问题,比如: **题目1:** 用2\*1的小矩形横着放或竖着放去覆盖右侧的2\*8的区域,要求用8个小矩形,无重叠的覆盖,那么总共有多少种方法? ![这里写图片描述][SouthEast 1] f(7)问题: ![这里写图片描述][SouthEast 2] f(6)问题: ![这里写图片描述][SouthEast 3] 而f(1)=f(2)=1 **题目2:** 一只青蛙一次可以跳1级或2级台阶,求跳上n级台阶有几种方法? **题目3:** 滴滴的一道智力题:有8层台阶,开始在第0层,每次可以爬一层或者两层,请问爬到8层一共有( )种方法? [SouthEast]: /images/20220610/3a61d731767d4a4397436a962811ff95.png [SouthEast 1]: /images/20220610/f72e3ac103a44fc78b49e48bf5fa986f.png [SouthEast 2]: /images/20220610/d37def1e0fe148868a9f350ad579be82.png [SouthEast 3]: /images/20220610/afe569d9f16642a18d8262d80bd9a0b2.png
相关 算法 | 斐波那契数列 系列文章目录 -------------------- 文章目录 系列文章目录 前言 具体实现 循环法 柔情只为你懂/ 2022年12月10日 08:42/ 0 赞/ 128 阅读
相关 斐波那契数列 关于斐波那契数列的解法,本人找到了一种比较简单的方法,结果是正确的,不知道各位有没有另外更好的解法,一起探讨探讨。 import java.util.; pu ╰+攻爆jí腚メ/ 2022年08月01日 12:15/ 0 赞/ 247 阅读
相关 斐波那契数列 定义:斐波那契数列指的是这样一个数列:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … 这个数列从第三项开始,每一项都等于前两项之和。 矫情吗;*/ 2022年07月13日 04:49/ 0 赞/ 209 阅读
相关 斐波那契数列 斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597, 冷不防/ 2022年07月13日 03:19/ 0 赞/ 233 阅读
相关 算法-斐波那契数列 题目: 写一个函数,输入为n,求斐波那契(Fibonacci)数列的第n项。斐波那契数列定义如下: ![这里写图片描述][SouthEast] 解题思路: 斐波那 「爱情、让人受尽委屈。」/ 2022年06月10日 13:07/ 0 赞/ 175 阅读
相关 斐波那契数列 class FibIter(object): def __init__(self, lenth): self.lent 一时失言乱红尘/ 2022年05月27日 13:51/ 0 赞/ 240 阅读
相关 斐波那契数列 include<iostream> using namespace std; int fibonacci1(int t) { if(t 古城微笑少年丶/ 2022年05月09日 08:58/ 0 赞/ 207 阅读
相关 斐波那契数列 > 斐波那契数列(Fibonacci sequence)指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递推的方法定义:F(1 墨蓝/ 2022年03月22日 15:59/ 0 赞/ 309 阅读
相关 斐波那契数列 时间限制:1秒 空间限制:32768K 热度指数:450138 算法知识视频讲解 题目描述 大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第 淡淡的烟草味﹌/ 2022年03月12日 08:13/ 0 赞/ 235 阅读
相关 斐波那契数列 package nums; public class Feibonaqi { public static void main(St 野性酷女/ 2022年03月07日 06:10/ 0 赞/ 271 阅读
还没有评论,来说两句吧...