蓝桥杯-振兴中华三种解题方法（C语言）

朴灿烈づ我的快乐病毒、 2022-03-31 14:46 302阅读 0赞

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

#include<stdio.h>
    int count=0;
    void road(int row,int col,int arr[][5])
    {
    	if(arr[row][col]==7)//从0开始跳到7则为一条完整路线 
    	{
    		count++;
    	}
    	if(col+1<5&&arr[row][col+1]==arr[row][col]+1)//横向走 
    	{
    		road(row,col+1,arr);
    	}
    	if(row+1<4&&arr[row+1][col]==arr[row][col]+1)//纵向走 
    	{
    		road(row+1,col,arr);
    	}
    }
    int main()
    {
    	int arr[4][5]={
    	            {0,1,2,3,4},
    	            {1,2,3,4,5},
    			    {2,3,4,5,6},
    			    {3,4,5,6,7}};
    	road(0,0,arr);
    	printf("%d",count);
    	return 0;			   
    }

**做法二代码如下：**

#include<stdio.h>
    int fun(int row,int col)
    {
    	if(row==0||col==0){
    		return 1;
    	}else{
    		return fun(row-1,col)+fun(row,col-1);
    	}	
    }
    int main()
    {
    	int count=fun(3,4);
    	printf("%d",count);
    	return 0;
    }

**做法三代码如下：**

#include<stdio.h>
    int main()
    {
    	int arr[4][5];
    	int i,j;
    	for(i=0;i<4;i++)
    	{
    		arr[i][0]=1;
    	}
    	for(j=0;j<5;j++)
    	{
    		arr[0][j]=1;
    	}
    	for(i=1;i<4;i++)
    	for(j=1;j<5;j++)
    	{
    		arr[i][j]=arr[i][j-1]+arr[i-1][j];
    	}
    	printf("%d",arr[3][4]);
    	return 0;
    }

[20190103170251400.png]: /images/20220331/74f0bbf75ea84558bcb52cbaa3a66447.png