青少年软件编程（C语言）等级考试试卷（四级）2021年12月网站首页 技术杂谈

青少年软件编程（C语言）等级考试试卷（四级）2021年12月

No0d1es 2023-06-20 20:00:03

简介青少年软件编程（C语言）等级考试试卷（四级）2021年12月

青少年软件编程（C语言）等级考试试卷（四级）2021年12月

1.移动路线
题目描述
桌子上有一个m行n列的方格矩阵，将每个方格用坐标表示，行坐标从下到上依次递增，列坐标从左至右依次递增，左下角方格的坐标为(1,1)，则右上角方格的坐标为(m,n)。
小明是个调皮的孩子，一天他捉来一只蚂蚁，不小心把蚂蚁的右脚弄伤了，于是蚂蚁只能向上或向右移动。小明把这只蚂蚁放在左下角的方格中，蚂蚁从左下角的方格中移动到右上角的方格中，每步移动一个方格。蚂蚁始终在方格矩阵内移动，请计算出不同的移动路线的数目。
对于1行1列的方格矩阵，蚂蚁原地移动，移动路线数为1；对于1行2列（或2行1列）的方格矩阵，蚂蚁只需一次向右（或向上）移动，移动路线数也为1……对于一个2行3列的方格矩阵，如下图所示：

蚂蚁一共有3种移动路线：
路线1：(1,1) - (1,2) - (1,3) - (2,3)
路线2：(1,1) - (1,2) - (2,2) - (2,3)
路线3：(1,1) - (2,1) - (2,2) - (2,3)
输入描述
输入只有一行，包括两个整数m和n（0 < m+n ≤ 20），代表方格矩阵的行数和列数，m、n之间用空格隔开。
输出描述
输出若干行，每行一个移动路线，输出形式如样例所示。
（为保证输出一致，蚂蚁移动时先向右，再向上）
输入
2 3
输出
蚂蚁共有3种移动路线：
路线1：(1,1) - (1,2) - (1,3) - (2,3)
路线2：(1,1) - (1,2) - (2,2) - (2,3)
路线3：(1,1) - (2,1) - (2,2) - (2,3)
————————————————
#include<iostream>
#include<cstdio>
using namespace std;
const int N=40;
const int dx[2]={0,1};
const int dy[2]={1,0};
int n,m,ans=0;
bool flag=false;
struct node{
   int x;
   int y;
}st[N*N],tu[N*N][N*N];
int a[N*N];
bool ran_out(int x,int y){
   return x<1||x>n||y<1||y>m;
}
void fuzhi(int step){
   ans++;
   a[ans]=step;
flag=true;
   for(int i=0;i<=step;i++){
       tu[ans][i].x=st[i].x;
       tu[ans][i].y=st[i].y;
   }
}
void dfs(int x,int y,int step){
   st[step].x=x;
   st[step].y=y;
   if(x==n&&y==m){
       fuzhi(step);
       return;
   }
   for(int i=0;i<2;i++){
       int xx=x+dx[i];
       int yy=y+dy[i];
       if(!ran_out(xx,yy)){
           dfs(xx,yy,step+1);
       }
   }
}
int main(){
   std::ios::sync_with_stdio(false);
   cin>>n>>m;
   dfs(1,1,0);
   printf("蚂蚁共有%d种移动路线： ",ans);
   for(int i=1;i<=ans;i++){
       printf("路线%d：",i);
       bool ff=false;
       for(int j=0;j<=a[i];j++){
           if(!ff){
               printf("(%d,%d)",tu[i][j].x,tu[i][j].y);
               ff=true;
           }else{
               printf(" - (%d,%d)",tu[i][j].x,tu[i][j].y);
           }
       }
       printf(" ");
   }
   return 0;
}

2.移动办公
题目描述
假设你经营着一家公司，公司在北京和南京各有一个办公地点。公司只有你一个人，所以你只能每月选择在一个城市办公。在第i个月，如果你在北京办公，你能获得Pi的营业额，如果你在南京办公，你能获得Ni的营业额。但是，如果你某个月在一个城市办公，下个月在另一个城市办公，你需要支付M的交通费。那么，该怎样规划你的行程（可在任何一个城市开始），才能使得总收入（总营业额减去总交通费）最大？
输入
输入的第一行有两个整数T（1 <= T <= 100）和M（1 <= M <= 100），T代表总共的月数，M代表交通费。接下来的T行每行包括两个在1到100之间（包括1和100）的的整数，分别表示某个月在北京和在南京办公获得的营业额。
输出
输出只包括一行，这一行只包含一个整数，表示可以获得的最大总收入。
样例输入
4 3
10 9
2 8
9 5
8 2
1
2
3
4
5
样例输出
31