搜索
第1/20页2011年决赛c本科考生须知：考试时间为5小时。本试卷包含两种题型：“代码填空”与“程序设计”。总计100分。其中代码填空：9+14=23分程序设计：19+28+30=77分填空题要求参赛选手在弄清给定代码工作原理的基础上填写缺失的部分，使得程序逻辑正确、完整。所填写的代码不超过一条语句（即不能出现分号）。把填空的答案（仅填空处的答案，不包括题面）存入考生文件夹下对应题号的“解答.txt”中即可。编程题要求选手设计的程序对于给定的输入能给出正确的输出结果。考生的程序只有能运行出正确结果的时候才有机会得分。注意：在评卷时使用的输入数据与试卷中给出的实例数据可能是不同的。选手的程序必须是通用的，不能只对试卷中给定的数据有效。对每个题目，要求考生把所有函数写在一个文件中。调试好后，存入与考生文件夹下对应题号的“解答.txt”中即可。相关的工程文件不要拷入。对于编程题目，要求选手给出的解答完全符合ANSIC标准，不能使用c++特性；不能使用诸如绘图、中断调用等硬件相关或操作系统相关的API。1.代码填空（满分9分）题目在考生文件夹下对应题号的“题目.rar”中，请先解压该文件。解压密码以现场公布为准。仔细阅读和调试题目提供的源代码，根据要求填写缺失的代码部分。注意：请把填空的答案（仅填空处的答案，不包括题面）存入考生文件夹下对应题号的“解答.txt”中即可。直接写在题面中不能得分。数论中有著名的四方定理：所有自然数至多只要用四个数的平方和就可以表示。我们可以通过计算机验证其在有限范围的正确性。对于大数，简单的循环嵌套是不适宜的。下面的代码给出了一种分解方案。请仔细阅读，填写空缺的代码（下划线部分）。注意：请把填空的答案（仅填空处的答案，不包括题面）存入考生文件夹下对应题号的“解答.txt”中即可。直接写在题面中不能得分。intf(intn,inta[],intidx){if(______________)return1;//填空1第2/20页if(idx==4)return0;for(inti=(int)sqrt(n);i=1;i--){a[idx]=i;if(_______________________)return1;//填空2}return0;}intmain(intargc,char*argv[]){for(;;){intnumber;printf(输入整数(1~10亿)：);scanf(%d,&number);inta[]={0,0,0,0};intr=f(number,a,0);printf(%d:%d%d%d%d\n,r,a[0],a[1],a[2],a[3]);}return0;}本题满分：9分填空1:(3分)n==0或者：0==n填空2:(6分)f(n-i*i,a,idx+1)或者：f(n-i*i,a,idx+1)0f(n-i*i,a,idx+1)==12.代码填空（满分14分）第3/20页题目在考生文件夹下对应题号的“题目.rar”中，请先解压该文件。解压密码以现场公布为准。仔细阅读和调试题目提供的源代码，根据要求填写缺失的代码部分。在对文本进行简单加密的时候，可以选择用一个n位的二进制数，对原文进行异或运算。解密的方法就是再执行一次同样的操作。加密过程中n位二进制数会循环使用。并且其长度也可能不是8的整数倍。下面的代码演示了如何实现该功能。请仔细阅读，填写空缺的代码（下划线部分）。voidf(char*buf,unsignedchar*uckey,intn){inti;for(i=0;in;i++)buf[i]=buf[i]^uckey[i];//异或运算，即：buf[i]^=uckey[i]}intmain(intargc,char*argv[]){charp[]=abcd中国人123;//待加密串char*key=11001100010001110;//以串的形式表达的密匙，运算时要转换为按位存储的形式。intnp=strlen(p);intnk=strlen(key);unsignedchar*uckey=(unsignedchar*)malloc(np);//unsignedchar是无符号字节型，char类型变量的大小通常为1个字节（1字节=8个位）//密匙串需要按位的形式循环拼入uckey中inti;for(i=0;inp*8;i++){if(key[i%nk]=='1')___uckey[i/8]|=(unsignedchar)0x80(i%8)___;//填空1按位或else___uckey[i/8]&=~((unsignedchar)0x80(i%8))___;//填空2按位与}f(p,uckey,strlen(p));f(p,uckey,strlen(p));第4/20页printf(%s\n,p);free(uckey);return0;}本题满分：14分填空1：(7分)uckey[i/8]|=(unsignedchar)0x80(i%8);//表示右移位，位逻辑运算符：&按位与，|按位或，^按位异或，~取反，移位运算符：左移，右移从数学上看，左移1位等于乘以2，右移1位等于除以2，然后再取整，移位溢出的丢弃填空2：(7分)uckey[i/8]&=~((unsignedchar)0x80(i%8));注意所有逻辑等价形式都是正确的答案，比如可以使用左移位：(unsignedchar)0x802等价于：0x0153.程序设计（满分19分）为什么1小时有60分钟，而不是100分钟呢？这是历史上的习惯导致。但也并非纯粹的偶然：60是个优秀的数字，它的因子比较多。事实上，它是1至6的每个数字的倍数。即1,2,3,4,5,6都是可以除尽60。我们希望寻找到能除尽1至n的的每个数字的最小整数。不要小看这个数字，它可能十分大，比如n=100,则该数为：69720375229712477164533808935312303556800请编写程序，实现对用户输入的n（n100）求出1~n的最小公倍数。例如：用户输入：6程序输出：60用户输入：10程序输出：2520第5/20页要求考生把所有函数写在一个文件中。调试好后，存入与考生文件夹下对应题号的“解答.txt”中即可。相关的工程文件不要拷入。对于编程题目，要求选手给出的解答完全符合ANSIC标准，不能使用c++特性；不能使用诸如绘图、中断调用等硬件相关或操作系统相关的API。解答：最小公倍数就是所有质数的相应幂的积比如N=10小于10的质数有2,3,5,7对应的最大幂是：3，2，1，1则最小公倍数是：2^3x3^2x5^1x7^1=2520#includeiostream#includecstring#includecmathusingnamespacestd;inta[50]={0};//存素数boolvis[100];intb[50]={0};//存幂次voidinit_prim()//求小于100的所有素数存入数组a{inti,j,k;intm=(int)(sqrt(100.0)+0.5);memset(vis,0,sizeof(vis));vis[0]=1;vis[1]=1;//必须加上,否则第一个素数别认为是1for(i=2;i=m;i++)if(!vis[i]){for(j=2*i;j=100;j+=i)vis[j]=1;}intt=0;for(k=0;k100;k++)if(!vis[k])a[t++]=k;}intmain(){inti,j,k;第6/20页init_prim();intn;//2^6=64,2^7=128;由于n最大100，幂次最大6//for(i=0;i100;i++)//素数没问题//if(!vis[i])//coutiendl;//while(1);while(cinn){memset(b,0,sizeof(b));for(i=0;i=n&&a[i]=n;i++)//”1到n素数个数小于n的一半“不对，3有两个素数{//couta[i]-----endl;for(j=1;j=6;j++){if(pow((double)a[i],(double)j)(double)n){b[i]=j-1;//b的下标不必新开break;}elseif(pow((double)a[i],(double)j)==(double)n)//必须分开{b[i]=j;break;}}}//不知道是不是pow函数的问题，把ans定义为int得出的结果出问题，double就对了doubleans=1;for(k=0;ki;k++){//couta[k]........b[k]endl;ans*=pow((double)a[k],(double)b[k]);}cout(int)ansendl;}return0;}//该程序到25时就溢出，ans换位longlong前几个就错误啦，此时需要把pow函数换掉#includeiostream第7/20页#includecstdio#includecstring#includecmathusingnamespacestd;constintN=105;intn;inta[N][50];intb[N]={0};voidmultiply(){inti,j,k;memset(a,0,sizeof(a));for(i=3;i=100;i++){/*下面的是直接按平常的乘法，乘数的一位乘以被乘数的每一位并处理进位；另外是乘数整体乘以被乘数的每一位最后统一处理进位*/inttemp=0;a[i][0]=1;//很重要for(j=2;j=i;j++){intc=0;for(k=0;k50;k++)//最大不超过160位，目前是100!,最后除以3等50{temp=a[i][k]*b[j]+c;a[i][k]=temp%1000;c=temp/1000;}}}}voidprintData(intn){inti,j,k;for(i=49;i=0;i--)if(a[n][i])break;couta[n][i];//第一个不输出前导0for(j=i-1;j=0;j--)printf(%03d,a[n][j]);第8/20页coutendl;}intmain(){inti,j,k;for(i=0;iN;i++)b[i]=i;for(i=2;iN;i++)for(j=i+1;j=N;j++){if(b[j]%b[i]==0)b[j]/=b[i];//coutb[j]endl;}//for(i=0;i100;i++)//coutb[i]endl;//while(1);multiply();while(cinn){if(n==1||n==2){coutnendl;continue;}printData(n);}return0;}4.程序设计（满分28分）为解决交通难题，某城市修建了若干条交错的地铁线路，线路名及其所属站名如stations.txt所示。线1苹果园....四惠东第9/20页线2西直门车公庄....建国门线4....其中第一行数据为地铁线名，接下来是该线的站名。当遇到空行时，本线路站名结束。下一行开始又是一条新线....直到数据结束。如果多条线拥有同一个站名，表明：这些线间可以在该站换车。为引导旅客合理利用线路资源，解决交通瓶颈问题，该城市制定了票价策略：1.每条线路可以单独购票，票价不等。2.允许购买某些两条可换乘的线路的联票。联票价格低于分别购票。单线票价和联合票价如price.txt所示。线1180.....线13114线1,线2350线1,线10390.....每行数据表示一种票价线名与票价间用空格分开。如果是联票，线名间用逗号分开。联票只能包含两条可换乘的线路。现在的问题是：根据这些已知的数据，计算