题目
题目标题: 第39级台阶
小明刚刚看完电影《第39级台阶》，离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级!
站在台阶前，他突然又想着一个问题：
如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多少种不同的上法呢？
请你利用计算机的优势，帮助小明寻找答案。
要求提交的是一个整数。
注意：不要提交解答过程，或其它的辅助说明文字。
题目分析
本题的正确答案是:
51167078
这里涉及递归, 斐波那契数列和动态规划, 可以使用深度优先搜索 (DFS) 的思想解决问题.
首先说一下深度优先搜索. 深搜的原则就是对每一个可能的路径都深入访问直到不能继续深入访问为止, 而且每个节点只访问一次. 深搜的应用条件是上一步的走法和下一步的走法的规则是一样的且该问题具备边界以结束深搜.
首先可以简化一下这个问题, 去掉题目中要求的”走偶数步”的限制. 之后, 剩下的问题就是每次上一个或者两个台阶, 一共有多少种走法, 第一步有两种可能(走一个台阶或者走两个台阶), 随后的每走过一步的下一步也都是有两种走法(走一个台阶或者走两个台阶).
假设函数 f(n) 可以计算在上面的条件下走完 n 阶台阶会有多少种走法, 则:
走完 1 个台阶之后 (走了 1 步), 剩余的走法有 f(n-1) 种;
走完 2 个台阶之后 (走了 1 步), 剩余的走法有 f(n-2) 种.
结束条件有两个, 一个是恰好走完了 39 个台阶, 另一个是走到了第 40 个台阶(正着走的情况下, 只剩下一个台阶时却迈了两步)或者走到了第 -1 个台阶(倒着走的情况下, 只剩下一个台阶的时候却迈了两步).
正着走: 可以认为是从楼梯下面往上面走;
倒着走: 可以认为是从楼梯上面往下面走;
正着走和倒着走的效果是一样的 (例如当”楼梯”是水平的”斑马线”的时候).
使用递归实现深搜的函数大致形式如下:
递归函数f(...){
if(...){ //本层递归函数结束条件 1
/* code */
}else if (...) { //本层递归函数结束条件 2
/* code */
}else{
递归函数f(...)//可能的步骤 1
递归函数f(...)//可能的步骤 2
}
}
在具体使用递归解决深搜问题的时候, 不同的思路和方法的最终实现方式会有些差别, 具体情况可以参考如下 4 个程序 (每个程序都可以独立解决”第39级台阶”这个问题).
程序 1 如下:
#include<iostream>
#include<stdio.h>
using namespace std;
int ans; //用于保存所有可能的走法
void f(int n, int step){//n: 剩下的阶梯数, step: 已走的步数
/*剩下的台阶数是负数 (如果最后只剩下一个台阶却走了两步
会导致产生剩下负数个台阶的情况), 这是不可能发生的,
因此退出 f() 函数.*/
if(n<0){//判断边界条件, 函数出口 1
return;
/*在 void 函数中使用"return"可以出发函数的强制结束,
类似于循环结构中的 "break", 在这里"return"用于退出
本层深度遍历, 回到上一个未被遍历的节点继续之后的深度遍历.
*/
}
if(n==0&&step%2==0){//判断边界条件, 函数出口 2
ans++;
return;
}
/*尝试每一种可能的结果("n-1"和"n-2")并触发
下一步的递归操作 ("n-1,step+1"和"n-2,step+1")
*/
f(n-1,step+1); //下一步可能的走法 1
f(n-2,step+1); //下一步可能的走法 2
}
int main(){
f(39,0);
cout << ans << endl;
return 0;
}
上面的程序是倒着计算(倒着走楼梯)的, 也可以按照正着计算(正着走楼梯)的方法写程序, 程序 2 如下:
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int sum=0;
void f(int n, int step){
if(n==39&&step%2==0){
sum++;
return;
}
if(n>39){
return;
}
f(n+1,step+1);
f(n+2,step+1);
}
int main(){
f(0,0);
cout<<sum<<endl;
return 0;
}
为了使逻辑上更清晰一些, 可以对上面的程序 2 做以下修改, 修改后得到的程序 3 如下:
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int sum=0;
void f(int n, int step){
if(n==39&&step%2==0){
sum++;
return;
}else if(n>39){
return;
}else{
f(n+1,step+1);
f(n+2,step+1);
}
}
int main(){
f(0,0);
cout<<sum<<endl;
return 0;
}
当然, 递归函数除了可以使用没有返回值的 “void f()” 来定义, 也可以使用有返回值的”int f()”来定义, 例如程序 4:
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int sum=0;
int f(int n, int step){
if(n==39&&step%2==0){
sum++;
return sum;
}else if(n>39){
return -1;
}else{
f(n+1,step+1);
f(n+2,step+1);
return 0;
}
}
int main(){
f(0,0);
cout<<sum<<endl;
return 0;
}