1、因式分解
因数分解是十分基本的数学运算，应用广泛。下面的程序对整数n(n>1)进行因数分解。比如，n=60, 则输出：2 2 3 5。请补充缺失的部分。
void f(int n) { for(int i=2; i<n/2; i++) { ____________________ { printf("%d ", i); n = n / i; } } if(n>1) printf("%d\n", n); }
参考答案： while( n % i == 0)
2、选择排序
当数据量较小的时候，使用基本排序方案并不会显著影响程序性能。
选择排序是十分常用的基本排序方案之一。它的每一趟排序都从一个序列中选择最小的那个元素，加入到逐步扩展的已排序序列。初始的时候，已排序序列为第一个元素，待排序序列为剩下的所有元素，即从第二个元素到结尾。
下面的代码演示了对int数组中的n个元素进行基本选择排序。请仔细阅读并分析代码，填写空白处的代码，使得程序的逻辑合理，结果正确。
1 void sel_sort(int* x, int n) 2 { 3 int k, i, m, t; 4 for(k=0; k<n-1; k++) // 多趟排序 5 { 6 m = _____________; // 填空1 7 for(i=k+1; i<n; i++) 8 { 9 if(x[i] < x[m]) _________________; // 填空2 10 } 11 12 t = x[k]; 13 x[k] = x[m]; 14 x[m] = t; 15 } 16 } 17 18 void display(int* x, int n) 19 { 20 for(int i=0; i<n; i++) printf("%d ", x[i]); 21 printf("\n"); 22 } 23 24 void main() 25 { 26 int N = 10; 27 int a[] = {5, 12, 35, 28, 19, 22, 36, 17, 4, 11}; 28 display(a, N); 29 sel_sort(a, N); 30 display(a, N); 31 }
k .................. (7分) m = i ..............(7分) 理解选择排序了就较为简单
3、n进制小数
将任意十进制正小数分别转换成2,3,4,5,6,7,8,9进制正小数，小数点后保留8位，并输出。例如：若十进制小数为0.795，则输出：
十进制正小数 0.795000 转换成 2 进制数为: 0.11001011
十进制正小数 0.795000 转换成 3 进制数为: 0.21011011
十进制正小数 0.795000 转换成 4 进制数为: 0.30232011
十进制正小数 0.795000 转换成 5 进制数为: 0.34414141
十进制正小数 0.795000 转换成 6 进制数为: 0.44341530
十进制正小数 0.795000 转换成 7 进制数为: 0.53645364
十进制正小数 0.795000 转换成 8 进制数为: 0.62702436
十进制正小数 0.795000 转换成 9 进制数为: 0.71348853
以下代码提供了这个功能。其中，dTestNo表示待转的十进制小数。iBase表示进制数。请填写缺失的部分。
1 void fun(double dTestNo, int iBase) 2 { 3 int iT[8]; 4 int iNo; 5 6 printf("十进制正小数 %f 转换成 %d 进制数为: ",dTestNo, iBase); 7 8 for(iNo=0;iNo<8;iNo++) 9 { 10 dTestNo *= iBase; 11 iT[iNo] = ________________; 12 if(___________________) dTestNo -= iT[iNo]; 13 } 14 15 printf("0."); 16 for(iNo=0; iNo<8; iNo++) printf("%d", iT[iNo]); 17 printf("\n"); 18 } 19 20 void main ( ) 21 { 22 double dTestNo= 0.795; 23 int iBase; 24 25 for(iBase=2;iBase<=9;iBase++) 26 fun(dTestNo,iBase); 27 printf("\n"); 28 }
参考答案： 空1： (int)dTestNo （2分） 空2： dTestNo>=1.0 （3分） 注意等价形式，如不能判定，代入程序进行运行试验
4、加密
在对文本进行简单加密的时候，可以选择用一个n位的二进制数，对原文进行异或运算。
解密的方法就是再执行一次同样的操作。
加密过程中n位二进制数会循环使用。并且其长度也可能不是8的整数倍。
下面的代码演示了如何实现该功能。
请仔细阅读，填写空缺的代码（下划线部分）。
注意：请把填空的答案（仅填空处的答案，不包括题面）存入考生文件夹下对应题号的“解答.txt”中即可。
直接写在题面中不能得分。
1 void f(char* buf, unsigned char* uckey, int n) 2 { 3 int i; 4 for(i=0; i<n; i++) 5 buf[i] = buf[i] ^ uckey[i]; 6 } 7 8 int main(int argc, char* argv[]) 9 { 10 char p[] = "abcd中国人123"; // 待加密串 11 12 char* key = "11001100010001110"; //以串的形式表达的密匙，运算时要转换为按位存储的形式。 13 14 int np = strlen(p); 15 int nk = strlen(key); 16 unsigned char* uckey = (unsigned char*)malloc(np); 17 18 // 密匙串需要按位的形式循环拼入 uckey中 19 int i; 20 for(i=0; i<np*8; i++) 21 { 22 if(key[i%nk]=='1') 23 ____________________________________________; // 填空1 24 else 25 ____________________________________________; // 填空2 26 27 } 28 29 f(p, uckey, strlen(p)); 30 f(p, uckey, strlen(p)); 31 32 printf("%s\n", p); 33 34 free(uckey); 35 36 return 0; 37 }
参考答案 填空1：(7分) uckey[i/8] |= (unsigned char)0x80 >> (i%8); 填空2：(7分) uckey[i/8] &= ~((unsigned char)0x80 >> (i%8)); 注意所有逻辑等价形式都是正确的答案，比如可以使用左移位。 (unsignec char)0x80 >> 2 等价于：0x01 << 5
5、四方定理
数论中有著名的四方定理：所有自然数至多只要用四个数的平方和就可以表示。
我们可以通过计算机验证其在有限范围的正确性。
对于大数，简单的循环嵌套是不适宜的。下面的代码给出了一种分解方案。
请仔细阅读，填写空缺的代码（下划线部分）。
注意：请把填空的答案（仅填空处的答案，不包括题面）存入考生文件夹下对应题号的“解答.txt”中即可。
直接写在题面中不能得分。
1 int f(int n, int a[], int idx) 2 { 3 if(______________) return 1; // 填空1 4 if(idx==4) return 0; 5 6 for(int i=(int)sqrt(n); i>=1; i--) 7 { 8 a[idx] = i; 9 10 if(_______________________) return 1; // 填空2 11 } 12 13 return 0; 14 } 15 16 int main(int argc, char* argv[]) 17 { 18 for(;;) 19 { 20 int number; 21 printf("输入整数(1~10亿)："); 22 scanf("%d",&number); 23 24 int a[] = {0,0,0,0}; 25 26 int r = f(number, a, 0); 27 28 printf("%d: %d %d %d %d\n", r, a[0], a[1], a[2], a[3]); 29 30 } 31 32 return 0; 33 }
参考答案 填空1: (3分) n==0 或者：0==n 填空2: (6分) f(n-i*i, a, idx+1) 或者： f(n-i*i, a, idx+1) > 0 f(n-i*i, a, idx+1) == 1 分析：第一空考虑n==0情况无疑，第二空只需考虑到第idx位置的数值是通过枚举获得，这也就使得后面数据的平方和为n-i*i即可。
6、数字黑洞
任意给定一个4位数(不能所有位都相同)，比如：3278，重新组合出最大数：8723，再重新组合出最小数：2378，相减，得到新的4位数（如不足则补0），重复这个过程，最后必然得到一个数字：6174。这个现象被称为：数字黑洞。下面的函数实现由给定的4位整数求出下一个整数的功能。请完善之。
1 int f(int n) 2 { 3 int N[4]; 4 for(int i=0; i<4; i++) 5 { 6 N[3-i] = n % 10; 7 ___________________; 8 } 9 10 for(i=0; i<3; i++) 11 for(int j=0; j<3-i; j++) 12 if(N[j]>N[j+1]) 13 { 14 int t = N[j+1]; 15 N[j+1] = N[j]; 16 N[j] = t; 17 } 18 19 int n_min=0; 20 for(i=0; i<4; i++) 21 n_min = n_min * 10 + N[i] ; 22 int n_max = 0; 23 for(i=3; i>=0; i--) 24 n_max = n_max * 10 + N[i]; 25 26 return n_max-n_min; 27 }
参考答案：n = n / 10 注意：也可以写成 n /= 10
7、数据压缩
某工业监控设备不断发回采样数据。每个数据是一个整数(0到1000之间)。各个数据间用空白字符（空格，TAB或回车换行）分隔。这些数据以文本形式被存储在文件中。
因为大多数时候，相邻的采样间隔数据是相同的，可以利用这个特征做数据的压缩存储。其方法是：对n(n>1)个连续相同的数字只记录n和该数字本身；对m(m>0)个连续不重复的数字，则记录 m*-1 和这些数字本身（之所以用负数，是为了与第一种情况区分，便于解压缩）。
例如：采样数字：
12 34 34 25 25 25 25 11 15 17 28 14 22 22 22 13
则根据上述规则变化后：
-1 12 2 34 4 25 -5 11 15 17 28 14 3 22 -1 13
下面的程序实现了这个功能。请仔细阅读分析代码，填写空白的部分。
1 void pop(int s, int* buf, int c, FILE* fp) 2 { 3 int i; 4 if(s) 5 { 6 fprintf(fp, "%d %d ", c, *buf); 7 } 8 else 9 { 10 fprintf(fp, "%d ", -c); 11 for(i=0; i<c; i++) 12 { 13 fprintf(fp, "%d ", buf[i]); 14 } 15 } 16 } 17 18 void dopack(FILE* r, FILE* w) 19 { 20 int buf[BUF_N]; 21 22 int pos = 0; // 下一个数字在buf中将要存放的位置 23 int c = 0; // 当前段已读入的整数个数 24 int pst; 25 int cst; 26 27 while(fscanf(r, "%d", buf+pos)==1) 28 { 29 if(c==0) 30 { 31 c = pos = 1; 32 continue; 33 } 34 35 if(c==1) 36 { 37 pst = buf[0] == buf[1]; 38 pos = pos + 1 - pst; 39 c = 2; 40 continue; 41 } 42 43 cst = buf[pos-1] == buf[pos]; 44 45 if(pst && !cst) 46 { 47 pop(pst, buf, c, w); 48 buf[0] = buf[1]; 49 c = pos = 1; 50 pst = cst; 51 } 52 53 else if(!pst && cst || pos == BUF_N-1) 54 { 55 pop(pst, buf, c-1, w); 56 buf[0] = buf[pos-1]; 57 c = 2; 58 59 if(!cst) 60 { 61 buf[1] = buf[pos]; 62 pos = 2; 63 } 64 else 65 { 66 pos = 1; 67 pst = ______________; // 填空1 68 } 69 } 70 else 71 { 72 c++; 73 if(!pst) pos++; 74 } 75 } // while 76 77 if(c>0) _____________________________; // 填空2 78 } 79 80 void main() 81 { 82 FILE* rfp; 83 FILE* wfp; 84 85 if((rfp=fopen(RFILE, "r")) == NULL) 86 { 87 printf("can not open %s!\n", RFILE); 88 exit(1); 89 } 90 91 if((wfp=fopen(WFILE, "w")) == NULL) 92 { 93 printf("can not open %s!\n", WFILE); 94 fclose(rfp); 95 exit(2); 96 } 97 98 dopack(rfp, wfp); 99 100 fclose(wfp); 101 fclose(rfp); 102 }
参考答案：
cst .............................. (8分)
pop(pst, buf, c, w) ..............(8分)
8、生日相同概率
生活中人们往往靠直觉来进行粗略的判断，但有的时候直觉往往很不可靠。比如：如果你们班有30名同学，那么出现同一天生日的概率有多大呢？你可能不相信，这个概率高达70%左右。
以下的程序就是用计算机随机模拟，再统计结果。仔细阅读代码，补全空白的部分。
#define N 30 ...... int a[N]; srand( time( NULL ) ); int n = 0; for(int k=0; k<10000; k++) { for(int i=0; i<N; i++) a[i] = rand() % 365; bool tag = false; // 假设没有相同 for(i=1; i<N; i++) { for(int j=0; j<i; j++) { if(a[i]==a[j]) { tag = true; break; } } _____________________; } if(tag) n++; } printf("%f\n", 1.0 * n / 10000 * 100);
答案： if(tag) break
总结：未涉及高级算法，一般简单考察递归、迭代、枚举等基本算法，其中第4、7题相对较难。