青少年软件编程(C语言)等级考试试卷(3级)-2021年9月-含参考答案和解析.docx

青少年软件编程（C语言）等级考试试卷（三级）
2021年9月
分数:100.00 题数：5—、编程题 （共5题，共100分）
1. 菲波那契数列
菲波那契数列是指这样的数列：数列的第一个和第二个数都为1,接下来每个数都等于 前面2个数之和。给出一个正整数a,要求菲波那契数列中第a个数对10000取模的结果 是多少。
时间限制：1000内存限制:65536
输入
第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行，包括一个正整 数 a（l <= a <= 1000000）o输出
n行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第a个数对 10000取模得到的结果。
样例输入4
52
191
样例输出5
14181
1
【解析】
> 考数组，通过n初始化数组计算数列时，需要记录前两个数，可用prevl和prev2记录。注意每次循环计算出 新的数current时，要将前一个数prevl保存到prev2中，以避免被覆盖。
/夫少年软件编程（C语言）等级考试试卷（三级）2021年9月-菲波那契数列大/ #include<stdio.h>int main（）｛
int n, i, j; //测试多少次
int prevl, prev2;
int current;〃代表现在的数
scanf（”％cT,&n）;
0
1
2
3
4
5
6
7
8
9

J
J
J
J
J
L
L

J

((((()))))

J
J
J
J
J

L
J
J
J

(((()())))
无左，移到第1个右括号后
J
J
J
J

J
L
J
J
J

(((())()))
无左，移到第1个右括号后
J
J
J
J
L
J
L

J

(((()))())
无左，移到第1个右括号后
L
J
J
L

J
J
J
J
J

(((())))()
无左，移到第1个右括号后
J
J

,L
J
J
J
J
J

((()))(())
有左，移到第1个左括号后
J
J
L
L

1
J

J

((()))()()
无左，移到第1个右括号后
J
J

L
J
L
J

J

(())(())()
有左，移到第1个左括号后
J
J
L
L

L
J

J

(())()(())
有左，移到第1个左括号后
J
J
J
,L
c
L
L

,L
J

(())()()()
无左，移到第1个右括号后
L

J
L

L
JL

()(((())))
递归调用4对括号的
L
L
J
J
J

L

J

()((()()))

J

J

J
,L
J

()((())())

L
,L
L
L
L
,L
J

,L

()((()))()

J

J

J
J
J
J

()(())(())

J
J
J
L
L
J
J
J
J
J

()(())()()

J

J

J
J
c

J
J

()()((()))
递归调用3对括号的
J

J
J
J
J
,L
L
J
L

()()(()())

1
J
J
J

J
J

L

()()(())()

JL
J

c
JL

()()()(())
递归调用2对括号的

J
L

J
c

()()()()()

5.余数相同问题
已知三个正整数a, b, co现有一个大于1的整数x,将其作为除数分别除a, b, c, 得到的余数相同。请问满足上述条件的x的最上值是多少？
时间限制：1000内存限制:65536
输入
—行，三个不大于100000。的正整数a, b, c,两个整数之间用一个空格隔开。
输出
—个整数，即满足条件的x的最小值。
样例输入300 262 205
样例输出19
【解析】
> 送分题，直接从2开始循环试探即可。
/★少年软件编程(C语言)等级考试试卷(三级)2021年9月-余数相同问题玖 #include<stdio.h>#include<stdlib.h>
int main(){
long a,b,c,x;
scanf("%ld %ld %ldH,&a,&b,&c);
for(x=2;x<=a && x< = b && x< 二c;x++){if(a%x= = b%x && b%x==c%x)(break;)
)
printf(”％cT,x);
return 0;}
int arr[n]; //每次测试要输出第几个数的数组
〃循环输入a,保存在数组中。 for(i=0; i<n; i ++){scanf("%d",&arr[i]);
} printfC'\r\n,,)： //先输出新行以分隔输入和输出的数 for(i=0; ivn; i ++){〃刚开始没有前一个数，记为0
prevl 二 0;prev2=0;
〃arr[i]记录了本次测试要输出第a个数的数列的值 for(j=l; j<=arr[i]; j++)(if(j==l || j==2)(
current=l;〃数列的第一个和第二个数都为1} else {
current二prevl+prev2; 〃第3个数开始，数值等于前两个数之和 } prev2=prevl; //将前一个数prevl赋值给前2个数prev2记下 prevl二current;//将当前位置的数赋值给前1个数prevl记下}
printf(,,%d\r\nn,current);
}
return 0;}
2. 广义格雷码
在一组数的编码中，若任意两个相邻(首尾也视为相邻)的代码只有一位二进制数不同， 则称这种编码为格雷码。如四位格雷码：
0000、 0001s 0011. 0010、 0110s Ollis 0101s 0100、 1100s 1101s nils 1110s 1010s 1011. 1001. 1000
现在将格雷码扩展至其他进制，仍然是相邻两个数只能有一位不同。输入两个正整数 n,m分别表示长度和进制，每行输出一个n位m进制数，输出任意一种编码即可。(提示： putchar输出效率更高) 时间限制：1000 内存限制：65536输入
—行，两个整数 n,mo 其中 2 W n W 12 ,2 W m W 10 且 mn W 500000输出
任意一种编码方案，每个编码一行。相邻两个编码相差一位。第一个编码和最后一个编 码算相邻 样例输入2 3
样例输出00
10 2021 01
1112
2202
【解析】
> 明确数制的概念，m进制数即逢m进一位，3进制数中的3就是10。
> 要输出n位m进制数的所有数，如样例的2位3进制数就是3的2次方，即9个, 分别是：
00、 01、 0210、 11、 12
20、 21、 22 3位3进制数就是3的3次方，即9个27个数： 000 001 002010 011 012
020 021 022100 101 102
110 111 112120 121 122
200 201 202210 211 212
220 221 222由于有前导0,所以储存时可用char数组，即保存时要用char-维数组。
> 本题难度最大的地方在于不是单纯的二进制的编码，二进制编码很简单，可以用二 元组变换来完成，如果是三进制则是三元组……复杂度大幅提高。为了适应题目最 多支持到12位10进制数的要求，采用了回溯算法，找到一个符合规则的编码方 案就算成功。
> 其次是数列长度是未知的，而且数量可能很多，不合适事先定义固定长度的数组, 所以需要动态内存分配，对小朋友来说可能不太好理解。
/*少年软件编程(C语言)等级考试试卷(三级)2021年9月-广义格雷码大/ #include<stdio.h>#include<stdlib.h>
#include<math.h>int
char** result = NULL; 〃输出字符串数组 void printCharArr(char** s){
int i=0;
for(i=0;i<t;i ++){puts(s[i]);
//判断s2是否可以放在si后面int canUse(char* si, char* s2){
int i=0, q = 0;
for(i=0;i<n;i ++){if(sl[i]!= s2[i]){q++;}
if(q>l){return 0;) 〃重复的位超过1个直接返回false
)
return q二二1; //有且只有1位不同)
//判断si代表的字符串是否在前面用过了int isUsed(char* si, char** arr, int len){
int i;
for(i=0; i<len; i++){if(sl==arr[i]){return 1;}
}
return 0;}
〃使用回溯算法找到可用的编码方案 char** huiSu(char** arr, char** s, int len){ int i;
〃一开始将第一个数放在试探数组s里
if(len 二二 0){s[0]=arr[0];
len++;
}
//逐个数试探，直到找到t个数，
//并且第0个数可以作为第t个数后面的数时试探成功 for(i=l; i<t; i ++) {char* tmp = s[len-l]; //读取已试探的数组中的最后一个数
char* current = arr[i]; //读取当前要试探的数
if(isUsed(current, s, len)) {continue;} // 当前数已用过则跳过 if(canUse(tmp, current))( //如果当前数可以作为最后一个数后面的数 s[len]二current;〃将当前数加入试探数组len ++;〃已找到的数的数量增加1
if(len==t){ //如果已找到t个数〃首尾的数符合规则，则试探成功，否则失败。
if(canUse(s[len-1],s[0]))(return s;}else(return NULL;)}
result二huiSu(arr,s,len); //递归调用试探下一个数 if(result! = NULL){return result;) //如果有数据返回则代表试探成功 〃否则证明此路不通，用数列的下一个数继续试探 len--;
s[len]=NULL;)
}
return NULL;int main()(
int ij；
〃相当于二维char数组，由于事先不能知道有多少元素，只能用动态内存分配。 char** arr;
char- s; 〃用于试探的数组
scanf("%d %d",&n,&m);
t=pow(mJn); //数列的长度
〃分配内存以保存完整的数列
arr=(char**)calloc(t,sizeof(char*));
int num, mod;
char* numStr;//用于保存数值的字符串
//填充所有n位m进制数
for(i=0;i<t;i ++) {//为字符串分配内存
numStr 二(char*)calloc(n, sizeof(char));
//用取模法将10进制数转化成m进制数 num 二 i;
for(j=0;j<n;j ++){ 〃需要前导0,所以不能是num==0时就退出mod = num % m;
numStr[n-j-l] = mod+48;〃将数字转成字符num /= m;
} arr[i]=numStr;
}
s=(char**)calloc(t,sizeof(char*));
//开始回溯试探
result 二 huiSu(arr,s,O);
if(result! = NULL){printCharArr(result);
)
//释放动态分配的内存
for(i=0;i<t;i ++)(numStr = arr[i];
if(numStr! = NULL){free(numStr);}
}
free(s);
free(arr);
return 0;课程冲突
小A修了 n门课程，第i门课程是从第ai天一直上到第bi天。定义两门课程的冲突程 度为：有几天是这两门课程都要上的。例如al=l,bl=3,a2=2,b2=4时这两门课的冲突程度 为2O现在你需要求的是这n门课中冲突程度最大的两门课的冲突程度。
时间限制:1000内存限制:65536
输入
第一行一个正整数n表示课程数量。接下来n行，每行两个正整数ai,bio 2 W n W 1000, 1 W ai W bi W 1000o输出
输出一个整数表示最大的冲突程度样例输入
33
245 5
样例输出2
【解析】> 这道题还是比较简单的。只需要定义一个表格（二维数组），一行代表一个课程， 列代表第几天，如果某课程某天有课，则在对应的格子里填上1,否则填上。就可 以。这样就得到了如下的课表：（按样例输入的数据）
1
1
1

1
1
1

1
> 然后用三重循环每两行逐个格子进行比较，统计同一列都是1的格子的数量（就是 冲突程度）即可。例如第1行与第2行比较，第1行与第3行比较，第2行与第3 行比较。

A 最后记录并输出冲突程度。
/大少年软件编程(C语言)等级考试试卷(三级)2021年9月一课程冲突大/ #include<stdio.h>#include<stdlib.h>
#include<math.h>int main()(
int n,a,b,ij; scanf(n%d",&n);
int arr[n][1001]; for(i=0;i<n;i ++){for(j=0;j<1001;j ++)( arr[i][j]=O;
}
)
int maxldx = 0; for(i=0;i<n;i ++)( scanf("%d %d",&a,&b); 〃在表格中标出上课时间对应的格子，要上课为1for(j=a;j<=b;j ++){
arr[i][j]=l;}
if(maxldx<b){maxldx=b;}
}
〃将表格中的行两两进行比较，看有多少格子都是1的，表示冲突程度。 int maxCount=0, count=0; //最大冲突数和用于临时保存本次比较的冲突数 for(i 二 0;i<n;i ++){for(j=i+l；j<n;j++)(
count 二 0;for(a=0;a<=maxldx;a++){
if(arr[i][a]==l && arr|j][a]==l){count ++;}}
//如果本次比较的冲突程度大于已记录的最大冲突程度，则记录下来。 if(maxCount<count){maxCount=count;})
}
printf("%d",maxCount);
return 0;生成括号
Paul是一名数学专业的同学，在课余选修了 C++编程课，现在他能够自己写程序判断 判断一个给定的由(和组成的字符串是否是正确匹配的。可是他不满足于此，想反其道而 行之，设计一个程序，能够生成所有合法的括号组合，请你帮助他解决这个问题。
时间限制:1000 内存限制:65536 输入
输入只有一行N,代表生成括号的对数(1 W N W 10)o输出
输出所有可能的并且有效的括号组合，按照字典序进行排列，每个组合占一行。
样例输入3
样例输出((()))
(00)(0)0
0(0)00()
【解析】＞本题的麻烦在于要按字典序进行排列。做法有二:一是先穷举所有组合，然后排序; 二是找规律后用字符移位的方法逐一输出。
> 穷举再排序的方案要动态创建二维字符数，字符移位则只需要一个一维字符数组即 可，相对简单。
> 原理是先生成指定数量的嵌套括号对，放在数组里。
> 然后找到最里层的括号对，接着寻找其后面的左括号，找到则将括号对后面的字符 左侧，将括号对插入到所找到的左括号的位置。
> 然后在移动的括号对之前寻找最右侧的第一个括号对，重复上述操作。
> 如果未找到左括号，则找右括号，找到后右移，直到移到最后面。
> 关键：最左侧出现新的成对的括号时，从括号后面重新生成数量-1的嵌套括号对， 放在数组里。然后递归调用，直到数组变成“（）（）（）”的形式。
/大少年软件编程(C语言)等级考试试卷(三级)2021年9月一生成括号大/#include<stdio.h>
#include<stdlib.h>#include<math.h>
//在数组arr中从begin位置开始寻找c字符出现的最小位置，找不到返回-1。 int findFirst(char arr|], char c, int begin){
int i 二 begin;
char t;
do{t=arr[i];
if(t==c)(return i;}i + + ；
)while(t! = '\0');
return -1;}
void genBrackets(char arr[], int begin, int len){
int pos, insPos, i,n;
puts(arr);
if(begin==len-2){ return;} // 处理完了
// arr[begin] =='C && arr[begin+l]==y 代表左侧出现括号对 while(!(arr[begin]=='(' && arr[begin+l]==')'))(
//从最中间到最左侧依次找括号对的位置，poa是左括号的位置 pos=findFirst(arr,')*,begin)-1;
while(pos<len-2){
//寻找括号对后面第1个左括号的位置 insPos=findFirst(arr,'(',pos+2);if(insPos>=0)(
//找到则将括号对移到左括号的后面 for(i=pos;i<insPos;i++){arr[i]=arr[i+2];
)arr[insPos-l]='(';
arr[insPos]=y；//最左侧出现新括号对则跳出循环 if((arr[begin]= = '(' && arr[begin+l]==')'))( break;} puts(arr);
pos=insPos-l;) else {
//寻找括号对后面第1个右括号的位置 insPos=findFirst(arr,,)',pos+2);if(insPos>=0){
//找到则将括号对移到右括号的后面 for(i=pos;i<insPos;i++){arr[i]=arr[i+2];
}
arr[insPos-l]='('； arr[insPos]=')';
if((arr[begin]=='(, && arr[begin + l]=='),)){ break;) puts(arr);
pos=insPos-l;}
})
}
〃n为右侧未处理的括号对的数量，4, 3, 2……
//此时begin和begin+1已是一对括号，所以要-2排除掉 n=(len-begin-2)/2;
〃重新生成括号对,生成结果例如:()((()))、()()(())这样 for(i=0;i<n;i++)(arr[begin+i+2]='(,； arr[begin+i+2+n]二')'；
}
〃递归处理剩余的字符串 genBrackets(arr, begin+2, len);}
int main()(
int n, len, i;
scanf("%d",&n);
// 10对括号最多20个字符，多加一位作为字符串结束符号。
char arr[21];
len 二 n *2;
//生成((()))这样的字符串
for(i=0;i<n;i ++)(arr[i]='C； arr[i+n]=')';
) arr[n*2]=,\0,;
genBrackets(arr,O,len);
return 0;}
推导过程：