【面试题】N阶台阶的走法种数问题(分支思想)

3/3/2017来源:C/C++教程人气:1311

【面试题】N阶台阶的走法种数问题(分支思想)

【面试题】在一些技术面试中,经常会有N阶台阶每次走一步或两步,问有多少种走法的题目,实际上就是斐波那契数列算法,在此本人通过分支思想进行统计方法数。

一、题目重述 总共有100阶台阶,每次走一步或两步,请问共有几种走法? 二、解决方案 可以模拟树分支的思想,通过for循环将每次选择一步或者两步的走法以分支形式分开,并将剩下的阶数(stair - i)作为参数进入递归,当stair为0,即到分支末,统计分支数,即可得方法数。 三、代码实现

#include <iostream> using namespace std; const int Stair = 100; //台阶数 static int num = 0; //统计方法数 void Add_up(int stair){ if (0 == stair || 1 == stair)//当stair为0,表示已到分支末;当stair为1,为避免stair - i出现小于0的情况,在此特意选出来 { num++; return; } for (int i = 1; i <= 2; i++)//每次可选择走一步或两布,根据选择不同划出分支 Add_up(stair - i);//减去所走步数,进入新的递归 } void main() { Add_up(Stair); cout << "共有" << num << "种走法" << endl; }

四、结束语 类似可以走一步或两步或三步的题目,可以参考上述代码修改for循环 i 的最大值和注意(stair - i)的值小于0的情况即可。 希望对大家有帮助。