c语言 跳台阶问题的解决方法

时间:2021-05-20

题目:一个台阶总共有n级,如果一次可以跳1级,也可以跳2级。求总共有多少种跳法,并分析算法的时间复杂度。
答:用一个函数f(n)来表示n级台阶总的跳法。
1、只有1个台阶,则f(1) = 1;
2、有2个台阶,则f(2) = 2;
3、当有n个台阶时,如果第一次跳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;
//循环
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;
}

运行界面如下:

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章