1. 基礎(chǔ)問題

題目描述

一只青蛙一次可以跳上 1 級(jí)臺(tái)階，也可以跳上 2 級(jí)。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法。

諾，就像下面這樣

解題思路

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

假如 n = 1，一共有一級(jí)臺(tái)階，顯然就只有一種跳法

一次跳1階；

假如 n = 2，一共有兩級(jí)臺(tái)階，共有兩種跳法

跳1階，再跳1階

跳2階

假設(shè)n = 3，共有三種跳法。

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

跳1階，再跳2階

跳2階, 再跳1階

（注：此過程圖是我從網(wǎng)上找的，實(shí)在是難得畫啦）

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

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

先假設(shè)f(n)為 n 級(jí)臺(tái)階的總跳法數(shù)；

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

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

現(xiàn)在青蛙一次只能跳一級(jí)或兩級(jí)，所以我們可以推出以下公式：

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

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

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

代碼實(shí)現(xiàn)

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

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

int main()
{
    int num = 0;
    printf("請(qǐng)輸入一個(gè)臺(tái)階數(shù):> ");
    scanf("%d", &num);

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

運(yùn)行結(jié)果

但是，我們來看一下計(jì)算的過程

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

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

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

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

你仔細(xì)觀察這顆遞歸樹，你會(huì)發(fā)現(xiàn)存在「大量重復(fù)計(jì)算」；

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

所以我們可以對(duì)代碼進(jìn)行優(yōu)化

遞歸升級(jí)

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

所以我們?cè)O(shè)置一個(gè)數(shù)組，用于存放第一次計(jì)算某一個(gè)n的jump(n)。

當(dāng)每一次要計(jì)算一個(gè)jump(n)的時(shí)候，就先查看數(shù)組中以n為下標(biāo)的地方是否有值，有的話就可以不調(diào)用jump(n)，而直接從數(shù)組中取得結(jié)果值，否則再計(jì)算jump(n)。

代碼實(shí)現(xiàn)

#include <stdio.h>

long int f[1000]={0};
int jump(int n){
    //當(dāng)只有一階臺(tái)階的時(shí)候，只有一種上臺(tái)階的方式。
    
    //當(dāng)有2階臺(tái)階的時(shí)候，有2種上臺(tái)階的方式，一種是一次上一階，還有一種是一次上2個(gè)臺(tái)階。
    
    //現(xiàn)在設(shè)有n階臺(tái)階,如果n>2,那種應(yīng)該有（先跳一階）+（先跳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("請(qǐng)輸入一個(gè)臺(tái)階數(shù):> ");
    scanf("%d", &num);

    int ret = jump(num);

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

運(yùn)行結(jié)果

動(dòng)態(tài)規(guī)劃解法

很快我又發(fā)現(xiàn)，不必把所有的記錄都記起來；

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

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

代碼實(shí)現(xiàn)

#include <stdio.h>

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

    //第二個(gè)數(shù)為2
    int two = 2;

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

        n--;
    }
    return sum;
}

int main()
{
    int num = 0;
    printf("請(qǐng)輸入一個(gè)臺(tái)階數(shù):> ");
    scanf("%d", &num);

    int ret = jump(num);

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

運(yùn)行結(jié)果

2. 問題升級(jí)

題目描述

一只青蛙一次可以跳上一級(jí)臺(tái)階，也可以跳上二級(jí)臺(tái)階……，也可以跳n級(jí)，求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共需要多少種跳法。

解題思路

一只青蛙要想跳到n級(jí)臺(tái)階，可以從一級(jí)，二級(jí)……，也就是說可以從任何一級(jí)跳到n級(jí)

當(dāng)臺(tái)階為1級(jí)時(shí)，f(1)=1；

當(dāng)臺(tái)階為2級(jí)時(shí)，f(2)=1+1=2；

當(dāng)臺(tái)階為3級(jí)時(shí)，f(3)=f(1)+f(2)+1=4；

當(dāng)臺(tái)階為4級(jí)時(shí)，f(4)=f(1)+f(2)+f(3)+1=8；

當(dāng)臺(tái)階為5級(jí)時(shí)，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)

最后這個(gè)f(0)是可以去掉的，因?yàn)?級(jí)就相當(dāng)于沒跳，所以f(0)=0

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

推導(dǎo)過程

我們列兩個(gè)等式：

①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)

代碼實(shí)現(xiàn)

遞歸方法

代碼示例

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

int main()
{
    int num = 0;
    printf("請(qǐng)輸入一個(gè)臺(tái)階數(shù):> ");
    scanf("%d", &num);

    int ret = jump(num);

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

運(yùn)行結(jié)果

非遞歸方法

當(dāng)然這里也可以用非遞歸的方式來實(shí)現(xiàn)

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

可以這樣理解：

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

但是我們這里可以不用庫函數(shù)來實(shí)現(xiàn)，給大家介紹一種神奇的運(yùn)算

代碼示例

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

int main()
{
    int num = 0;
    printf("請(qǐng)輸入一個(gè)臺(tái)階數(shù):> ");
    scanf("%d", &num);

    int ret = jump(num);

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

運(yùn)行結(jié)果

我這里選擇用<<左移操作符來計(jì)算

3. 特性總結(jié)

其實(shí)這道算法題的本質(zhì)可以說就是斐波那契數(shù)的衍生；

反言之，對(duì)于算法，我的理解：算法本質(zhì)就是數(shù)學(xué)的解題過程

以上就是C語言解決青蛙跳臺(tái)階問題(升級(jí)版)的詳細(xì)內(nèi)容，更多關(guān)于C語言青蛙跳臺(tái)階的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論