C语言数据结构递归之斐波那契数列
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; }
只是很简单的修改,但是代码就整洁易懂了很多,也学到了新内容。
工欲善其事必先利其器,共勉。
如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
相关文章
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
- 这篇文章主要介绍了C#数据结构之队列(Quene),结合实例形式较为详细的讲述了队列的功能、原理与C#实现队列的相关技巧,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了C#实现斐波那契数列的几种方法整理,主要介绍了递归,循环,公式和矩阵法等,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25
- 在本篇内容里小编给大家分享了关于C++实现递归函数的教学步骤,需要的朋友跟着参考下。...2020-04-25
- 这篇文章主要介绍了C++递归删除一个目录的实现方法,涉及到目录的操作及递归算法的应用,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C#常用数据结构和算法,这里我们总结了一些知识点,可以帮助大家理解这些概念。...2020-06-25
- 斐波那契数列来源于兔子繁殖问题,所以也叫兔子序列,下面这篇文章主要给大家介绍了关于JavaScript输出斐波那契数列的实现方法,需要的朋友可以参考下...2021-06-27
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 以下是对C++中输出斐波那契数列的两种实现方法进行了详细的介绍,需要的朋友可以过来参考下,希望对大家有所帮助...2020-04-25
- 本文主要和大家分享几种Redis数据结构详解,希望文中的案例和代码,能帮助到大家。...2021-01-15
- 这篇文章主要介绍了C#递归实现显示文件夹及所有文件并计算其大小的方法,是遍历算法中比较典型的一种应用,有不错的学习借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要为大家详细的介绍了Redis高效的原因以及分析了Redis高效的数据结构,有需要的朋友可以借鉴参考下,希望能够有所帮助...2021-09-27
- 这篇文章主要介绍了C$ 笔试题之同线程Lock语句递归不会死锁,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 上文对数据结构与算法,有了一个简单的概述与介绍,这篇文章,我们介绍一中典型数据结构——线性结构...2020-06-25
- 这篇文章主要介绍了python 非递归解决n皇后问题的方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-16
- 这篇文章主要介绍了C语言数据结构递归之斐波那契数列的相关资料,希望通过本文能帮助到大家,让大家理解掌握这部分内容,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了Java中的什么场景使用递归,如何使用递归的操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-09-03
- 这篇文章主要介绍了使用递归实现数组求和示例,思路是给定一个含有n个元素的整型数组a,求a中所有元素的和,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了C++数据结构与算法之哈夫曼树的实现方法,简单说明了哈夫曼树的原理,并结合具体实例形式分析了C++实现哈夫曼树的相关操作技巧,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了使用dom4j递归解析节点内还含有多个节点的xml,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-09-25