C语言数据结构学习：递归之斐波那契数列

2019-08-1409:18:53编程语言入门到精通Comments3,256 views字数 1297阅读模式

自己对递归还是不太熟练，于是做的时候就很吃力，就是翻棋子直到棋盘上所有棋子的颜色一样为止，求最少翻多少次，方法是枚举递归。然后就打算先做另一道递归的题（从数组中取出n个元素的组合），但是同样在递归的问题上不太理解。好吧，于是复习CPP，在第229页的时候，看到了斐波那契数列，回想起之前做过的一道题目，发现可以用递归的方法来做。于是决定优化一下之前的代码。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/15149.html

以下这段摘自《C primer plus》文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/15149.html

斐波那契数列的定义如下：第一个和第二个数字都是1，而后续的每个数字是其前两个数字之和，例如，数列中前几个数字是1，1，2，3，5，8和13。…下面我们创建一个函数，它接受一个正整数n作为参数，返回相应的斐波那契数值。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/15149.html

首先，关于递归深度，递归提供了一个简单的定义。如果调用Fibonacci(),当n为1或2时Fibonacci(n)应返回1；对于其他数值应返回Fibonacci(n-1)+Fibonacci(n-2);文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/15149.html

  1. long Fibonacci(n)
  2. {
  3. if (n > 2)
  4. return Fibonacci(n-1)+Fibonacci(n-2);
  5. else
  6. return 1;
  7. }

然后是兔子总数问题。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/15149.html

有一对兔子，从出生后第三个月起每个月都生一对兔子，小兔子长到第三个月后又生一对兔子，假如兔子都不死，每个月兔子对数为多少？文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/15149.html

思考这道题的时候，如果你简单的推算一下，会发现兔子每个月的对数就是斐波那契数列。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/15149.html

第一个月：1对；
第二个月：1对；
第三个月：2对；
第四个月：3对：
第五个月：5对：
第六个月：8对；
……文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/15149.html

我之前做这道题的时候，觉得思路很简单，就是从第三个月起，求每个月的兔子数时，只要把这个月的前两个月总数相加。
这是我之前的代码，用f1和f2表示月。：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/15149.html

  1. #include<stdio.h>
  2. int main()
  3. {
  4. int f1,f2;
  5. int month,ct;
  6. printf("请输入月份：");
  7. scanf("%d",&month);
  8. if(month<=2)
  9. printf("两只。\n");
  10. if (month > 2)
  11. {
  12. f1 = f2 = 1;
  13. ct = 0;
  14. while(ct < month -2){
  15. f1 = f1+f2;
  16. ct += 1;
  17. f2 = f1+f2;
  18. ct += 1;
  19. }
  20. if (month %2 == 0){
  21. printf("第 %d 个月的兔子对数为：%d.\n",month,f2);
  22. }
  23. if (month %2 == 1){
  24. printf("第 %d 个月的兔子对数为：%d.\n",f1);
  25. }
  26. }
  27. return 0;
  28. }

其实这个代码离递归就差一步，很接近了。但是我当时完全没有想到。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/15149.html

这是我重新修改之后的代码：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/15149.html

  1. #include<stdio.h>
  2. long Fibonacci(n)
  3. {
  4. if (n > 2)
  5. return Fibonacci(n-1)+Fibonacci(n-2);
  6. else
  7. return 1;
  8. }
  9. int main()
  10. {
  11. long num;
  12. int month;
  13. printf("请输入月份：");
  14. scanf("%d",&month);
  15. num = Fibonacci(month);
  16. printf("这个月的兔子对数为%d.\n",num);
  17. return 0;
  18. }

只是很简单的修改，但是代码就整洁易懂了很多，也学到了新内容。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/ymba/15149.html

  • 本站内容整理自互联网，仅提供信息存储空间服务，以方便学习之用。如对文章、图片、字体等版权有疑问，请在下方留言，管理员看到后，将第一时间进行处理。
  • 转载请务必保留本文链接：https://www.cainiaoxueyuan.com/ymba/15149.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定