文章目錄
- 什么是斐波那契數列（Fibonacci）?
- 如何求第n個斐波那契數？
- 青蛙跳臺階問題
什么是斐波那契數列（Fibonacci）?
斐波那契數列（Fibonacci sequence），又稱黃金分割數列，因數學家萊昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數列”，指的是這樣一個數列：0、1、1、2、3、5、8、13、21、34、……在數學上，斐波那契數列以如下被以遞推的方法定義：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）在現代物理、準晶體結構、化學等領域，斐波納契數列都有直接的應用，為此，美國數學會從 1963 年起出版了以《斐波納契數列季刊》為名的一份數學雜志，用于專門刊載這方面的研究成果，
如何求第n個斐波那契數？
有兩種方式來求得斐波那契數，一種是用遞回的方法來求，第二種是用迭代的方法（也就是我們通常所說的回圈）求，兩種方法各有千秋，下面一起來講解一下，
1.遞回求解
關于遞回的基本概念這里就不贅述了，如有不懂可點以下鏈接查看：
函式遞回講解
通過對斐波那契數列的了解，我們不難寫出它的通式：
寫出通式后，用遞回的方法就比較簡單了：
long long Fibonacci(int n)
{
if (n == 0 || n == 1)
return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}//遞回
int main()
{
int n=0;
scanf("%d",&n);
printf("%d",Fibonacci(n));
return 0;
}
優點：代碼量少，便于理解
缺點：代碼執行的次數相對多（會多次執行同一個函式），若n特別大，容易造成堆疊溢位的問題
2.迭代求解
long long Fibonacci(int n)
{
if (n == 0)
return 0;
else if (n == 1)
return 1;
long long a = 0;
long long b = 1;
long long c = 1;
while (n >=2)
{
a = b;
b = c;
c = a + b;
n--;
}
return c;
}//迭代法
主函式（略）
相較于遞回，迭代的方法雖然代碼量相對比較多，但總體執行起來效率更高，
青蛙跳臺階問題
問題描述：一只青蛙一次可以跳 1 階臺階，也可以跳2 階，求該青蛙跳上一個n 級的臺階總共有多少種跳法?
分析：
（1）n=1 跳法：1種
（2）n=2 跳法：2種
（3）n=3 跳法：3種
（4）n=4 跳法：5種
（5）n=5 跳法：8種
由數學歸納法分析可得：
（6）n=n 跳法：Jump(n - 1) + Jump(n - 2) 這里想到遞回思想
類似于斐波那契數列：1 1 2 3 8 13 21 34 55 …
所以由以上分析我們很容易就能寫出代碼如下：
//回圈求解
int Jump2(int n)
{
int a = 1;
int b = 2;
int c = n;
while (n>2)
{
c = a + b;
a = b;
b = c;
n--;
}
return c;
}
//遞回求解 速度慢，求的過大時可能存在堆疊溢位--stack overflow
int Jump1(int n)
{
if (n <= 2)
{
return n;
}
else
{
return Jump1(n - 1) + Jump1(n - 2);
}
}
int main()
{
int n = 0;
int ret = 0;
printf("請輸入臺階數:");
scanf("%d", &n);
ret = Jump1(n);
printf("遞回法:有%d種跳法\n", ret);
ret = Jump2(n);
printf("回圈法:有%d種跳法\n", ret);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/291232.html
標籤：其他
下一篇：世界500強是如何解決千億流量留存問題的，《Ceph分布式存盤架構》-使用CentOS 7部署 Ceph分布式存盤架構-為他們解決什么問題。