蓝桥杯-2013省赛-振兴中华

振兴中华"/>

蓝桥杯-2013省赛-振兴中华

蓝桥杯-2013省赛-振兴中华

题目描述

标题: 振兴中华

小明参加了学校的趣味运动会，其中的一个项目是：跳格子。地上画着一些格子，每个格子里写一个字，如下所示：（也可参见p1.jpg）从我做起振
我做起振兴
做起振兴中
起振兴中华比赛时，先站在左上角的写着“从”字的格子里，可以横向或纵向跳到相邻的格子里，但不能跳到对角的格子或其它位置。一直要跳到“华”字结束。
要求跳过的路线刚好构成“从我做起振兴中华”这句话。请你帮助小明算一算他一共有多少种可能的跳跃路线呢？

答案是一个整数，请通过浏览器直接提交该数字。
注意：不要提交解答过程，或其它辅助说明类的内容。

/*思考：从左上角走到右下角一共有多少种走法？其中又有多少符合要求呢？

• 枚举所有的走法，枚举有两种方法：
• 1.迭代
• 2.递归*/

思路解析

除去华字，考虑，其他字只有两种走法，向右走或者向下走，利用递归 的思想：

终止条件为：走到华字，返回1（代表这是一条路线）；走出格子范围，返回0（代表这条路线不通）

// 2013-t3-振兴中华#include<iostream>
using namespace std;// 递归走格子
int f(int x, int y) {if (x == 3 && y == 4) // 走到华字return 1;if (x > 3 || y > 4)  // 越过边界return 0;return f(x + 1, y) + f(x, y + 1);    
}int main() {cout << f(0, 0) << endl;return 0;
}

• 上述的写法可以继续改进：

除华字外，边界上的字要走到华字，下一步只有一种走法，且有且仅有一条路线走到华字；而非边界上的字，下一步有两种走法，因此代码可以改写为：

// 2013-t3-振兴中华#include<iostream>
using namespace std;// 递归走格子
int f(int x, int y) {if (x == 3 || y == 4) // 走到边界return 1;return f(x + 1, y) + f(x, y + 1);    
}int main() {cout << f(0, 0) << endl;return 0;
}

答案：35