找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

【算法漫画】斐波那契的兔子问题

admin 2019-12-15 13:02 306人围观 C++相关











题目的意思是在最初给一对幼年兔子,幼年兔子需要一个月长成成年兔子,此后每一个月都会产下一对幼年兔子。

我们考虑设立函数R(x)表示x个月后,兔子的对数,首先我们按照题目给出的兔子在两个月后开始产生一对幼年兔子,所以在x个月新出生的兔子的对数是R(x-2),因为第x个月兔子数的构成是由之前就有的兔子数目加上这个月新生产出兔子数目,而这其中的之前就存在的兔子对数可以直接使用R(x-1)来表示,所以我们发现了转移式R(x)=R(x-1)+R(x-2)。

这个时候我们发现这样的式子是可以用递归计算的,但是当我们尝试用递归实现的时候会明显感觉到代码的运行效率很低,虽然是可以解决12个月后兔子的对数,但如果查询的是10年后数目,这样的代码就满足不了需求了。

我们考虑怎么对这个代码进行优化,第一种思路是我们发现转移式中的x只受到比x小的月份影响,我们可以直接用一个循环递推答案,第二种思路是可以使用记忆化搜索优化之前的递归,在递归的时候如果R(x)还没有被存储上值的情况下就向下递归,然后将返回的值存在R(x)中,反之如果R(x)已经被存上值了,就直接使用它即可。这道题是斐波那契数列的经典题之一,有兴趣的同学也可以自行学习一下与其相关的楼梯问题等其他问题。

解析作者:Johnson_Wu





▼往期精彩回顾▼【算法漫画】谜题毒酒【算法漫画】夜过吊桥【算法漫画】超级蛋测试【算法漫画】击落战舰【算法漫画】科学家在世的最好时代
版权声明:本篇漫画版权归校苑数模公众号所有,任何形式的转载及内容使用需与校苑数模工作人员模小数联系,未经授权的转载与使用我们将对其追究法律责任。合作与转载请在公众号会话窗口回复【合作】或【转载】。感谢您的支持与认可。


看都看完了,还不点这里试试


----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:校苑数模,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......