F = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...}
F 0 = 0, F 1 = 1, F n = F n - 1 + F n - 2 ;
n ≥ 0,n ∈ Z
在Java中取得前n個斐波那契數
假設我們有一個任務來取得前 n 個斐波那契數。-
案例0.1:
某個數字 n 來到我們身邊:
int[] arr = new int[n]; arr[0] = 0; arr[1] = 1; for (int i = 2; i < arr.length; ++i) { arr[i] = arr[i - 1] + arr[i - 2]; }
我們建立一個大小為 n 的陣列。前兩個元素將等於 0 和 1,其餘元素是透過執行此循環並使用數組中的先前數字獲得的。
我們顯示:
for (int i = 0; i < arr.length; ++i) { System.out.println(arr[i]); }
設定int n = 10;
我們得到:
0 1 1 2 3 5 8 13 21 34
-
對於情況 1.1,解決方案實際上沒有什麼不同:
int[] arr = new int[n]; arr[0] = 1; arr[1] = 1; for (int i = 2; i < arr.length; ++i) { arr[i] = arr[i - 1] + arr[i - 2]; }
我們需要更改的只是數組 arr[0] 的第一個元素:從 0 到 1。相應地,前 10 個元素將是:
1 1 2 3 5 8 13 21 34 55
通過流的前 n 個斐波那契數
但我們想展示我們的水平。那麼讓我們看看使用Stream 的解決方案會是什麼樣子。-
對於 0.1:
Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]}) .limit(n) .map(y -> y[0]) .forEach(x -> System.out.println(x));
Stream類別的靜態 iterate 方法傳回一個無限有序流,該流是透過將該函數應用於初始數組 arr 而建立的。在我們的例子中,該功能是根據前一個陣列設定組成每個新數組的規則。結果,我們將得到一個數組流:
{0,1} {1,1} {1, 2} {2, 3} {3, 5} {5, 8} {8, 13} {13, 21} {21, 34} {34, 55} …..
但它們的數量是無限的,因此使用 .limit(n) 我們將元素的數量減少到前 n (在我們的例子中減少到 10)。
但是,我們不需要數組流,因此使用 .map(y -> y[0]) 我們選擇每個數組的第一個元素並獲取包含我們需要的數字的流,並使用 forEach 將其列印到控制台。
看起來更酷,不是嗎?
第一個元素為 1,1,此程式碼也幾乎相同:Stream.iterate(new int[]{1, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]}) .limit(n) .map(y -> y[0]) .forEach(x -> System.out.println(x));
同樣,差異在於初始元素:我們設定了 {1, 1},而不是 {0, 1}
實際上,結果將與前面的範例相同。
斐波那契數列之和
如果我們被要求獲得直到第 n 個元素(含第 n 個元素)的斐波那契數列總和,該怎麼辦?這不應該給我們帶來任何困難。讓我們採用流的解決方案,並將 forEach 替換為其他幾個方法:-
對於 0.1:
int n = 10; int result = Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]}) .limit(n) .map(t -> t[0]) .mapToInt(Integer::intValue) .sum(); System.out.println(result);
使用 .mapToInt(Integer::intValue) 我們將流轉換為數位 IntStream 並使用其 .sum() 方法來取得所有元素的總和。
- 對於初始元素為 1,1 的情況,我們設定 {1, 1},而不是 {0, 1}。
取得斐波那契數列中的第 n 個數字
有時,系統會要求您列印的不是一系列數字,而是列印斐波那契數列中的第 n 個數字。通常,這只會使任務變得更容易,因為您可以輕鬆適應先前的解決方案。那麼,透過遞歸來解決問題怎麼樣呢?-
對於 0.1:
public int getFibonacciValue(int n) { if (n <= 1) { return 0; } else if (n == 2) { return 1; } else { return getFibonacciValue(n - 1) + getFibonacciValue(n - 2); } }
要使用 0,1 運行演算法,需要指定當我們嘗試取得第一個元素時,我們取得 0,第二個元素取得 - 1。事實上,與先前的解決方案一樣,我們需要設定前兩個元素元素。
-
1.1 的實作會略有不同:
public int getFibonacciValue(int n) { if (n == 0) { return 0; } else if (n == 1) { return 1; } else { return getFibonacciValue(n - 1) + getFibonacciValue(n - 2); } }
在這種情況下,我們只需將第一個元素設為 1,因為第二個元素將相同,且該方法的回應將相同。
同時,我們將方法的反應設為0,因為如果我們不設定它,那麼當2作為參數時,會遞歸呼叫相同的方法,但參數為0。接下來,將啟動相同的方法,但為負數,依此類推,直到負無窮大。結果,我們將收到一個 StackOverflowError。
GO TO FULL VERSION