C語言如何解決青蛙跳臺階問題

小編給大家分享一下C語言如何解決青蛙跳臺階問題，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

1. 基礎問題

題目描述

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

諾，就像下面這樣

解題思路

其實我一看到這道題，我也是懵的，不知道從哪里著手分析，那我們就從最簡單的情況開始分析。

假如 n = 1，一共有一級臺階，顯然就只有一種跳法

一次跳1階；

假如 n = 2，一共有兩級臺階，共有兩種跳法

跳1階，再跳1階

跳2階

假設n = 3，共有三種跳法。

跳1階，跳1階，再跳1階

跳1階，再跳2階

跳2階, 再跳1階

（注：此過程圖是我從網上找的，實在是難得畫啦）

通過上面的分析，我們可以這樣思考問題

前往樓梯頂部的最后一步，要么跳1階，要么跳2階；

先假設f(n)為 n 級臺階的總跳法數；

那么第一次如果選擇跳一級的話，剩下的 n-1 級臺階的跳法數就為f(n−1)。

如果第一次跳兩級的話，剩下的 n-2 級臺階的跳法就是f(n−2)；

現在青蛙一次只能跳一級或兩級，所以我們可以推出以下公式：

咦，這玩意兒不就是我們 斐波那契數 嗎？

只不過有一點不同的是，斐波那契數列一般是以1,1,2,3,5,8,13……開始的；

而我們這是以1,2,3,5,8,13……開始的，少了最前面的一個1。

代碼實現

上面說到這個過程有點類似于斐波那契數，但又不完全是，所以我們先看主代碼部分

#include <stdio.h>
int jump(int n)
{
    if (n < 3)
    {
        //假設n的范圍是[0, 3]
        return n;
    }
    else
    {
        //n>3的時候
        return jump(n - 1) + jump(n - 2);
    }
}

int main()
{
    int num = 0;
    printf("請輸入一個臺階數:> ");
    scanf("%d", &num);

    int ret = jump(num);
    
    printf("小青蛙有 %d種 跳法\n", ret);
    return 0;
}

運行結果

但是，我們來看一下計算的過程

要計算f(6)，就需要先計算出子問題f(5)和f(4)

然后要計算f(5)，又要先算出子問題f(4)和f(3)，以此類推。

一直到f(2)和f(1)，遞歸樹才終止。

因此，青蛙跳階，遞歸解法的時間復雜度 等于O(1) * O(2?)=O(2?)

你仔細觀察這顆遞歸樹，你會發現存在「大量重復計算」；

比如f(4)被計算了兩次，f(3)被重復計算了3次…所以這個遞歸算法低效的原因，就是存在大量的重復計算！

所以我們可以對代碼進行優化

遞歸升級

在遞歸法的基礎上，新建一個長度為n的數組，用于在遞歸時存儲f(0)至f(n) 的數字值，重復遇到某數字時則直接從數組取用，避免了重復的遞歸計算。

所以我們設置一個數組，用于存放第一次計算某一個n的jump(n)。

當每一次要計算一個jump(n)的時候，就先查看數組中以n為下標的地方是否有值，有的話就可以不調用jump(n)，而直接從數組中取得結果值，否則再計算jump(n)。

代碼實現

#include <stdio.h>

long int f[1000]={0};
int jump(int n){
    //當只有一階臺階的時候，只有一種上臺階的方式。
    
    //當有2階臺階的時候，有2種上臺階的方式，一種是一次上一階，還有一種是一次上2個臺階。
    
    //現在設有n階臺階,如果n>2,那種應該有（先跳一階）+（先跳2階）的方式
    
    //如果先跳一階，那么就有jump(n-1)中方式。如果先跳2階，那么就有jump(n-2)中方式。
    
    //因此可以知道共有jump(n-1) + jump(n-2)種方式。
    if(n==1)
    {
        f[1]=1;
        return f[1];
    }

    if(n==0)
    {
        f[0]=1;
        return f[0];
    }

    if(n==2)
    {
        f[2]=2;
        return f[2];
    }
    else
    {
        if(f[n-1]!=0)
        {
            if(f[n-2]!=0)
            {
                return (f[n-1]+f[n-2]);
            }
            else
            {
                f[n-2]=jump(n-2);
                return (f[n-1]+f[n-2]);
            }
        }
        else
        {
            if(f[n-2]!=0)
            {
                f[n-1]=jump(n-1);
                return (f[n-1]+f[n-2]);
            }
            else
            {
                f[n-1]=jump(n-1);
                f[n-2]=jump(n-2);
                return (f[n-1]+f[n-2]);
            }
        }
    }
}

int main()
{
    int num = 0;
    printf("請輸入一個臺階數:> ");
    scanf("%d", &num);

    int ret = jump(num);

    printf("小青蛙有 %d種 跳法\n", ret);
    return 0;
}

運行結果

動態規劃解法

很快我又發現，不必把所有的記錄都記起來；

假設我有3階樓梯，我只需要知道跳2階和跳1階的方法數是多少就可以算出跳3階的方法數；

因此每次只需要保留n−1階和n−2階的方法數。

代碼實現

#include <stdio.h>

int jump(int n)
{
    //n=0、1、2的時候,直接返回n即可
    if (n < 3)
    {
        return n;
    }
    
    //第一個數為1
    int one = 1;

    //第二個數為2
    int two = 2;

    //用于存放前兩個數之和
    int sum = 0; 
    while (n > 2)
    {
        sum = one + two;
        one = two;
        two = sum;

        n--;
    }
    return sum;
}

int main()
{
    int num = 0;
    printf("請輸入一個臺階數:> ");
    scanf("%d", &num);

    int ret = jump(num);

    printf("小青蛙有 %d種 跳法\n", ret);
    return 0;
}

運行結果

2. 問題升級

題目描述

一只青蛙一次可以跳上一級臺階，也可以跳上二級臺階……，也可以跳n級，求該青蛙跳上一個n級的臺階總共需要多少種跳法。

解題思路

一只青蛙要想跳到n級臺階，可以從一級，二級……，也就是說可以從任何一級跳到n級

當臺階為1級時，f(1)=1；

當臺階為2級時，f(2)=1+1=2；

當臺階為3級時，f(3)=f(1)+f(2)+1=4；

當臺階為4級時，f(4)=f(1)+f(2)+f(3)+1=8；

當臺階為5級時，f(5)=f(1)+f(2)+f(3)+f(4)+1=16；

所以遞推公式我們很容易就能想到:f(n)=f(n−1)+f(n−2)+……+f(2)+f(1)+f(0)

最后這個f(0)是可以去掉的，因為0級就相當于沒跳，所以f(0)=0

然后我們把f(0)去掉再轉換一下：f(n−1)=f(n−2)+f(n−3)+……+f(2)+f(1)；

推導過程

我們列兩個等式：

①f(n)=f(n−1)+f(n−2)+f(n−3)+…+f(2)+f(1)

②f(n−1)=f(n−2)+f(n−3)+…+f(2)+f(1)

由①-②得，f(n)=2f(n−1)

代碼實現

遞歸方法

代碼示例

int jump(int n)
{
    if (n == 1)
    {
        return 1;
    }
    else
    {
        return 2 * jump(n - 1);
    }
}

int main()
{
    int num = 0;
    printf("請輸入一個臺階數:> ");
    scanf("%d", &num);

    int ret = jump(num);

    printf("小青蛙有 %d種 跳法\n", ret);
    return 0;
}

運行結果

非遞歸方法

當然這里也可以用非遞歸的方式來實現

那么非遞歸怎么去思考呢？

可以這樣理解：

然后使用用函數pow(2,n -1)，需要加頭文件<math.h>

但是我們這里可以不用庫函數來實現，給大家介紹一種神奇的運算

代碼示例

int jump(int n)
{
    if (n == 1)
    {
        return 1;
    }
    else
    {
        return 1 << (n-1);
    }
}

int main()
{
    int num = 0;
    printf("請輸入一個臺階數:> ");
    scanf("%d", &num);

    int ret = jump(num);

    printf("小青蛙有 %d種 跳法\n", ret);
    return 0;
}

運行結果

我這里選擇用<<左移操作符來計算

以上是“C語言如何解決青蛙跳臺階問題”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！