算法-斐波那契数列 - 兔子繁殖问题 2024-03-10 默认分类 暂无评论 271 次阅读 > 故事得从西元1202年说起，话说有一位意大利青年，名叫斐波那契。在他的一部著作中提出了一个有趣的问题：假设一对刚出生的小兔一个月后就能长成大兔，再过一个月就能生下一对小兔，并且此后每个月都生一对小兔，一年内没有发生死亡，问：一对刚出生的兔子，一年内繁殖成多少对兔子? 好了，虽说问题很有趣儿，但是貌似不是很容易解答哈，那我们还是先看看斐波那契是何许人也。  <h3><a class="cl-offset" name="cl-1"></a>人物介绍[1-2] </h3> > 斐波那契，又称比萨的列奥纳多（英语：Leonardo Pisano Bigollo，或称Leonardo of Pisa, Leonardo Pisano, Leonardo Bonacci, Leonardo Fibonacci，1175年－1250年[1]），出生于意大利的比萨，意大利数学家，西方第一个研究斐波那契数，并将现代书写数和乘数的位值表示法系统引入欧洲。 一般认为斐波那契数列的提出是基于兔子的繁殖问题：如果一开始有一对兔子，它们每月生育一对兔子，小兔在出生后一个月又开始生育且繁殖情况与最初的那对兔子一样，那么一年后有多少对兔子？ 答案是，每月兔子的总数可以用以下数列表示：1，1，2，3，5，8，13，21，34，55，89，144，233…。 这一数列是意大利数论家列奥纳多·斐波那契（Leonardo Fibonacci）在他13世纪初的著作Liber Abaci中最早提出的。如果取数列前两个元素为1，那么递推关系就是： ```math F_n = F_{n-1}+F_{n-2} ``` 当然，曾经有一度数学家们将0作为斐波那契数列的首项（或第0项）。 <h3><a class="cl-offset" name="cl-2"></a>递归法 </h3> ```Go func fib(n int) { if (n==1 || n==2) { return 1 } return fib(n-1)+fib(n-2) } ``` <h3><a class="cl-offset" name="cl-3"></a>迭代法 </h3> ```Go func fib(n int) int { p, q, r := 0, 0, 1 for i := 1; i <= n; i++ { p = q q = r r = p + q } return r } ``` 文章目录 人物介绍[1-2] 递归法 迭代法 标签: 算法 转载请注明文章来源 本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
评论已关闭