第1~3届蓝桥杯决赛试题及答案.docx

2011年暑假蓝桥杯决赛题附答案 1． 四方定理 数论中有著名的四方定理：所有自然数至多只要用四个数的平方和就可以表示。 我们可以通过计算机验证其在有限范围的正确性。对于大数，简单的循环嵌套是不适宜的。下面的代码给出了一种分解方案。请仔细阅读，填写空缺的代码（下划线部分）。 注意：请把填空的答案（仅填空处的答案，不包括题面）存入考生文件夹下对应题号的“解答.txt”中即可。直接写在题面中不能得分。 int f(int n, int a[], int idx) { if(______________) return 1; // 填空1 if(idx==4) return 0; for(int i=(int)sqrt(n); i=1; i--) { a[idx] = i; if(_______________________) return 1; // 填空2 } return 0; } int main(int argc, char* argv[]) { for(;;) { int number; printf(输入整数(1~10亿)：); scanf(%d,number); int a[] = {0,0,0,0}; int r = f(number, a, 0); printf(%d: %d %d %d %d\n, r, a[0], a[1], a[2], a[3]); } return 0; } 2． 加密 在对文本进行简单加密的时候，可以选择用一个n位的二进制数，对原文进行异或运算。解密的方法就是再执行一次同样的操作。加密过程中n位二进制数会循环使用。并且其长度也可能不是8的整数倍。下面的代码演示了如何实现该功能。请仔细阅读，填写空缺的代码（下划线部分）。 注意：请把填空的答案（仅填空处的答案，不包括题面）存入考生文件夹下对应题号的“解答.txt”中即可。 直接写在题面中不能得分。 void f(char* buf, unsigned char* uckey, int n) { int i; for(i=0; in; i++) buf[i] = buf[i] ^ uckey[i]; } int main(int argc, char* argv[]) { char p[] = abcd中国人123; // 待加密串 char* key = 11001100010001110; //以串的形式表达的密匙，运算时要转换为按位存储的形式。 int np = strlen(p); int nk = strlen(key); unsigned char* uckey = (unsigned char*)malloc(np); // 密匙串需要按位的形式循环拼入 uckey中 int i; for(i=0; inp*8; i++) { if(key[i%nk]==1) ____________________________________________; // 填空1 else ____________________________________________; // 填空2 } f(p, uckey, strlen(p)); f(p, uckey, strlen(p)); printf(%s\n, p); free(uckey); return 0; } 3． 公倍数 为什么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 要求考生把所有函数写在一个文件中。调试好后，存入与考生文件夹下对应题号的“解答.txt”中即可。 相关的工程文件不要拷入。 对于编程题目，要求选手给出的解答完全符合ANSI C标准，不能使用c++特性； 不能使用诸如绘图、中断调用等硬件相关或操作系统相关的API。 4． 地铁换乘 为解决交通难题，某城市修建了若干条交错的地铁线路，线路名及其所属站名如stations.txt所示。