[蓝桥省题](C2013_3) 振兴中华

3、(振兴中华)小明参加了学习的趣味运动会,其中一个项目是:跳格子。地上画着一些格子,每个格子里写一个字,如下所示:

img

比赛时,先站在左上角的写着“从”字的格子里,可以横向或纵向跳到相邻的格子里,但不能跳到对角的格子或其他位置,一直要跳到“华”字结束

要求跳过的路线刚好构成"从我做起,振兴中华"这句话

请你帮助小明算一算他一共有多少种可能的跳跃路线呢?

答案是一个整数,请通过浏览器提交该数字,注意:不要提交解答过程,或其他辅助说明类的内容

题意:上述图案是一个矩阵,我们可以对应的看作一个二维数组,通过坐标的变化我们要求坐标序列构成“从我做起,振兴中华”题目要求算出所有达到要求的坐标序列。起始是(0,0)终点是(3,4)

思路:我们可以从图上得知,每个格子的方向只有<向右>和<向下>两种可能,通过这两个方向所走的路线之和就是所有路线总和,在"0,0"的位置和其余所有位置的选择都是一样的,如下图所示:

img例如:在“从”的位置的位置选择和在“做的位置”的选择是一样的

那么结束条件就是达到“华”的位置即是一种走法,也就是说,每个位置不管向左还是向下,只要能达到"华"就是一种解法,则我们可以用递归将问题缩小求解

代码如下所示:

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;
}

根据思路我们可以画出它的树型图并与理解:

img

这题其实还能用排列组合来做,一共是七个位置(从开始包括从需要减一)其中三种向下,其他全部向右,这个序列的总和就是题目答案

C73=7x6x5/1x2x3=35

教学视频如下:

<video controls="" src="https://axuannote-1304271763.cos.ap-nanjing.myqcloud.com/%E8%93%9D%E6%A1%A52013_3.mp4";></video>

本文链接:

https://nullcode.fun/92.html
1 + 7 =
快来做第一个评论的人吧~