斐波那契數列

2022-11-24 20:16:18 字數 1095 閱讀 5879

斐波那契數列滿足如下定義:

當n=0時,f(0)=0;

當n=1時,f(1)=1;

當n>1時,f(n)=f(n-1)+f(n-2);

可以很快寫出類似如下的**:

1

public

static

long f(int

n)

但是如上遞迴解法有很嚴重的效率問題,例如計算f(10)的值,需要f(8)和f(9)的和,子遞迴一f(8)需要計算f(6)和f(7)的和,子遞迴二中計算f(9)的值需要f(8)和f(7)的和,此時f(8)又重複算了一次。此演算法的時間複雜度是以n的指數的方式遞增的。

改進的方法可以考慮從f(0)逐步計算到f(n)(即先根據f(0)和f(1)算出f(2),再根據f(1)和f(2)算出f(3)……),並用一個長度為2的整型陣列儲存每次需要迭代的值。很明顯,此演算法的時間複雜度值有o(n)。

1

public

static

long f(int

n);4

if(n < 2) return

arr[n];

5long

psum;

6for(int i = 2; i <= n; i++)

11return arr[1];

12 }

接下來來看一下斐波那契數列的應用

先從最簡單情況出發:

如果有1級臺階,則只有一種跳法,即f(1)=1。

如果有2級臺階,則可以有兩種跳法(1級1級跳或2級跳),即f(2)=2。

如果有3級臺階,考慮第一次跳的時候有兩種選擇:一種是一次跳1級,則此跳法數目等於剩下(3-1)級臺階的跳法,即等於f(3-1),另一種是一次跳2級,則此跳法數目等於剩下的(3-2)級臺階的跳法,即等於f(3-2),所以f(3)=f(3-1)+f(3-2)=3。

再從一般情況出發:

當n>2時,第一次跳有兩種選擇:一種是一次跳1級,則跳法數目等於後面剩下(n-1)級臺階的跳法,即f(n-1),一種是一次跳2級,則跳法數目等於後面剩下的(n-2)級臺階的跳法,即f(n-2),所以f(n)=f(n-1)+f(n-2)。

不難看出這實際上就是斐波那契數列了。

斐波那契數

題目描述 小明現在知道斐波那契數列中的第x個數模p後的值n,即fabonacci x mod p n,以及x可能的最大值m,如果再對於斐波那契數列中每一個數都模p,他想知道這個數可能出現在第幾個。輸入描述 一行,共3個整數,第一個數為n,第二個數為p,第三個數為x可能的最大值m,三個數以空格隔開。輸...

斐波那契博弈

處理何種問題 有一堆個數為n的石子,遊戲雙方輪流取石子,滿足 1 先手不能在第一次把所有的石子取完,且最少取1個 2 之後每次可以取得石子數介於1到對手剛取的石子數的2倍之間 包含1和對手剛取得石子數的兩倍 約定取走最後一個石子的人為贏家,求誰獲勝。此類問題有一個結論 當n是斐波那契數時,後手必勝 ...

斐波那契樹

原題 斐波那契樹 定義滿足下面條件的樹是斐波拉契樹 現在給你樹的深度 n 每個葉子節點的深度都為 n 問求距離為 d 的白色點對一共有多少對?需要求出 1 leq d leq2 n 的每一個取值的答案。輸入僅一行,一個整數nn,表示這個斐波拉契樹的深度。輸出共 2 n 個整數,第 i 個整數表示當 ...