溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

斐波拉契的變形題

發布時間:2020-07-22 19:39:08 來源:網絡 閱讀:665 作者:小止1995 欄目:編程語言

 一只青蛙一次可以跳上 1 級臺階,也可以跳上2 級。求該青蛙跳上一個n 級的臺階總共有多少種跳法

假設,一級臺階,有f(1)種方法,二級有f(2)種,以此類推,n級有f(n)種方法。

可以看出,f(1)=1;f(2)=2。

那么,假設n級臺階,那么第一步就有兩種情況,跳一步,跟跳兩步。

情況一:跳一步,那么接下去的就是f(n-1);

情況二:跳兩步,那么接下去的就是f(n-2)。

所以總數是f(n)=f(n-1)+f(n-2)。

public int  cal(int n){
    if(n<=0){
        return -1;
    }
    if(n==1||n==2){
        return n;
    }
    else{
        return cal(n-1)+cal(n-2);
    }
}

一只青蛙一次可以跳上1級臺階,也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。

假設f(n)是n個臺階跳的次數。

  1. f(1) = 1

  2. f(2) 會有兩個跳得方式,一次1階或者2階,這回歸到了問題f(1),f(2) = f(2-1) + f(2-2)

  3. f(3) 會有三種跳得方式,1階、2階、3階,那么就是第一次跳出1階后面剩下:f(3-1);第一次跳出2階,剩下f(3-2);第一次3階,那么剩下f(3-3).因此結論是
    f(3) = f(3-1)+f(3-2)+f(3-3)

  4. f(n)時,會有n中跳的方式,1階、2階...n階,得出結論:

f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1) == f(n) = 2*f(n-1)

public long jumpFloor(int n) {
    if (n <= 0)
        return -1;
    if (n == 1)
        return 1;
    return 2 * jumpFloor(n - 1);
}

考慮到效率,也可以改成迭代來做。

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

亚洲午夜精品一区二区_中文无码日韩欧免_久久香蕉精品视频_欧美主播一区二区三区美女