斐波那契額數列及青蛙跳台階問題

 斐波那契（Fibonacci）數列定義如下：

效率很低的解法：

1

2

3

4

5

6

7

8

9

10

<code>long</code> <code>long</code> <code>Fibonacci_Solution1(unsigned </code><code>int</code> <code>n)</code>

<code>{</code>

<code>    </code><code>if</code><code>(n &lt;= 0)</code>

<code>        </code><code>return</code> <code>0;</code>

<code>    </code><code>if</code><code>(n == 1)</code>

<code>        </code><code>return</code> <code>1;</code>

<code>    </code><code>return</code> <code>Fibonacci_Solution1(n - 1) + Fibonacci_Solution1(n - 2);</code>

<code>}</code>

改進的算法：從下往上計算。首先根據f(0)和f(1)算出f(2)，再根據f(1)和f(2)算出f(3)。。。。。依此類推就可以算出第n項了。很容易了解，這種思路的時間複雜度是o(n)。實作代碼如下：

11

12

13

14

15

16

17

18

<code>long</code> <code>long</code> <code>Fibonacci(unsigned n)</code>

<code>    </code><code>int</code> <code>result[2] = {0 , 1};</code>

<code>    </code><code>if</code><code>(n &lt; 2)</code>

<code>        </code><code>return</code> <code>result[n];</code>

<code>    </code><code>long</code> <code>long</code> <code>fibMinusOne = 1;</code>

<code>    </code><code>long</code> <code>long</code> <code>fibMinusTwo = 0;</code>

<code>    </code><code>for</code><code>(unsigned </code><code>int</code> <code>i = 2 ; i &lt;= n ; ++i)</code>

<code>    </code><code>{</code>

<code>        </code><code>fibN = fibMinusOne + fibMinusTwo;</code>

<code>        </code><code>fibMinusTwo = fibMinusOne;</code>

<code>        </code><code>fibMinusOne = fibN;</code>

<code>    </code><code>}</code>

<code>    </code> 

<code>    </code><code>return</code> <code>fibN;</code>

可以把n級台階時的跳法看成是n的函數，記為f(n)。當n&gt;2時，第一次跳的時候就有兩種不同的選擇：一是第一次隻跳1級，此時跳法數目等于後面剩下的n-1級台階的跳法數目，即為f(n-1);另一種選擇是第一次跳2級，此時跳法數目等于後面剩下n-2級台階的跳法數目，即為f(n-2)。是以，n級台階的不同跳法的總數f(n)=f(n-1)+f(n-2)。分析到這裡，不難看出這實際上就是斐波那契數列了。

19

20

21

22

<code>#include&lt;iostream&gt;</code>

<code>using</code> <code>namespace</code> <code>std;</code>

<code> </code><code>long</code> <code>Fibonacci_Solution1(unsigned </code><code>int</code> <code>n)</code>

<code>int</code> <code>main()</code>

<code>    </code><code>int</code> <code>n;</code>

<code>    </code><code>cin&gt;&gt;n;</code>

<code>    </code><code>cout&lt;&lt;Fibonacci_Solution1(n)&lt;&lt;endl;</code>

<code>   </code> 

<code>   </code><code>return</code> <code>0;</code>

 在青蛙跳台階的問題中，如果把條件改成：一隻青蛙一次可以跳上1級台階，也可以跳上2級。。。。。它也可以跳上n級，此時該青蛙跳上一個n級的台階總共有多少種跳法？

用數學歸納法可以證明f(n)=2n-1.

本文轉自夏雪冬日部落格園部落格，原文連結：http://www.cnblogs.com/heyonggang/p/3405089.html，如需轉載請自行聯系原作者