c語言 跳臺(tái)階問題的解決方法
更新時(shí)間：2013年05月24日 09:29:20 作者：
本篇文章是對c語言中跳臺(tái)階問題的解決方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下
題目：一個(gè)臺(tái)階總共有n級，如果一次可以跳1級，也可以跳2級。求總共有多少種跳法，并分析算法的時(shí)間復(fù)雜度。
答：用一個(gè)函數(shù)f(n)來表示n級臺(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級，有f(n-1)種跳法，如果第一次跳2級，有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)來表示n級臺(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級，有f(n-1)種跳法，如果第一次跳2級，有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)文章
這篇文章主要介紹了C++ bitset用法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-08-08
在ANSI C的任意一種實(shí)現(xiàn)中，存在2中不同的環(huán)境。第一種是翻譯環(huán)境，負(fù)責(zé)將源代碼轉(zhuǎn)換成可執(zhí)行的機(jī)器指令；第二種是執(zhí)行環(huán)境，用于實(shí)際執(zhí)行代碼。一個(gè)程序從源代碼到可執(zhí)行程序一共會(huì)經(jīng)歷四個(gè)過程，分別是預(yù)處理、編譯、匯編、鏈接，本篇讓我們來了解編譯與預(yù)處理2022-04-04
atoi和itoa函數(shù)的實(shí)現(xiàn)方法
本文介紹了，atoi和itoa函數(shù)的實(shí)現(xiàn)方法，需要的朋友可以參考一下2013-03-03
使用opencv實(shí)現(xiàn)車道線檢測實(shí)戰(zhàn)代碼
這篇文章主要介紹了opencv車道線檢測實(shí)戰(zhàn),效果非常逼真，代碼簡單易懂，對opencv車道線檢測實(shí)戰(zhàn)代碼感興趣的朋友一起看看吧2022-03-03
C語言學(xué)生成績管理系統(tǒng)課程設(shè)計(jì)
這篇文章主要為大家詳細(xì)介紹了C語言學(xué)生成績管理系統(tǒng)課程設(shè)計(jì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-01-01
回溯法即是在按條件搜索走不通的情況下退回再選擇其他路線的方法,這里我們來看C語言使用回溯法解旅行售貨員問題與圖的m著色問題的方法示例:2016-07-07
本文主要介紹了CMake中使用vcpkg的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-06-06
基于Windows C++ 應(yīng)用程序通用日志組件的使用詳解
眾所周知，在調(diào)試、跟蹤和執(zhí)行應(yīng)用程序的過程中，程序的日志能為這些工作提供大量有價(jià)值的運(yùn)行信息。因此，程序的日志對應(yīng)用程序的運(yùn)行、維護(hù)至關(guān)重要2013-05-05
C語言qsort函數(shù)用冒泡排序?qū)崿F(xiàn)過程詳解
qsort函數(shù)是由C語言提供的標(biāo)準(zhǔn)庫函數(shù), 它的實(shí)現(xiàn)思想是快速排序。這篇文章主要介紹了C語言中qsort函數(shù)用法及用冒泡排序?qū)崿F(xiàn)qsort函數(shù)功能，需要的可以參考一下2023-02-02
C++實(shí)現(xiàn)strcmp字符串比較的深入探討
本篇文章是對使用C++實(shí)現(xiàn)strcmp字符串比較進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05