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

时间:2021-05-20

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

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

以下这段摘自《C primer plus》

斐波那契数列的定义如下:第一个和第二个数字都是1,而后续的每个数字是其前两个数字之和,例如,数列中前几个数字是1,1,2,3,5,8和13。…下面我们创建一个函数,它接受一个正整数n作为参数,返回相应的斐波那契数值。

首先,关于递归深度,递归提供了一个简单的定义。如果调用Fibonacci(),当n为1或2时Fibonacci(n)应返回1;对于其他数值应返回Fibonacci(n-1)+Fibonacci(n-2);

long Fibonacci(n){ if (n > 2) return Fibonacci(n-1)+Fibonacci(n-2); else return 1;}

然后是兔子总数问题。

有一对兔子,从出生后第三个月起每个月都生一对兔子,小兔子长到第三个月后又生一对兔子,假如兔子都不死,每个月兔子对数为多少?

思考这道题的时候,如果你简单的推算一下,会发现兔子每个月的对数就是斐波那契数列。

第一个月:1对;
第二个月:1对;
第三个月:2对;
第四个月:3对:
第五个月:5对:
第六个月:8对;
……

我之前做这道题的时候,觉得思路很简单,就是从第三个月起,求每个月的兔子数时,只要把这个月的前两个月总数相加。
这是我之前的代码,用f1和f2表示月。:

#include<stdio.h>int main(){ int f1,f2; int month,ct; printf("请输入月份:"); scanf("%d",&month); if(month<=2) printf("两只。\n"); if (month > 2) { f1 = f2 = 1; ct = 0; while(ct < month -2){ f1 = f1+f2; ct += 1; f2 = f1+f2; ct += 1; } if (month %2 == 0){ printf("第 %d 个月的兔子对数为:%d.\n",month,f2); } if (month %2 == 1){ printf("第 %d 个月的兔子对数为:%d.\n",month,f1); } } return 0;}

其实这个代码离递归就差一步,很接近了。但是我当时完全没有想到。

这是我重新修改之后的代码:

#include<stdio.h>long Fibonacci(n){ if (n > 2) return Fibonacci(n-1)+Fibonacci(n-2); else return 1;}int main(){ long num; int month; printf("请输入月份:"); scanf("%d",&month); num = Fibonacci(month); printf("这个月的兔子对数为%d.\n",num); return 0;}

只是很简单的修改,但是代码就整洁易懂了很多,也学到了新内容。

工欲善其事必先利其器,共勉。

如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章