劍指offer之青蛙跳臺(tái)階問(wèn)題

1 問(wèn)題

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

 
2 分析

我們可以定位函數(shù)f(n),n為n級(jí)別的臺(tái)階，f(n)的值是青蛙有多少種跳法，我們知道當(dāng)n為1的時(shí)候，f(1) = 1;

當(dāng)n為2的時(shí)候，我們知道可以先跳一級(jí)再跳一級(jí)，或者直接跳2級(jí)，這里就有2種跳法，所以f(2) = 2;

當(dāng)n為3的時(shí)候，我們可以這樣理解，青蛙先跳一級(jí)，后面還有n-1級(jí)需要跳，所以這里的跳法為f(n - 1);

或者青蛙先跳兩級(jí)，后面還有n-2級(jí)需要跳，所以這里的跳法為f(n - 2); 所以我們知道當(dāng)n大于2時(shí)，f(n) = f(n - 1) + f(n - 2);

    f(1) = 1; (n = 1)
    f(2) = 2; (n = 2)
    f(n) = f(n - 1) + f(n - 2); (n > 2)

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

    #include <stdio.h>
     
    long long fibonacciOne(unsigned int n)
    {
        if (n <= 0)
            return 0;
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        return fibonacciOne(n - 1) + fibonacciOne(n - 2);
    }
     
    long long fibonacciTwo(unsigned int n)
    {
        if (n <= 0)
            return 0;
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        long long first = 1;
        long long second = 2;
        long long sum = 0;
        for (int  i = 3; i <=n ; ++i)
        {
            sum = first + second;
            first = second;
            second = sum;
        }
        return sum;
    }
     
    int main(void)
    {
        long long resultOne = fibonacciOne(4);
        long long resultTwo = fibonacciTwo(4);
        printf("resultOne is %lld\n", resultOne);
        printf("resultTwo is %lld\n", resultTwo);
        return 0;
    }

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

    resultOne is 5
    resultTwo is 5

 

 



 


作者：chen.yu
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號(hào)：編程入門(mén)到禿頭 或掃描下面二維碼
零基礎(chǔ)入門(mén)進(jìn)階人工智能(鏈接)