[蓝桥省题](C2013_3) 振兴中华
3、(振兴中华)小明参加了学习的趣味运动会,其中一个项目是:跳格子。地上画着一些格子,每个格子里写一个字,如下所示:
比赛时,先站在左上角的写着“从”字的格子里,可以横向或纵向跳到相邻的格子里,但不能跳到对角的格子或其他位置,一直要跳到“华”字结束
要求跳过的路线刚好构成"从我做起,振兴中华"这句话
请你帮助小明算一算他一共有多少种可能的跳跃路线呢?
答案是一个整数,请通过浏览器提交该数字,注意:不要提交解答过程,或其他辅助说明类的内容
题意:上述图案是一个矩阵,我们可以对应的看作一个二维数组,通过坐标的变化我们要求坐标序列构成“从我做起,振兴中华”题目要求算出所有达到要求的坐标序列。起始是(0,0)终点是(3,4)
思路:我们可以从图上得知,每个格子的方向只有<向右>和<向下>两种可能,通过这两个方向所走的路线之和就是所有路线总和,在"0,0"的位置和其余所有位置的选择都是一样的,如下图所示:
例如:在“从”的位置的位置选择和在“做的位置”的选择是一样的
那么结束条件就是达到“华”的位置即是一种走法,也就是说,每个位置不管向左还是向下,只要能达到"华"就是一种解法,则我们可以用递归将问题缩小求解
代码如下所示:
int f(int x, int y)//每层变化的就是坐标
{
if (x == 3 && y == 4)//如果x和y等于(3,4)则达到结束条件
return 1;
if (x == 3 && y != 4)
return f(x, y + 1);
else if (x != 3 && y == 4)
return f(x + 1, y);
else
return f(x + 1, y) + f(x, y + 1);
}
int main()
{
int result = f(0, 0);
printf("%d", result);
system("pause");
return 0;
}
根据思路我们可以画出它的树型图并与理解:
这题其实还能用排列组合来做,一共是七个位置(从开始包括从需要减一)其中三种向下,其他全部向右,这个序列的总和就是题目答案
C73=7x6x5/1x2x3=35
教学视频如下: