c語(yǔ)言 跳臺(tái)階問(wèn)題的解決方法
更新時(shí)間：2013年05月24日 09:29:20 作者：
本篇文章是對(duì)c語(yǔ)言中跳臺(tái)階問(wèn)題的解決方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下
題目：一個(gè)臺(tái)階總共有n級(jí)，如果一次可以跳1級(jí)，也可以跳2級(jí)。求總共有多少種跳法，并分析算法的時(shí)間復(fù)雜度。
答：用一個(gè)函數(shù)f(n)來(lái)表示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序列。
#include "stdafx.h"
#include <iostream>
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<<TotalStep(20)<<endl;
cout<<RecurTotalStep(20)<<endl;
return 0;
}
運(yùn)行界面如下：
答：用一個(gè)函數(shù)f(n)來(lái)表示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 <iostream>
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<<TotalStep(20)<<endl;
cout<<RecurTotalStep(20)<<endl;
return 0;
}
運(yùn)行界面如下：
相關(guān)文章
類(lèi)是創(chuàng)建對(duì)象的模板，一個(gè)類(lèi)可以創(chuàng)建多個(gè)對(duì)象，每個(gè)對(duì)象都是類(lèi)類(lèi)型的一個(gè)變量；創(chuàng)建對(duì)象的過(guò)程也叫類(lèi)的實(shí)例化。每個(gè)對(duì)象都是類(lèi)的一個(gè)具體實(shí)例（Instance），擁有類(lèi)的成員變量和成員函數(shù)2021-10-10
C++基礎(chǔ)知識(shí)之運(yùn)算符重載詳解
這篇文章主要為大家詳細(xì)介紹了C++基礎(chǔ)知識(shí)之運(yùn)算符重載，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-02-02
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言中順序棧和鏈棧的定義和使用，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)C語(yǔ)言有一定的幫助，感興趣的小伙伴可以了解一下2022-10-10
詳解C語(yǔ)言結(jié)構(gòu)體中的函數(shù)指針
這篇文章主要介紹了詳解C語(yǔ)言結(jié)構(gòu)體中的函數(shù)指針,文中對(duì)函數(shù)指針的基本概念也有講解,需要的朋友可以參考下2016-04-04
typename在C++類(lèi)模板或者函數(shù)模板中經(jīng)常使用的關(guān)鍵字，此時(shí)作用和class相同，只是定義模板參數(shù)，下面通過(guò)例子給大家介紹c++模板typename的具體用法，一起看看吧2021-07-07
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言的文件操作，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-03-03
C++中多態(tài)的定義及實(shí)現(xiàn)詳解
這篇文章主要給大家介紹了關(guān)于C++中多態(tài)的定義及實(shí)現(xiàn)的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-05-05
適合初學(xué)者的C語(yǔ)言數(shù)據(jù)類(lèi)型的講解
在 C 語(yǔ)言中，數(shù)據(jù)類(lèi)型指的是用于聲明不同類(lèi)型的變量或函數(shù)的一個(gè)廣泛的系統(tǒng)。變量的類(lèi)型決定了變量存儲(chǔ)占用的空間，以及如何解釋存儲(chǔ)的位模式。2022-04-04
基于Qt制作一個(gè)定時(shí)關(guān)機(jī)的小程序
這篇文章主要為大家詳細(xì)介紹了如何基于Qt制作一個(gè)有趣的定時(shí)關(guān)機(jī)的小程序,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-12-12
C++實(shí)現(xiàn)將數(shù)據(jù)寫(xiě)入Excel工作表的示例代碼
直觀的界面、出色的計(jì)算功能和圖表工具，使Excel成為最流行的個(gè)人計(jì)算機(jī)數(shù)據(jù)處理軟件。在本文中，您將學(xué)習(xí)如何使用?Spire.XLS?for?C++?創(chuàng)建?Excel?文檔，以及如何將數(shù)據(jù)寫(xiě)入?Excel?工作表2023-03-03