劍指Offer系列(java版,詳細解析)10.斐波那契數列

程序員社區 2022-01-08 04:43:56 阅读数:793

offer 系列 java 解析

題目一

題目描述

劍指 Offer 10- I. 斐波那契數列

難度簡單108

寫一個函數,輸入 n ,求斐波那契(Fibonacci)數列的第 n 項(即 F(N))。斐波那契數列的定義如下:

F(0) = 0, F(1) = 1F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契數列由 0 和 1 開始,之後的斐波那契數就是由之前的兩數相加而得出。

答案需要取模 1e9+7(1000000007),如計算初始結果為:1000000008,請返回 1。

示例 1:

輸入:n = 2輸出:1

示例 2:

輸入:n = 5輸出:5

提示:

  • 0 <= n <= 100

測試用例

  • 功能測試(如輸入3、5、10等)
  • 邊界值測試(如輸入0、1、2)
  • 性能測試(輸入較大的數值,如40、50、100等)

題目考點

  • 考察應聘者對遞歸、循環的理解及編碼能力
  • 考察隊時間複雜度的分析能力
  • 如果結合實際問題,可能還考察數學建模能力

解題思路

循環求餘法:

大數越界: 隨著 n 增大, f(n) 會超過 Int32 甚至 Int64 的取值範圍,導致最終的返回值錯誤。

  • 求餘運算規則: 設正整數 x, y, p ,求餘符號為 ⊙ \odot ,則有 ( x + y ) ⊙ p = ( x ⊙ p + y ⊙ p ) ⊙ p (x + y) \odot p = (x \odot p + y \odot p) \odot p (x+y)p=(xp+yp)p
  • 解析: 根據以上規則,可推出 f ( n ) ⊙ p = [ f ( n − 1 ) ⊙ p + f ( n − 2 ) ⊙ p ] ⊙ p f(n) \odot p = [f(n-1) \odot p + f(n-2) \odot p] \odot p f(n)p=[f(n1)p+f(n2)p]p ,從而可以在循環過程中每次計算 s u m = ( a + b ) ⊙ 1000000007 sum = (a + b) \odot 1000000007 sum=(a+b)1000000007,此操作與最終返回前取餘等價。

參考解題

public class Solution1 {
 public int Fibonacci(int n) {
 if (n < 2) {
 return n; } int pre1 = 0; int pre2 = 1; int fib = 0; for (int i = 2; i <=n; i++) {
 fib = pre1 + pre2; pre1 = pre2; pre2 = fib; } return fib; }}

題目二

題目描述

一只青蛙一次可以跳上1級臺階,也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法(先後次序不同算不同的結果)。

題目考點

考察數學建模能力,發現實質是斐波那契數列。

解題思路

與斐波那契數列相同,但是還是需要分析一下:

先分析最簡單的情况。如果只有1級臺階,那顯然只有一種跳法。如果有2級臺階,那就有兩種跳法,分為每次跳1級,和一次跳兩級。

再討論一般情况,我們把n級臺階時的跳法看成n的函數,記為f(n)。當 n>2 時,第一次跳的時候就有兩種不同的選擇:一是第一次跳1級,此時跳法數目等於後面剩下的 n-1 級臺階的跳法數目,即為 f(n-1) ,二是第一次跳2級,此時跳法數目等於後面剩下的 n-2 級臺階的跳法數目,即為 f(n-2) 。因此,n級臺階的不同跳法的總數f(n) = f(n-1) + f(n-2)。

我們馬上就可以看出這就是斐波那契數列了。

自己解題

/** * 青蛙臺階問題 */public class FrogSolution {
 /** * 采用斐波那契解法 * @param target * @return */ public int JumpFloor(int target) {
 if (target < 3) {
 return target; } int pre1 = 1; int pre2 = 2; int fib = 0; for (int i = 3; i <= target; i++) {
 fib = pre1 + pre2; pre1 = pre2; pre2 = fib; } return fib; }}

補充

通常基於遞歸實現的代碼比基於循環實現的代碼要簡潔很多,更加容易實現。如果面試官沒有特殊要求,則應聘者可以采用遞歸的方法編程,但是我們還是應該以時間複雜度為首要考慮。

版权声明:本文为[程序員社區]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201080443563469.html