神奇兔子数列

左手的ㄟ右手 2023-09-26 15:31 16阅读 0赞

[14天阅读挑战赛][14]  
*努力是为了不平庸~  
算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！欢迎记录下你的那些努力时刻（算法学习知识点/算法题解/遇到的算法bug/等等），在分享的同时加深对于算法的理解，同时吸收他人的奇思妙想，一起见证技术er的成长~*

**算法题目描述**

> 假设第1个月有1对刚诞生的兔子，第2个月进入成熟期，第3个月开始生育兔子，而1对成熟的兔子每月会生1对兔子，兔子永不死去……那么，由1对初生兔子开始，12个月后会有多少对兔子呢？
> 
> 兔子数列即斐波那契数列，它的发明者是意大利数学家列昂纳多•斐波那契（Leonardo Fibonacci，1170—1250）。1202年，他撰写了《算盘全书》（《Liber Abaci》）一书，该书是一部较全面的初等数学著作。书中系统地介绍了印度—阿拉伯数码及其演算法则，介绍了中国的“盈不足术”；引入了负数，并研究了一些简单的一次同余式组。
> 
> ![18d0b448c0a7cff979594862e868a352.jpeg][]

### 做题思路 ###

> 这个数列有十分明显的特点，从第3个月开始，**当月的兔子数**=**上月兔子数**\+**当月新生兔子数**，而当月新生的兔子正好是**上上月的兔子数**。因此，前面相邻两项之和，构成了后一项，即：
> 
> **当月的兔子数**=**上月兔子数**\+**上上月的兔子数**
> 
> 斐波那契数列如下：
> 
> 1，1，2，3，5，8，13，21，34，…
> 
> 递归式表达式：
> 
> ![c7ae285da418b5df7e1da3e44d0a5583.png][]
> 
> 那么我们该怎么设计算法呢？
> 
> > 哈哈，这太简单了，用递归算法很快就算出来了！

### 模板代码 ###

>     Fun(int n){  
>         if(n<1)   
>             return -1;
>         else if(n==1||n==2)   
>             return 1;
>         else return Fun1(n-1)+Fib1(n-2);
>     }

### 做题过程中遇到的bug及解决方案 ###

> 太耗时了
> 
> 不能用递归

### 相关算法题型题目总结 ###

> 可以用数组，然后for循环搞定

### 读书笔记 ###

> 做出来不是关键，关键是如何优化，才是算法的意义

###  ###

[14]: https://marketing.csdn.net/p/bb9f9e25975dba9f9b87f5272afded16
[18d0b448c0a7cff979594862e868a352.jpeg]: https://img-blog.csdnimg.cn/img_convert/18d0b448c0a7cff979594862e868a352.jpeg
[c7ae285da418b5df7e1da3e44d0a5583.png]: https://img-blog.csdnimg.cn/img_convert/c7ae285da418b5df7e1da3e44d0a5583.png