關(guān)于C語(yǔ)言跳臺(tái)階問題的解決方法

2020-02-24 14:33:48

字體：大中小

供稿：網(wǎng)友

今天風(fēng)和日麗的，那我們也不能閑著，今天給你們帶來這篇關(guān)于C語(yǔ)言跳臺(tái)階問題的解決方法，本文對(duì)C語(yǔ)言中跳臺(tái)階問題的解決方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友跟隨武林技術(shù)頻道的小編來參考下吧。

題目：一個(gè)臺(tái)階總共有n級(jí)，如果一次可以跳1級(jí)，也可以跳2級(jí)。求總共有多少種跳法，并分析算法的時(shí)間復(fù)雜度。
答：用一個(gè)函數(shù)f(n)來表示n級(jí)臺(tái)階總的跳法。1、只有1個(gè)臺(tái)階，則f(1) = 1;
2、有2個(gè)臺(tái)階，則f(2) = 2;
3、當(dāng)有n個(gè)臺(tái)階時(shí)，如果第一次跳1級(jí)，有f(n-1)種跳法，如果第一次跳2級(jí)，有f(n - 2)種跳法，即f(n) = f(n-1) + f(n-2)。
即為Fibonacci序列。

復(fù)制代碼代碼如下:

#include "stdafx.h"
#include 
using namespace std;
//循環(huán)
int TotalStep(int n)
{
    if (n <= 0)
    {
        return 0;
    }
    else if (1 == n || 2 == n)
    {
        return n;
    }
    int first = 1;
    int second = 2;
    int total = 0;
    for (int i = 3; i <= n; i++)
    {
        total = first + second;
        first = second;
        second = total;
    }
    return total;
}
//遞歸
int RecurTotalStep(int n)
{
    if (n <= 0)
    {
        return 0;
    }
    else if (n == 1 || n == 2)
    {
        return n;
    }
    else
    {
        return RecurTotalStep(n - 1) + RecurTotalStep(n - 2);
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    cout<    cout<    return 0;
}(20)(20)