青少年软件编程(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 考数组，通过n初始化数组计算数列时，需要记录前两个数，可用prevl和prev2记录。注意每次循环计算出 新的数current时，要将前一个数prevl保存到prev2中，以避免被覆盖。/夫少年软件编程（C语言）等级考试试卷（三级）2021年9月-菲波那契数列大/ #includeint main（）int n, i, j; /测试多少次int prevl, prev2;int current;代表现在的数scanf（”cT,&n）;0123456789JJJJJLLJ()JJJJJLJJJ()()无左，移到第1个右括号后JJJJJLJJJ()()无左，移到第1个右括号后JJJJLJLJ()()无左，移到第1个右括号后LJJLJJJJJ()()无左，移到第1个右括号后JJ,LJJJJJ()()有左，移到第1个左括号后JJLL1JJ()()()无左，移到第1个右括号后JJLJLJJ()()()有左，移到第1个左括号后JJLLLJJ()()()有左，移到第1个左括号后JJJ,LcLL,LJ()()()()无左，移到第1个右括号后LJLLJL()()递归调用4对括号的LLJJJLJ()()()JJJ,LJ()()()L,LLLL,LJ,L()()()JJJJJJ()()()JJJLLJJJJJ()()()()JJJJcJJ()()()递归调用3对括号的JJJJJ,LLJL()()()()1JJJJJL()()()()JLJcJL()()()()递归调用2对括号的JLJc()()()()()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#includeint 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 arrn; /每次测试要输出第几个数的数组循环输入a,保存在数组中。 for(i=0; in; i +)scanf(%d,&arri); printfCrn,)： /先输出新行以分隔输入和输出的数 for(i=0; ivn; i +)刚开始没有前一个数，记为0prevl 二 0;prev2=0;arri记录了本次测试要输出第a个数的数列的值 for(j=l; j 明确数制的概念，m进制数即逢m进一位，3进制数中的3就是10。 要输出n位m进制数的所有数，如样例的2位3进制数就是3的2次方，即9个, 分别是：00、 01、 0210、 11、 1220、 21、 22 3位3进制数就是3的3次方，即9个27个数： 000 001 002010 011 012020 021 022100 101 102110 111 112120 121 122200 201 202210 211 212220 221 222由于有前导0,所以储存时可用char数组，即保存时要用char-维数组。 本题难度最大的地方在于不是单纯的二进制的编码，二进制编码很简单，可以用二 元组变换来完成，如果是三进制则是三元组复杂度大幅提高。为了适应题目最 多支持到12位10进制数的要求，采用了回溯算法，找到一个符合规则的编码方 案就算成功。 其次是数列长度是未知的，而且数量可能很多，不合适事先定义固定长度的数组, 所以需要动态内存分配，对小朋友来说可能不太好理解。/*少年软件编程(C语言)等级考试试卷(三级)2021年9月-广义格雷码大/ #include#include#includeintchar* result = NULL; 输出字符串数组 void printCharArr(char* s)int i=0;for(i=0;it;i +)puts(si);/判断s2是否可以放在si后面int canUse(char* si, char* s2)int i=0, q = 0;for(i=0;il)return 0;) 重复的位超过1个直接返回false)return q二二1; /有且只有1位不同)/判断si代表的字符串是否在前面用过了int isUsed(char* si, char* arr, int len)int i;for(i=0; ilen; i+)if(sl=arri)return 1;return 0;使用回溯算法找到可用的编码方案 char* huiSu(char* arr, char* s, int len) int i;一开始将第一个数放在试探数组s里if(len 二二 0)s0=arr0;len+;/逐个数试探，直到找到t个数，/并且第0个数可以作为第t个数后面的数时试探成功 for(i=l; it; i +) char* tmp = slen-l; /读取已试探的数组中的最后一个数char* current = arri; /读取当前要试探的数if(isUsed(current, s, len) continue; / 当前数已用过则跳过 if(canUse(tmp, current)( /如果当前数可以作为最后一个数后面的数 slen二current;将当前数加入试探数组len +;已找到的数的数量增加1if(len=t) /如果已找到t个数首尾的数符合规则，则试探成功，否则失败。if(canUse(slen-1,s0)(return s;else(return NULL;)result二huiSu(arr,s,len); /递归调用试探下一个数 if(result! = NULL)return result;) /如果有数据返回则代表试探成功 否则证明此路不通，用数列的下一个数继续试探 len-;slen=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;it;i +) /为字符串分配内存numStr 二(char*)calloc(n, sizeof(char);/用取模法将10进制数转化成m进制数 num 二 i;for(j=0;jn;j +) 需要前导0,所以不能是num=0时就退出mod = num % m;numStrn-j-l = mod+48;将数字转成字符num /= m; arri=numStr;s=(char*)calloc(t,sizeof(char*);/开始回溯试探result 二 huiSu(arr,s,O);if(result! = NULL)printCharArr(result);)/释放动态分配的内存for(i=0;i 这道题还是比较简单的。只需要定义一个表格（二维数组），一行代表一个课程， 列代表第几天，如果某课程某天有课，则在对应的格子里填上1,否则填上。就可 以。这样就得到了如下的课表：（按样例输入的数据）1111111 然后用三重循环每两行逐个格子进行比较，统计同一列都是1的格子的数量（就是 冲突程度）即可。例如第1行与第2行比较，第1行与第3行比较，第2行与第3 行比较。A 最后记录并输出冲突程度。/大少年软件编程(C语言)等级考试试卷(三级)2021年9月一课程冲突大/ #include#include#includeint main()(int n,a,b,ij; scanf(n%d,&n);int arrn1001; for(i=0;in;i +)for(j=0;j1001;j +)( arrij=O;)int maxldx = 0; for(i=0;in;i +)( scanf(%d %d,&a,&b); 在表格中标出上课时间对应的格子，要上课为1for(j=a;j=b;j +)arrij=l;if(maxldxb)maxldx=b;将表格中的行两两进行比较，看有多少格子都是1的，表示冲突程度。 int maxCount=0, count=0; /最大冲突数和用于临时保存本次比较的冲突数 for(i 二 0;in;i +)for(j=i+l；jn;j+)(count 二 0;for(a=0;a=maxldx;a+)if(arria=l & arr|ja=l)count +;/如果本次比较的冲突程度大于已记录的最大冲突程度，则记录下来。 if(maxCount 穷举再排序的方案要动态创建二维字符数，字符移位则只需要一个一维字符数组即 可，相对简单。 原理是先生成指定数量的嵌套括号对，放在数组里。 然后找到最里层的括号对，接着寻找其后面的左括号，找到则将括号对后面的字符 左侧，将括号对插入到所找到的左括号的位置。 然后在移动的括号对之前寻找最右侧的第一个括号对，重复上述操作。 如果未找到左括号，则找右括号，找到后右移，直到移到最后面。 关键：最左侧出现新的成对的括号时，从括号后面重新生成数量-1的嵌套括号对， 放在数组里。然后递归调用，直到数组变成“（）（）（）”的形式。/大少年软件编程(C语言)等级考试试卷(三级)2021年9月一生成括号大/#include#include#include/在数组arr中从begin位置开始寻找c字符出现的最小位置，找不到返回-1。 int findFirst(char arr|, char c, int begin)int i 二 begin;char t;dot=arri;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; / 处理完了/ arrbegin =C & arrbegin+l=y 代表左侧出现括号对 while(!(arrbegin=( & arrbegin+l=)(/从最中间到最左侧依次找括号对的位置，poa是左括号的位置 pos=findFirst(arr,)*,begin)-1;while(pos=0)(/找到则将括号对移到左括号的后面 for(i=pos;i=0)/找到则将括号对移到右括号的后面 for(i=pos;iinsPos;i+)arri=arri+2;arrinsPos-l=(； arrinsPos=);if(arrbegin=(, & arrbegin + l=),) break;) puts(arr);pos=insPos-l;)n为右侧未处理的括号对的数量，4, 3, 2/此时begin和begin+1已是一对括号，所以要-2排除掉 n=(len-begin-2)/2;重新生成括号对,生成结果例如:()()、()()()这样 for(i=0;in;i+)(arrbegin+i+2=(,； arrbegin+i+2+n二)；递归处理剩余的字符串 genBrackets(arr, begin+2, len);int main()(int n, len, i;scanf(%d,&n);/ 10对括号最多20个字符，多加一位作为字符串结束符号。char arr21;len 二 n *2;/生成()这样的字符串for(i=0;in;i +)(arri=C； arri+n=);) arrn*2=,0,;genBrackets(arr,O,len);return 0;推导过程：