斐波那契问题（兔子问题）

大家好，我是讯享网，很高兴认识大家。

14天阅读挑战赛在这里插入图片描述
讯享网14天阅读挑战赛
努力是为了不平庸~

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。

学习日记

一、斐波那契数列的概念

二、斐波那契的复现

1、递归实现

2、迭代实现

3、总结

三、兔子问题

一、斐波那契数列的概念

        斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。

斐波那契数列指的是这样一个数列：

0，1，1，2，3，5，8，13，21，34，55，89，144，233，377，610，987，1597，2584，4181，6765，10946，17711……

它的规律是：这个数列从第 3 项开始，每一项都等于前两项之和。

在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*），显然，斐波那契数列是一个线性递推数列。



        我们给出斐波那契数列的推导公式：

二、斐波那契的复现

常用的实现斐波那契数列的方法分为两大类：递归和循环。

1、递归实现

#C语言版本

#include <stdio.h> int F(int n) //斐波那契数列函数 递归形式 { if(n == 0) //初始化 return 0; if(n == 1 || n == 2) return 1; return F(n-1) + F(n-2); //如果n != 1 && n != 2 进行递归运算 } int main() { int t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); printf("%d\n", F(n)); } return 0; }

讯享网

#python版本

讯享网import time def Fibonacci(i): if i==0: return 0 elif i==1: return 1 else: return Fibonacci(i-1)+Fibonacci(i-2) def main(): a=time.time() for i in range(1,101): print(Fibonacci(i)) b=time.time() print("running time:%s Seconds"%(b-a)) main()

2、迭代实现

#C语言版本

#include <stdio.h> int fibonacci(int n) //定义斐波那契函数 { if(n == 0) //定义初始值 return 0; if(n == 1 || n == 2) return 1; int a=1,b=1,c=0; //定义初始值 //用一个for循环，a、b分别为前两项，c为前两项之和，得到c后进行交换更新a、b的值，进行n次交换即可。 for(int i=3;i<=n;i++) //更新操作 { c = a+b; a = b; b = c; } return c; //c即为结果输出 } int main() { int t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); printf("%d\n", fibonacci(n)); } return 0; }

#python版本

讯享网import time def fib(n): if n<=0: return 0 if n == 1: return n first, second, third = 0, 1, 0 for i in range(2, n+1): third = first + second first = second second = third return third def main(): a=time.time() for i in range(1,101): print(fib(i)) b=time.time() print("%s"%(b-a)) main()

3、总结

因为递归算法存在着大量的重复计算，在N趋近于较大值时，可能会造成内存溢出或超时的情况，又因为使用迭代算法的情况下同样可以实现计算斐波那契数列第N项的功能，所以在N值很大时我们优先使用迭代算法。

三、兔子问题

题目描述

        这是一个有趣的古典数学问题，著名意大利数学家Fibonacci曾提出一个问题：有一对小兔子，从出生后第3个月起每个月都生一对兔子。小兔子长到第3个月后每个月又生一对兔子。按此规律，假设没有兔子死亡，第一个月有一对刚出生的小兔子，问第n个月有多少对兔子？

输入：月数n（1<=n<=44）。                                输出：输出第n个月有多少对兔子。

样例输入 3                                                            样例输出2

#递归

#include<stdio.h> int fib(int n) { if(n==1||n==2) return 1; else return fib(n-1)+fib(n-2); } int main() { int n ; scanf("%d",&n); printf("%d",fib(n)); }

#循环

讯享网 #include<stdio.h> int main () { int i,n,item,n1=1,n2=1; scanf("%d",&n); if(n==1||n==2) item=1; for(i=3;i<=n;i++) { item=n1+n2; n2=n1; n1=item; } printf("%d",item); }

斐波那契问题（兔子问题）

学习日记

一、斐波那契数列的概念

二、斐波那契的复现

1、递归实现

2、迭代实现

3、总结

三、兔子问题

相关推荐