手机
当前位置:查字典教程网 >编程开发 >C语言 >c语言 跳台阶问题的解决方法
c语言 跳台阶问题的解决方法
摘要:题目:一个台阶总共有n级,如果一次可以跳1级,也可以跳2级。求总共有多少种跳法,并分析算法的时间复杂度。答:用一个函数f(n)来表示n级台阶...

题目:一个台阶总共有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;

}

运行界面如下:

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

【c语言 跳台阶问题的解决方法】相关文章:

c语言B树深入理解

基于C语言中段错误的问题详解

c++ 一个二进制串转化为整数的解决方法

c语言全局变量和局部变量问题及解决汇总

c语言 汉诺塔算法代码

使用C语言实现CRC校验的方法

c语言:金币阵列的问题

c语言求1+2+...+n的解决方法

使用root权限运行自己所编译程序的解决方法

c语言中十六进制转二进制显示的实现方法

精品推荐
分类导航