当前位置:首页 >> 学科竞赛 >>

C语言竞赛题目大全


C 语言竞赛题目大全
POWERED 问题: 假设在一个 32 位的机器上,需要将某个外设寄存器的第 X 位(最低位为第 0 位,最高位为第 31 位)设置成 0,将第 Y 位开始的 连续三位设置成 110(从高位到低位的顺序),而其它位保持不变。对给定的寄存器值 R,及 X,Y,编程计算更改后的寄存器值 R。 输入的数据仅一行, 包括 R,X,Y, 以逗号"

,"分隔, 为 16 进制表示的 32 位整数, 在 0-31 之间且 Y>=3, R X,Y (Y-X)的绝对值>=3, 保证两次置位不会重合更改后的寄存器值 R(16 进制输出)。例如: Sample Input 12345678,0,3 输出: ? 1234567c 解题思路: 很简单的位操作,但是需要注意的是 Y 那里是 110,不能直接或上 110,而是先两次 SET,在 CLR。 答案: #include <stdio.h> #define CLR(r, x) #define SET(r, y) r &= ~(1UL << x) //1UL 表示 32 位无符号数,将 r 的 x 位清零。 r |= (1UL << y) //表示将 r 的 y 位置零 BY SYD168 2010 年 5 月 7 日

int main() { int r, x, y; scanf("%x,%d,%d", &r, &x, &y); CLR(r,x); //清除 x 位 SET(r,y); //置位 y 位 SET(r,y-1); //置位 y-1 位 CLR(r,y-2); //置位 y-2 位 printf("%x", r); return 0; } 第1题 破译密码

问题: 据说最早的密码来自于罗马的凯撒大帝。消息加密的办法是:对消息原文中的每个字母,分别用该字母之后的第 5 个字母替换 (例如:消息原文中的每个字母 A 都分别替换成字母 F)。而你要获得消息原文,也就是要将这个过程反过来。 密码字母:A B C D E F G H I J K L M N O P Q R S T U V W X Y Z M 原文字母:V W X Y Z A B C D E F G H I J K L M N O P Q R S T U (注意:只有字母会发生替换,其他非字母的字符不变,并且消息原文的所有字母都是大写的。) 输入:最多不超过 100 个数据集组成,每个数据集之间不会有空行,每个数据集由 3 部分组成: 1. 起始行:START 2. 密码消息:由 1 到 200 个字符组成一行,表示凯撒发出的一条消息. 3. 结束行:END 在最后一个数据集之后,是另一行:ENDOFINPUT。 输出: 每个数据集对应一行,是凯撒的原始消息。 ? Sample Input START NS BFW, JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX END START N BTZQI WFYMJW GJ KNWXY NS F QNYYQJ NGJWNFS ANQQFLJ YMFS XJHTSI NS WTRJ 1

?

END START IFSLJW PSTBX KZQQ BJQQ YMFY HFJXFW NX RTWJ IFSLJWTZX YMFS MJ END ENDOFINPUT Sample Output IN WAR, EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSES I WOULD RATHER BE FIRST IN A LITTLE IBERIAN VILLAGE THAN SECOND IN ROME DANGER KNOWS FULL WELL THAT CAESAR IS MORE DANGEROUS THAN HE 解题思路 凯撒编码,判断字符是否是字母,并循环-5 即可,记得要循环哦,非常简单的题目哦 答案: #include <stdio.h> #include <string.h> #include <ctype.h> #define N 202 char str[N]={0}; int main() { char *p; gets(str); while( strcmp(str, "ENDOFINPUT") != 0 ) { if ( (strcmp(str, "START") !=0) //当消息不是开始 &&(strcmp(str, "END") != 0) ) //消息不是结尾 { for(p=str; *p !='\0'; p++) //对输入的串进行解密 { if( isupper(*p) ) //判断是否为大写字符 *p += *p-5 <'A' ? 26-5: -5; //进行转换,考虑边界问题! } puts(str); } gets(str); } return 0; } //输出字符 //接受下一行

//当没遇到消息集的结尾时

第2题

小孩报数问题

有 N 个小孩围成一圈,给他们从 1 开始依次编号,现指定从第 W 个开始报数,报到第 S 个时,该小孩出列,然后从下一个小 孩开始报数,仍是报到 S 个出列,如此重复下去,直到所有的小孩都出列(总人数不足 S 个时将循环报数),求小孩出列的顺序。 或者是求最后出圈人的编号等等类似问题。 输入:第一行输入小孩的人数 N(N<=64),接下来每行输入一个小孩的名字(人名不超过 15 个字符) 最后一行输入 W,S (W < N),用逗号","间隔 输出:按人名输出小孩按顺序出列的顺序,每行输出一个人名 ? Sample Input 5 Xiaoming Xiaohua Xiaowang Zhangsan Lisi 2,3 2

?

Sample Output Zhangsan Xiaohua Xiaoming Xiaowang Lisi 解题思路:(暂空)

第3题

方阵填数

答案:
#include <iostream> using namespace std; int a[10][10]; void Fun(int n) { int m = 1,j,i; for(i = 0; i < n/2; i++) { for(j = 0; j < n-i; j++) { if(a[i][j] == 0) a[i][j] = m++; } for(j = i+1; j < n-i; j++) { if(a[j][n-1-i] == 0) a[j][n-1-i] = m++; } for(j = n-i-1; j > i; j--) { if(a[n-i-1][j] == 0) a[n-i-1][j] = m++; } for(j = n-i-1; j > i; j--) { if(a[j][i] == 0) 第4题 1. 第五套 a[j][i] = m++; } } if(n%2==1) a[n/2][n/2] = m; } void main() { int n, i, j; cin>>n; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) a[i][j] = 0; } Fun(n); for(i = 0; i < n; i++) { for(int j = 0; j < n; j++) { cout << a[i][j] << " "; } cout <<endl; } }

编写一个程序,让它有以下功能:从键盘上输入一个五位数,对此整数中的五个数值进行从大到小排序,形成一个新的五位数, 3

2. 3. 4. 5. 6.

输出这个整数。 输入年、月、日,输出该日期是该年的第几天。 将学生的学号和成绩存储在数组中,利用循环计算出数组中存储学生的平均成绩,找出高于平均分的学生信息并输出。 输入五个国家的名字,按字母顺序(即按 ASCII 码从小到大的顺序)排列输出。 用指针实现:任意输入 20 个数,将它们按照从大到小的顺序输出。 编写一个简单的通讯录管理系统。通讯录包括:姓名、通讯地址、邮编、联系电话,现编写一个通讯录管理系统,可以对通讯 录进行输入、显示、查找,通讯录保存到一个文件中。 进制转换问题

第5题 1.

问题描述 实现将 N 进制到 M 进制数的转换(1 < N,M <= 36)。对于 11 到 36 进制数,其基数使用从 A 到 Z 的英文字母(全部为大写)代 替。例如对于 11 进制,其基数 10(十进制)使用"A"表示;对于 36 进制,其基数 35(十进制)使用"Z"表示。被转换的数全部为正 数且小于 2147483647(long 型的最大值)。下表为十进制数 100 对应的各进制数: 进制 数值 10 100 11 91 16 64 27 3J 35 2U

2. 要求: (1).实现 10 进制数到 M 进制数的转换。(2).程序具有较强的容错能力(例如对错误的输入数字串的处理)。(3). N 进制到 M 进 制数(1 < N,M < 36)的转换(扩展要求,选做)。 3. 输入: 输入文件名为 convert.in,文件内容格式为第一列为被转换数的进制数,第二列为被转换数,第三列为转换后的进制。这三 列内容均为字符串形式。每列之间使用一个空格隔开。 4. 输出: 输出文件名为 convert.out,文件内容为转换后的数。对于一切错误,则输出“error”字符串。 5. 输入输出文件样例: 样例 1 convert.in 10 100 27 样例 2 convert.in 3 140 27 答案: #include <stdio.h> #include <string.h> void ten_to_m(char out[], long int data, int M); int judge(int N, long int data); void convert(char out[], int N, long int data, int M); int main() { int N; int M; long int data; char out[100]; /* convert.out error convert.out 3J

//N 进制 //M 进制 //N 进制数 //存放 M 进制数 */

打开 convert.in 这个文件,从文件中读取用到的数据 FILE *fp = fopen("/home/student/convert.in", "r"); if (fp != NULL) { fscanf(fp, "%d%ld%d", &N, &data, &M); fclose(fp); fp = NULL; } 4

/*

判断数据 data 有没有错,如果没错则转换为 M 进制,如果错则把 error 写入 out 中 */ if (judge(N, data) == 1) { convert(out, N, data, M); } else { strcpy(out, "error"); } printf("%s\n", out);

/*

把得到的结果写入 convert.out 文件中去 FILE *fw = fopen("/home/student/convert.out", "w"); if (fw != NULL) { fprintf(fw, "%s\n", out); fclose(fw); fw = NULL; } return 0;

*/

} /* 判断 data 有没有错,先把 data 转换为字符串,然后再进行判断 int judge(int N, long int data) { char b[100]; //data 转换后放入 b 中 ten_to_m(b, data, 10); //相当于 itoa char *s = b; while (*s != '\0') { if ((*s-'0') >= N) { return 0; } s++; } return 1; } /* N 进制转为 M 进制,先把 N 进制转为十进制,再把十进制转为 M 进制 void convert(char out[], int N, long int data, int M) { int a = n_to_ten(N, data); ten_to_m(out , a, M); } /* 十进制转为 M 进制,当 M=10 时此函数相当于 itoa

*/

*/

*/

void ten_to_m(char out[], long int data, int M) { int i = 0; int tmp = data; int len; char t; /* 把 data 转为字符倒序的放入字符数组 out 中去 5 */

while (tmp != 0) { if (tmp%M >= 10) { out[i] = tmp%M - 10 +'A'; } else { out[i] = tmp%M + '0'; } tmp = tmp/M; i++; } len = i; /* 把字符数组 out 反序 for (i=0; i<len/2; i++) { t = out[i]; out[i] = out[len -i -1]; out[len -i -1] = t; } out[len] = '\0'; */

} /* N 进制转为十进制 */

int n_to_ten(int N, long int data) { char a[100]; int i; ten_to_m(a, data, 10); int len = strlen(a); int out = 0; for (i=0; i<len; i++) { out = out*N + a[i]-'0'; } return out; } 第6题 综合应用

//把 data 转为字符串

1. 矩阵应用 给定一个整数 N,生成一个 N*N 的矩阵,矩阵中元素取值为 1 至 N2,1 在左上角,其余各数按顺时针方向旋转前进,依次递 增放置。例如,当 N=4 时,矩阵中的内容如下: 3 4 13 14 5 16 15 6 9 8 7 给定 n(3 &pound; n &pound; 50000)个闭区间[ai, bi](1 &pound; i &pound; n, ai,bi 均为非负整数),将这些区间合并为不相交 的闭区间。输入文件的第一行包含一个整数 n,为区间的数目。以下有 n 行,每行各包括两个空格分隔的整数 ai 和 bi,表示一个区 间[ai, bi](0 &pound; ai &pound; bi &pound; 1000000)。计算结果写在标准输出上,各区间按照升序排列输出。每一行包含两个用 空格分开的整数,分别描述一个区间的上下界。例如,对于下列输入数据: 1 12 11 10 2

6

5 56 14 10 10 69 8 10 输出为: 14 5 10 2. 字符串处理 从标准输入中读入 N(1<N<10000)行以换行符结束且长度不超过 2048 的字符串, 并在输入结束后输出其中最长 10 行的输入序 号、长度和内容。当有多行长度相等的最长行时,输出最先输入的行的信息。参考【例 2-7】的讨论,分别使用不同的方法实现这 一程序,比较各种方法的运行效率。 3. 汉诺塔问题 写出程序求解 Hanoi 双塔问题。 从标准输入上读入正整数 n(n < 12), 在标准输出上输出盘子的移动动作。 盘子的尺寸由 1 到 n, 输出数据格式为: move <盘子编号> from <原位置> to <新位置> 其中<盘子编号>为<d>a 或<d>b,其中<d>是一个小于等于 n 的正整数,在初始状态下尺寸相同的盘子中 a 盘在 b 盘之上, <原位置>和<新位置>均为字母 ABC 中的一个。例如,移动序列的第一个动作可能是 move 1a from A to C。 4. 表达式问题 从标准输入上读入一个由数字和四则运算符组成的后缀表达式,将其转换为中缀表达式。后缀表达式中的运算符不超过 15 个, 数字可以是整数,也可以是带有小数部分的浮点数,数字和运算符之间由空格分隔。转换后的中缀表达式中不应出现不必要的括号 和空格,且转换前后各运算数的出现顺序不变。例如,对于后缀表达式: 4 7 输出 2.1 5 + * 7.1 9 /

(4-7)*(2.1+5)/(7.1-9) 有大、中、小三个酒桶,分别能装 A 斤、B 斤和 C 斤酒,其中 A、B、C 均为整数,A=B+C,B>C>0,且 A 为偶数。现在大桶 装满了酒,另外两个桶都空着。写程序求解用这三个桶将酒平分成为两份的操作序列。当无解时输出字符串 “No”。 5. 文件处理 读入一个不超过 20000000 个字符的正文文件,统计其中所有由字母组成的单词及其所在的行号。文件中各个单词之间以空白 符或标点分隔,区分大小写。按单词的字典序在标准输出上输出统计结果,输出格式为<word>: <h1> <h2> … <hn>,每个单词 一行,其中<word>是单词,<hn>是行号。行号之间由空格分隔,按升序排列,不得重复,即当一个单词在一行出现多次时,只输 出该行号一次。 6. 路径处理 写一个程序, 列出环境变量 PATH 中包含的所有目录的路径名。 注意, Unix/Linux 上 PATH 中各个路径名之间的分隔符与 Windows 上的不同。使用条件编译,使你的程序可以适用于这两种系统 第7题 1. 第八套

百度语言翻译机

百度的工程师们是非常注重效率的,在长期的开发与测试过程中,他们逐渐创造了一套独特的缩略语。他们在平时的交谈、会 议,甚至在各种技术文档中都会大量运用。 为了让新员工可以更快地适应百度的文化,更好地阅读公司的技术文档,人力资源部决定开发一套专用的翻译系统,把相关文 档中的缩略语和专有名词翻译成日常语言。 输入要求: 输入数据包含三部分: 1. 第一行包含一个整数 N(N<=10000),表示总共有多少个缩略语的词条; 2. 紧接着有 N 行的输入,每行包含两个字符串,以空格隔开。第一个字符串为缩略语(仅包含大写英文字符,长度不超过 10 字节),第二个字符串为日常语言(不包含空格,长度不超过 255 字节); 3. 从第 N+2 开始到输入结束为包含缩略语的相关文档(总长度不超过 1000000 个字节)。例: 6 PS 门户搜索部 NLP 自然语言处理 7

PM 产品市场部 HR 人力资源部 PMD 产品推广部 MD 市场发展部 百度的部门包括 PS,PM,HR,PMD,MD 等等,其中 PS 还包括 NLP 小组。 样例:in.txt 输出要求: 输出将缩略语转换成日常语言后的文档。(将缩略语转换成日常语言,其他字符保留原样)。例: 百度的部门包括门户搜索部,产品市场部,人力资源部,产品推广部,市场发展部等等,其中门户搜索部还包括自然语言处理 小组。 样例:out.txt 2. 饭团的烦恼 “午餐饭团”是百度内部参与人数最多的民间组织。同一个部门的、同一所大学的、同一年出生的、使用同一种型号电脑的员工 们总是以各种理由组织各种长期的、临时的饭团。 参加饭团,不仅可以以优惠的价格尝到更加丰富的菜式,还可以在吃饭的时候和同事们增进感情。但是,随着百度的员工越来越多, 各个饭团的管理变得繁杂起来。特别是为了照顾员工们越来越挑剔的胃,饭团的点菜负责人的压力也越来越大。现在,这个任务就 交给“百度之星”了,因为,你将要为所有的百度饭团设计一个自动点菜的算法。 饭团点菜的需求如下: 1.经济是我们要考虑的一个因素,既要充分利用百度员工的午餐补助,又不能铺张浪费。因此,我们希望最后的人均费用越接 近 12 元越好。 2.菜式丰富是我们要考虑的另一个因素。为简单起见,我们将各种菜肴的属性归结为荤菜,素菜,辛辣,清淡,并且每个菜只 能点一次。 3.请谨记,百度饭团在各大餐馆享受 8 折优惠。 输入要求: 1.输入数据第一行包含三个整数 N,M,K(0<N<=16,0<M<=N,0<K<=12),分别表示菜单上菜的数目,饭团需要点的菜 的数目,就餐的人数; 2.紧接着 N 行,每行的格式如下: 菜名(长度不超过 20 个字符) 价格(原价,整数)是否荤菜(1 表示是,0 表示否) 是否辛辣(1 表示是,0 表示否); 3.第 N+2 行是 a b c d 四个整数,分别表示需要点的荤菜,素菜,辛辣,清淡菜的数目。例: 322 水煮鱼 30 1 1 口水鸡 18 1 1 清炖豆腐 12 0 0 1111 样例:in.txt 输出要求: 对于每组测试数据,输出数据包含 M+1 行,前 M 行每行包含一个菜名(按菜名在原菜单的顺序排序)。第 M+1 行是人均消费, 结果保留两位小数。例: 口水鸡 清炖豆腐 12.00 样例:out.txt 第8题 比赛规则

为了促进各部门员工的交流,百度举办了一场全公司范围内的“拳皇”(百度内部最流行的格斗游戏)友谊赛,负责组织这场比 赛的是百度的超级“拳皇”迷 W.Z。W.Z 不想用传统的淘汰赛或者循环赛的方式,而是自己制定了一个比赛规则。 由于一些员工(比如同部门或者相邻部门员工)平时接触的机会比较多,为了促进不同部门之间的交流,W.Z 希望员工自由分 组。不同组之间的每两个人都会进行一场友谊赛而同一组内的人之间不会打任何比赛。 比如 4 个人,编号为 1~4,如果分为两个组并且 1,2 一个组,3,4 一个组,那么一共需要打四场比赛:1 vs 3,1 vs 4,2 vs 3, 2 vs 4。而如果是 1,2,3 一组,4 单独一组,那么一共需要打三场比赛: 1 vs 4,2 vs 4,3 vs 4。 很快 W.Z 意识到,这样的比赛规则可能会让比赛的场数非常多。W.Z 想知道如果有 N 个人,通过上面这种比赛规则,总比赛场 数有可能为 K 场吗?比如 3 个人,如果只分到一组则不需要比赛,如果分到两组则需要 2 场比赛,如果分为三组则需要 3 场比赛。 但是无论怎么分都不可能恰需要 1 场比赛。 相信作为编程高手的你一定知道该怎么回答这个问题了吧?那么现在请你帮助 W.Z 吧。 输入要求: 8

每行为一组数据,包含两个数字 N, K(0<N<=500, K>=0)。例: 20 21 31 32 样例:in.txt 输出要求: 对输入的 N,K 如果 N 个员工通过一定的分组方式可以使比赛场数恰好为 K,则输出"YES",否则输出"NO"(请全部使用大写字母), 每组数据占一行。例: YES YES NO YES 样例:out.txt 第9题 蝈蝈计分

蝈蝈小朋友刚刚学会了 0~9 这十个数字,也跟爸爸妈妈来参加百度每周进行的羽毛球活动。但是他还没有球拍高,于是大人们 叫他记录分数。聪明的蝈蝈发现只要记录连续得分的情况就可以了,比如用“3 2 4”可以表示一方在这一局中连得三分后,输了两分, 接着又连得到四分。可是,后来大人们发现蝈蝈只会用 0~9 这十个数字,所以当比赛选手得分超过 9 的时候,他会用一个 X 来表示 10 完成记分。但问题是,当记录为“X 3 5”的时候,蝈蝈自己也记不起来是一方连续得到十三分后,再输五分;还是先赢十分输三分 再赢五分。 因为百度内部就要开始进行羽毛球联赛了,要先摸清大家的实力才好分组比赛呢~于是,大人们想知道以前每局的比分是怎样 的,以及谁获得了胜利。要是遇到了根据比赛记录无法确认比赛过程的情况,也要输出相应的提示哦。 需要进一步说明的是,比赛是五局三胜的,每局先获得二十一分的为胜,但是胜方必须领先对手两分或以上,否则必须继续比 赛直到一方超出对手两分为止,比分多的一方获胜。任何一方先获胜三局后就获得最终胜利,比赛也相应的结束。而且蝈蝈保证是 完整的无多余信息的记录了比赛。 输入要求: 1.文件中第一行只有一个整数 M,表示蝈蝈记录了多少场比赛的分数; 2.在接下来的 2M 行里,每场比赛用两行记录,第一行是一个整数 N(N<=1000)表示当前这个记录中有多少个字符,第二行就 是具体的 N 个字符表示记录的分数(相邻字符用空格隔开)。例: 3 23 973624783279X22121X1X11 25 9385483984XXXX2XXXX284924 43 7777734567654213579753130993932111515151551 样例:in.txt 输出要求: 对应每一个分数记录,输出相应的每局分数,每局分数都使用两个整数表示,表示两个选手的得分,中间用":"分隔开;每组分 数记录间使用一个空行分隔开。如果相应的比赛结果无法预测,以“UNKNOWN”一个单词独占一行表示(请全部使用大写字母)。 例: 21:17 24:22 21:3 UNKNOWN 21:14 20:22 21:23 21:16 21:9 样例:out.txt 第10题 座位调整 9

百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现,员工如果可以在自己喜欢的美食旁边工作,效率会大 大提高。因此,百度决定进行一次员工座位的大调整。 调整的方法如下: 1.首先将办公区按照各种零食的摆放分成 N 个不同的区域(例如:可乐区,饼干区,牛奶区等等); 2.每个员工对不同的零食区域有不同的喜好程度(喜好程度是 1~100 的整数,喜好程度越大表示该员工越希望被调整到相应 的零食区域); 3.由于每个零食区域可以容纳的员工数量有限,人力资源部希望找到一个最优的调整方案使得总的喜好程度最大。 输入要求: 文件第一行包含两个整数 N,M(N>=1,M<=300)。分别表示 N 个区域和 M 个员工; 第二行是 N 个整数构成的数列 a,其中 a[i]表示第 i 个区域可以容纳的员工数(1<=a[i]<=M,a[1]+a[2]+...+a[N]=M); 紧接着是一个 M*N 的矩阵 P,P(i,j)表示第 i 个员工对第 j 个区域的喜好程度。例: 33 111 100 50 25 100 50 25 100 50 25 样例:in.txt 输出要求: 对于每个测试数据,输出可以达到的最大的喜好程度。例: 175 样例:out.txt 数据解释: 此数据只存在一种安排方法,三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175 第11题 剪刀石头布

N 个小孩正在和你玩一种剪刀石头布游戏(剪刀赢布,布赢石头,石头赢剪刀)。N 个小孩中有一个是裁判,其余小孩分成三 组(不排除某些组没有任何成员的可能性),但是你不知道谁是裁判,也不知道小孩们的分组情况。然后,小孩们开始玩剪刀石头 布游戏,一共玩 M 次,每次任意选择两个小孩进行一轮,你会被告知结果,即两个小孩的胜负情况,然而你不会得知小孩具体出的 是剪刀、石头还是布。已知各组的小孩分别只会出一种手势(因而同一组的两个小孩总会是和局),而裁判则每次都会随便选择出 一种手势,因此没有人会知道裁判到底会出什么。请你在 M 次剪刀石头布游戏结束后,猜猜谁是裁判。如果你能猜出谁是裁判,请 说明最早在第几次游戏结束后你就能够确定谁是裁判。 输入要求: 输入文件包含多组测试数据,每组测试数据第一行为两个整数 N 和 M(1<=N<=500,0<M<=2000),分别为小孩的个数和剪刀 石头布游戏进行的次数。接下来 M 行,每行两个整数且中间以一个符号隔开。两个整数分别为进行游戏的两个小孩各自的编号(为 小于 N 的非负整数)。符号的可能值为“=”、“>”和“<”,分别表示和局、第一个小孩胜和第二个小孩胜三种情况。例: 33 0<1 1<2 2<0 35 0<1 0>1 1<2 1>2 0<2 44 0<1 0>1 2<3 2>3 10 样例:in.txt 输出要求: 1.每组测试数据输出一行,若能猜出谁是裁判,则输出裁判的编号,并输出在第几次游戏结束后就能够确定谁是裁判,小孩的编号 和游戏次数以一个空格隔开; 2.如果无法确定谁是裁判,输出-2;如果发现剪刀石头布游戏的胜负情况不合理(即无论谁是裁判都会出现矛盾),则输出-1。例: 10

-2 14 -1 00 第12题 <0> 一个正整数有可能可以被表示为 n(n>=2)个连续正整数之和,如: 15=1+2+3+4+5 15=4+5+6 15=7+8 请编写程序,根据输入的任何一个正整数,找出符合这种要求的所有连续正整数序列。 输入数据: 一个正整数,以命令行参数的形式提供给程序。 输出数据: 在标准输出上打印出符合题目描述的全部正整数序列,每行一个序列,每个序列都从该序列的最小正整数开始、以从小到大的顺序 打印。如果结果有多个序列,按各序 列的最小正整数的大小从小到大打印各序列。此外,序列不允许重复,序列内的整数用一个空格分隔。如果没有符合要求的序列, 输出“NONE”。 例如,对于 15,其输出结果是: 12345 456 78 对于 16,其输出结果是: NONE <1> 重叠区间大小(20 分) 题目描述: 请编写程序,找出下面“输入数据及格式”中所描述的输入数据文件中最大重叠区间的大小。 对一个正整数 n,如果 n 在数据文件中某行的两个正整数(假设为 A 和 B)之间,即 A<=n<=B 或 A>=n>=B,则 n 属于该行; 如果 n 同时属于行 i 和 j,则 i 和 j 有重叠区间;重叠区间的大小是同时属于行 i 和 j 的整数个数。 例如,行(10 20)和(12 25)的重叠区间为[12 20],其大小为 9;行(20 10)和(12 18)的重叠区间为[10 12],其大小为 3;行(20 10)和(20 30)的重叠区间大小为 1。 输入数据: 程 序读入已被命名为 input.txt 的输入数据文本文件,该文件的行数在 1 到 1,000,000 之间,每行有用一个空格分隔的 2 个正整数,这 2 个正整数的 大小次序随机,每个数都在 1 和 2^32-1 之间。(为便于调试,您可下载测试 input.txt 文件,实际运行时我们会使用不同内容的输 入文件。) 输出数据: 在标准输出上打印出输入数据文件中最大重叠区间的大小,如果所有行都没有重叠区间,则输出 0。 评分标准: 程序输出结果必须正确,内存使用必须不超过 256MB,程序的执行时间越快越好。 <2> 题目描述: 请编写程序,根据指定的对应关系,把一个文本中的字符串替换成另外的字符串。 输入数据: 程 序读入已被命名为 text.txt 和 dict.txt 的两个输入数据文本文件,text.txt 为一个包含大量字符串(含中文)的文本,以 whitespace 为分隔符;dict.txt 为表示字符串(s1)与字符串(s2)的对应关系的另一个文本(含中文),大约在 1 万行左右,每行 两个字 符串(即 s1 和 s2),用一个\t 或空格分隔。dict.txt 中各行的 s1 没有排序,并有可能有重复,这时以最后出现的那次 s1 所对应的 s2 为准。 text.txt 和 dict.txt 中的每个字符串都可能包含除 whitespace 之外的任何字符。text.txt 中的字符串必须和 dict.txt 中的某 s1 完全匹配才能被替换。(为便于调试,您可下载测试 text.txt 和 dict.txt 文件,实际运行时我们会使用不同内容的输入文 件。) 输出数据: 11 数与表达式

在标准输出上打印 text.txt 被 dict.txt 替换后了的整个文本。 评分标准: 程序输出结果必须正确,内存使用越少越好,程序的执行时间越快越好。 第13题 低频词过滤

<1>:低频词过滤(40 分) 题目描述: 请编写程序,从包含大量单词的文本中删除出现次数最少的单词。如果有多个单词都出现最少的次数,则将这些单词都删除。 输入数据: 程序读入已被命名为 corpus.txt 的一个大数据量的文本文件, 该文件包含英文单词和中文单词, 词与词之间以一个或多个 whitespace 分隔。(为便于调试,您可下载测试 corpus.txt 文件,实际运行时我们会使用不同内容的输入文件。) 输出数据: 在标准输出上打印删除了 corpus.txt 中出现次数最少的单词之后的文本(词与词保持原来的顺序,仍以空格分隔)。 评分标准: 程序输出结果必须正确,内存使用越少越好,程序的执行时间越快越好。 题目描述: 一个 Internet 站点集合,可以用如下的方式来描述站点和站点之间的链接引用关系: s1234 1/403 23/45 322/2 4614/ 其中与 s(site)同行和同列的数字都表示站点号,其他每个数字表示一个站点到另一个站点的超文本链接数。如果站点 A 有到另一个 站点 B 的直接链接或间接(指通过一个或多个直接链接)链接,则称站点 A 有到站点 B 的访问关系,或称站点 B 可以被站点 A 访问 到。例如,上面描述了一个有 4 个站点链接关系的站点集合,第一行 / 4 0 3 表示站点 1 到站点 1,2,3,4 的超文本链接数。 请编写程序: 1) 将一个有 N 个站点的集合划分成满足下面所有条件的站点子集(这些子集的 union 组成了该 N 个站点集合): a) 当任一子集中的站点数大于 1 时,该子集内至少存在一个站点有到该子集内所有其他站点的访问关系; b) 当任一子集中的站点数大于 1 时,该子集内的任一站点至少可以被该子集内的某一站点访问到; c) 两个不同子集中的任意两个站点之间不存在任何访问关系。 2) 裁减这些子集内的站点之间现有的链接关系,使得被裁减后的各子集内的站点依然可以满足上述所有条件,同时使得子集内的 站点之间的链接总数相加之和为最小。 假如上面的站点集合是这 N 个站点集合中的一个子集,它满足了条件 a):4 可以访问到 3, 也可以访问到 2 和 1;也满足了条件 b):站点 4 可以被站点 3 访问到,等等。对该站点集合进行裁减使其仍然满足条件 a 和 b,并 使得其链接总数之和为最小的结果为: s1234 1/000 20/00 320/2 4014/ 这里,站点 4 可以访问到站点 3 和 2,站点 4 也可以访问到站点 1(通过站点 3 间接访问);此外,站点 3 可以访问到站点 4;最小 链接总数相加为 2+2+1+4=9。

输入数据:
程序读入已被命名为 sites.txt 的完全如上所示的 N*N 矩阵的输入数据文本文件,N 不大于 10 万(N 即为行数和列数),输入文件 的每一行的列和列之间用一个\\t 分隔,行和行之间用\\n 分隔。

输出数据:
按行输出满足题目要求的每个子集内的站点数以及裁减后的最小链接总数之和,数和数之间都以一个空格分隔。如上述子集和最小 链接总数为:1 2 3 4 9 如果输入数据无满足题目要求的子集存在,则输出 NONE。 <2> 题目描述: 一个智能决策系统可以由规则库和事实库两部分组成, 假定规则库的形式为: Ri C1 & C2 & … & Cn->A 表示在条件 C1,C2,… 和 Cn 都满足的前提下,结论 A 成立(即采取行动 A);Ri 表示这是规则库中的第 i 条规则。事实库则由若干为真的条件(即命题)所 组成。 对一个新的待验证的命题 Q,可使用数据驱动或目标驱动两种推理方式之一,来确认它是否可由某规则库和事实库推出: 1) 数据驱动的推理是指从事实库开始,每次试图发现规则库中某条能满足所有条件的规则,并将其结论作为新的事实加入事实库, 然后重复此过程,直至发现 Q 是一个事实或没有任何新的事实可被发现; 12

2) 目标驱动的推理是指从目标假设 Q 出发,每次试图发现规则库中某条含该假设的规则,然后将该规则的前提作为子目标,确认 这些子目标是否和事实库中的事实相匹配,如果没有全部匹配,则重复此过程,直至发现新的子目标都为真或不能再验证子目标是 否为真。 例如,一个规则库为: R1 X & B & E -> Y R2 Y & D -> Z R3 A->X 事实库为: A B C D E 如果想知道命题 Z 是否为真,数据驱动的推理是从 A B C D E 开始,依次匹配规则 R3(得到新事实 X),R1(得到新事实 Y)和 R2, 得到 Z 为真的事实;目标驱动的推理是从假设目标 Z 开始,依次匹配规则 R2(得到新的子目标 Y),R1(得到新的子目标 X)和 R3,得到假设 Z 为真的结论。 请编写程序正确、高效的实现这两种推理方式。 输入数据: 程序需要两个命令行参数: 1) <推理方式>:data|goal,分别表示程序应采用数据驱动的推理或目标驱动的推理; 2) <命题>:如 Z。 此外,程序还需读入已被命名为 rules.txt 的规则库和已被命名为 facts.txt 的事实库。规则库中的规则可能在千量级,按 R1,R2,R3… 依次按行排列的,每行一条规则,每条规则都以 Ri C1 & C2 & … & Cn->A 的形式表示,Ri 和 C1 之间有 1 个或多个空格,Ci 和&之 间,Cn 和->之间,以及->和 A 之间可以有 0 或多个空格。事实库中的各事实之间用 1 个\\n 隔开,每行一个事实。 输出数据: 如果 Z 能被推理为真,则输出: TRUE <推理方式:data 或 goal> <用空格隔开的规则序列:以在所输入的推理方式下,推 出该命题为真的规则被激活的顺序排列> 例如:TRUE goal R2 R1 R3 如果 Z 不能被推理为真,输出: UNCERTAIN <3>题目描述: 八方块移动游戏要求从一个含 8 个数字(用 1-8 表示)的方块以及一个空格方块(用 0 表示)的 3x3 矩阵的起始状态开始,不断移 动该空格方块以使其和相邻的方块互换,直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右 4 个方向可移动, 在四个角落上有 2 个方向可移动,在其他位置上有 3 个方向可移动。例如,假设一个 3x3 矩阵的初始状态为: 803 214 765 目标状态为: 123 804 765 则一个合法的移动路径为: 803 813 813 013 103 123 2 1 4 => 2 0 4 => 0 2 4 => 8 2 4 => 8 2 4 => 8 0 4 765 765 765 765 765 765 另外,在所有可能的从初始状态到目标状态的移动路径中,步数最少的路径被称为最短路径;在上面的例子中,最短路径为 5。如 果不存在从初试状态到目标状态的任何路径,则称该组状态无解。 请设计有效的 (细节请见评分规则) 算法找到从八方块的某初试状态到某目标状态的所有可能路径中的最短路径, 并用 C/C++实现。 输入数据: 程序需读入已被命名为 start.txt 的初始状态和已被命名为 goal.txt 的目标状态,这两个文件都由 9 个数字组成(0 表示空格,1-8 表 示 8 个数字方块),每行 3 个数字,数字之间用空格隔开。 输出数据: 如果输入数据有解,输出一个表示最短路径的非负的整数;如果输入数据无解,输出-1。 自测用例: 如果输入为:start.txt 和 goal.txt,则产生的输出应为: 13

5 又例,如果用 784 356 102 替换 start.txt 中的内容,则产生的输出应为: 21 第14题 矩阵应用

(1).给定一个整数 N,生成一个 N*N 的矩阵,矩阵中元素取值为 1 至 N2,1 在左上角,其余各数按顺时针方向旋转前进,依次 递增放置。例如,当 N=4 时,矩阵中的内容如下: 1 12 11 10 3 4 13 14 5 16 15 6 9 8 7 (2).给定 n(3 &pound; n &pound; 50000)个闭区间[ai, bi](1 &pound; i &pound; n, ai,bi 均为非负整数),将这些区间合并为不 相交的闭区间。输入文件的第一行包含一个整数 n,为区间的数目。以下有 n 行,每行各包括两个空格分隔的整数 ai 和 bi,表示一 个区间[ai, bi](0 &pound; ai &pound; bi &pound; 1000000)。计算结果写在标准输出上,各区间按照升序排列输出。每一行包含两 个用空格分开的整数,分别描述一个区间的上下界。例如,对于下列输入数据: 5 56 14 10 10 69 8 10 输出为: 14 5 10 (3)从标准输入中读入 N(1<N<10000)行以换行符结束且长度不超过 2048 的字符串,并在输入结束后输出其中最长 10 行的输 入序号、长度和内容。当有多行长度相等的最长行时,输出最先输入的行的信息。参考【例 2-7】的讨论,分别使用不同的方法实 现这一程序,比较各种方法的运行效率。 (4).写出程序求解 Hanoi 双塔问题。从标准输入上读入正整数 n(n < 12),在标准输出上输出盘子的移动动作。盘子的尺寸由 1 到 n,输出数据格式为: move <盘子编号> from <原位置> to <新位置> 其中<盘子编号>为<d>a 或<d>b,其中<d>是一个小于等于 n 的正整数,在初始状态下尺寸相同的盘子中 a 盘在 b 盘之上,<原 位置>和<新位置>均为字母 ABC 中的一个。例如,移动序列的第一个动作可能是 move 1a from A to C。 (5).从标准输入上读入一个由数字和四则运算符组成的后缀表达式,将其转换为中缀表达式。后缀表达式中的运算符不超过 15 个,数字可以是整数,也可以是带有小数部分的浮点数,数字和运算符之间由空格分隔。转换后的中缀表达式中不应出现不必要的 括号和空格,且转换前后各运算数的出现顺序不变。例如,对于后缀表达式: 4 7 输出 2.1 5 + * 7.1 9 / 2

(4-7)*(2.1+5)/(7.1-9) (6).有大、中、小三个酒桶,分别能装 A 斤、B 斤和 C 斤酒,其中 A、B、C 均为整数,A=B+C,B>C>0,且 A 为偶数。现在 大桶装满了酒,另外两个桶都空着。写程序求解用这三个桶将酒平分成为两份的操作序列。当无解时输出字符串 “No”。 (7) 读入一个不超过 20000000 个字符的正文文件,统计其中所有由字母组成的单词及其所在的行号。文件中各个单词之间以 空白符或标点分隔,区分大小写。按单词的字典序在标准输出上输出统计结果,输出格式为<word>: <h1> <h2> … <hn>,每个 单词一行,其中<word>是单词,<hn>是行号。行号之间由空格分隔,按升序排列,不得重复,即当一个单词在一行出现多次时, 只输出该行号一次。 (8) 写一个程序,列出环境变量 PATH 中包含的所有目录的路径名。注意,Unix/Linux 上 PATH 中各个路径名之间的分隔符与 Windows 上的不同。使用条件编译,使你的程序可以适用于这两种系统。 第15题 经典问题

1.将7万元投资到A,B,C三项目上, 其利润见下表: 投资额(万元)│ 1 2 3 4 5



7 14

──────┼────────────────────

A利润 │0.11 0.13 0.15 0.24 0.24 0.30 0.35 B利润 │0.12 0.16 0.21 0.25 0.25 0.29 0.34 目 C利润 │0.08 0.12 0.20 0.26 0.26 0.30 0.35 如何分配投资额,使获得的利润最大。 2.将真分数分解为埃及分数(分子为 1 的分数称为埃及分数)。 输入一个真分数,请将该分数分解为埃及分数。 如:8/11=1/2+1/5+1/55+1/110 3.在N行N列的数阵中, 数K(1〈=K〈=N)在每行和每列中出现且仅出现一次,这样的数阵叫N阶拉丁方阵。例如下图 就是一个五阶拉丁方阵。编一程序,从键盘输入N值后,打印出所有不同的N阶拉丁方阵,并统计个数。 项 1 4 5 2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4 4.十个小孩围成一圈分糖果,老师分给第一个小孩 10 块,第二个小孩 2 块,第三个小孩 8 块,第四个小孩 22 块,第五个小 孩 16 块,第六个小孩 4 块,第七个小孩 10 块,第八个小孩 6 块,第九个小孩 14 块,第十个小孩 20 块。然后所有的小孩同时将手 中的糖分一半给右边的小孩;糖块数为奇数的人可向老师要一块。问经过这样几次后大家手中的糖的块数一样多?每人各有多少块 糖? 第16题 歌手大赛问题 2 3

题目:青年歌手参加歌曲大奖赛,有 10 个评委进行大粪,试编程求这位选手的平均得分。 3 种方法:分别要求使用到排序,数组,函数,指针。 分析:这道题的核心程序是排序,将评委打的 10 个分数利用数组按增序(或降序)排列,计算数组中除了第一个和最后一个分数以 外的数以外的数的平均分

答案: #include<stdio.h> double Aver(int p[],int count) //求出结果,p 为整型数组,count 为数组大小 { double result=0; for(int i=0;i<count-1;i++) //排序 for(int j=i;j<count;j++) { if(p[i]<p[j]) { int temp=p[i]; p[i]=p[j]; p[j]=temp; } } printf("评委打分按顺序:"); for(int m=0;m<10;m++) //显示排序后结果 printf("%d ",p[m]); printf("\n"); for(int k=1;k<count-1;k++) //求出去掉首尾的平均分 result+=p[k]; result/=count-2; return result; } void main() { printf("请输入 10 组评分:\n"); int p[10]; int i; 15

for(i=0;i<10;i++) //输入评分 { printf("输入评委%d 打分:",i+1); scanf("%d",&p[i]); } double result=Aver(p,10); //计算平均分 printf("\n 平均分为%5.2f\n",result); } 第17题 100 个经典 C 语言程序

1. 绘制余弦曲线 在屏幕上用“*”显示 0~360 度的余弦函数 cos(x)曲线 *问题分析与算法设计 如果在程序中使用数组,这个问题十分简单。但若规定不能使用数组,问题就变得不容易了。 关键在于余弦曲线在 0~360 度的区间内,一行中要显示两个点,而对一般的显示器来说,只能按行输出,即:输出第一行信息 后,只能向下一行输出,不能再返回到上一行。为了获得本文要求的图形就必须在一行中一次输出两个“ *” 。 为了同时得到余弦函数 cos(x)图形在一行上的两个点,考虑利用 cos(x)的左右对称性。将屏幕的行方向定义为 x,列方向定义 为 y, 0~180 度的图形与 180~360 度的图形是左右对称的, 则 若定义图形的总宽度为 62 列, 计算出 x 行 0~180 度时 y 点的坐标 m, 那么在同一行与之对称的 180~360 度的 y 点的坐标就 应为 62-m。程序中利用反余弦函数 acos 计算坐标(x,y)的对应关系。 使用这种方法编出的程序短小精炼,体现了一定的技巧。 *程序说明与注释 #include<stdio.h> #include<math.h> void main() { double y; int x,m; for(y=1;y>=-1;y-=0.1) /*y 为列方向,值从 1 到-1,步长为 0.1*/ { m=acos(y)*10; /*计算出 y 对应的弧度 m,乘以 10 为图形放大倍数*/ for(x=1;x<m;x++) printf(" "); printf("*"); /*控制打印左侧的 * 号*/ for(;x<62-m;x++)printf(" "); printf("*\\n"); /*控制打印同一行中对称的右侧*号*/ } } 2. 2.绘制余弦曲线和直线 在屏幕上显示 0~360 度的 cos(x)曲线与直线 f(x)=45*(y-1)+31 的迭加图形。其中 cos(x)图形用“*”表示,f(x)用“+”表示, 在两个图形相交的点上则用 f(x)图形的符号。 *问题分析与算法设计 本题可以在上题的基础上进行修改。图形迭加的关键是要在分别计算出同一行中两个图形的列方向点坐标后,正确判断相互的 位置关系。为此,可以先判断图形的交点,再分别控制打印两个不同的图形。 *程序注释与说明 #include<stdio.h> #include<math.h> void main() { double y; int x,m,n,yy; for(yy=0;yy<=20;yy++) /*对于第一个 y 坐标进行计算并在一行中打印图形*/ { y=0.1*yy; m=acos(1-y)*10; n=45*(y-1)+31; /*y:屏幕行方向坐标*/ /*m: cos(x)曲线上 y 点对应的屏幕列坐标*/ /*n: 直线上 y 点对应的列坐标*/ 16

for(x=0;x<=62;x++) /*x: 屏幕列方向坐标*/ if(x==m&&x==n) printf("+"); /*直线与 cos(x)相交时打印“+”*/ else if(x==n) printf("+"); /*打印不相交时的直线图形*/ else if(x==m||x==62-m) printf("*"); /*打印不相交时的 cos(x)图形*/ else printf(" "); /*其它情况打印空格*/ printf("\\n"); } } -------------------------------------------------------------------------------3. 绘制圆 在屏幕上用“*”画一个空心的圆 *问题分析与算法设计 打印圆可利用图形的左右对称性。根据圆的方程: R*R=X*X+Y*Y 可以算出圆上每一点行和列的对应关系。 *程序说明与注释 #include<stdio.h> #include<math.h> void main() { double y; int x,m; for(y=10;y>=-10;y--) { m=2.5*sqrt(100-y*y);

/*计算行 y 对应的列坐标 m,2.5 是屏幕纵横比调节系数因为屏幕的 行距大于列距,不进行调节显示出来的将是椭圆*/ for(x=1;x<30-m;x++) printf(" "); /*图形左侧空白控制*/ printf("*"); /*圆的左侧*/ for(;x<30+m;x++) printf(" "); /*图形的空心部分控制*/ printf("*\\n"); /*圆的右侧*/

} } 4. 歌星大奖赛 在歌星大奖赛中,有 10 个评委为参赛的选手打分,分数为 1~100 分。选手最后得分为:去掉一个最高分和一个最低分后其余 8 个分数的平均值。请编写一个程序实现。 *问题分析与算法实现 这个问题的算法十分简单,但是要注意在程序中判断最大、最小值的变量是如何赋值的。 *程序说明与注释 #include<stdio.h> void main() { int integer,i,max,min,sum; max=-32768; min=32767; sum=0;

/*先假设当前的最大值 max 为 C 语言整型数的最小值*/ /*先假设当前的最小值 min 为 C 语言整型数的最大值*/ /*将求累加和变量的初值置为 0*/

for(i=1;i<=10;i++) { printf("Input number %d=",i); scanf("%d",&integer); sum+=integer; if(integer>max)max=integer; if(integer<min)min=integer;

/*输入评委的评分*/ /*计算总分*/ /*通过比较筛选出其中的最高分*/ /*通过比较筛选出其中的最低分*/

} printf("Canceled max score:%d\\nCanceled min score:%d\\n",max,min); 17

printf("Average score:%d\\n",(sum-max-min)/8); } *运行结果

/*输出结果*/

Input number1=90 Input number2=91 Input number3=93 Input number4=94 Input number5=90 Input number6=99 Input number7=97 Input number8=92 Input number9=91 Input number10=95 Canceled max score:99 Canceled min score:90 Average score:92 *思考题 题目条件不变,但考虑同时对评委评分进行裁判,即在 10 个评委中找出最公平(即评分最接返平均分)和最不公平(即与平均分 的差距最大)的评委,程序应该怎样实现? -------------------------------------------------------------------------------5. 求最大数 问 555555 的约数中最大的三位数是多少? *问题分析与算法设计 根据约数的定义,对于一个整数 N,除去 1 和它自身外,凡能整除 N 的数即为 N 的约数。因此,最简单的方法是用 2 到 N-1 之 间的所有数去除 N,即可求出 N 的全部约数。本题只要求取约数中最大的三位数,则其取值范围可限制在 100 到 999 之间。 *程序说明与注释 #include<stdio.h> void main() { long i; int j; printf("Please input number:"); scanf("%ld",&i); for(j=999;j>=100;j--) if(i%j==0) { printf("The max factor with 3 digits in %ld is:%d,\\n",i,j); break; } } *运行结果 输入:555555 输出:The max factor with 3 digits in 555555 is:777 6. 6.高次方数的尾数 求 13 的 13 次方的最后三位数 *问题分析与算法设计 解本题最直接的方法是:将 13 累乘 13 次方截取最后三位即可。 但是由于计算机所能表示的整数范围有限,用这种“正确”的算法不可能得到正确的结果。事实上,题目仅要求最后三位的值, 完全没有必要求 13 的 13 次方的完整结果。 研究乘法的规律发现:乘积的最后三位的值只与乘数和被乘数的后三位有关,与乘数和被乘数的高位无关。利用这一规律,可 以大大简化程序。 *程序说明与注释 #include<stdio.h> 18

void main() { int i,x,y,last=1;

/*变量 last 保存求 X 的 Y 次方过程中的部分乘积的后三位*/

printf("Input X and Y(X**Y):"); scanf("%d**%d",&x,&y); for(i=1;i<=y;i++) /*X 自乘 Y 次*/ last=last*x%1000; /*将 last 乘 X 后对 1000 取模,即求积的后三位*/ printf("The last 3 digits of %d**%d is:%d\\n",x,y,last%1000); /*打印结果*/ } *运行结果 Input X and Y(X**Y):13**13 The last 3 digits of 13**13 is:253 Input X and Y(X**Y):13**20 The last 3 digits of 13**20 is:801 ----------------------------------------------------------------------------------7. 8.借书方案知多少 小明有五本新书,要借给 A,B,C 三位小朋友,若每人每次只能借一本,则可以有多少种不同的借法? *问题分析与算法设计 本问题实际上是一个排列问题,即求从 5 个中取 3 个进行排列的方法的总数。首先对五本书从 1 至 5 进行编号,然后使用穷举 的方法。假设三个人分别借这五本书中的一本,当三个人所借的书的编号都不相同时,就是满足题意的一种借阅方法。 *程序说明与注释 void main() { int a,b,c,count=0; printf("There are diffrent methods for XM to distribute books to 3 readers:\\n"); for(a=1;a<=5;a++) /*穷举第一个人借 5 本书中的 1 本的全部情况*/ for(b=1;b<=5;b++) /*穷举第二个人借 5 本书中的一本的全部情况*/ for(c=1;a!=b&&c<=5;c++) /*当前两个人借不同的书时,穷举第三个人借 5 本书 中的 1 本的全部情况*/ if(c!=a&&c!=b) /*判断第三人与前两个人借的书是否不同*/ printf(count%8?"%2d:%d,%d,%d ":"%2d:%d,%d,%d\\n /*打印可能的借阅方法*/ } *运行结果 There are diffrent methods for XM to distribute books to 3 readers: 1: 1,2,3 2: 1,2,4 3: 1,2,5 4: 1,3,2 5: 1,3,4 6: 1,3,5 7: 1,4,2 8: 1,4,3 9: 1,4,5 10:1,5,2 11:1,5,3 12:1,5,4 13:2,1,3 14:2,1,4 15:2,1,5 16:2,3,1 17:2,3,4 18:2,3,5 19:2,4,1 20:2,4,3 21:2,4,5 22:2,5,1 23:2,5,3 24:2,5,4 25:3,1,2 26:3,1,4 27:3,1,5 28:3,2,1 29:3,2,4 30:3,2,5 31:3,4,1 32:3,4,2 33:3,4,5 34:3,5,1 35:3,5,2 36:3,5,4 37:4,1,2 38:4,1,3 39:4,1,5 40:4,2,1 41:4,2,3 42:4,2,5 43:4,3,1 44:4,3,2 45:4,3,5 46:4,5,1 47:4,5,2 48:4,5,3 49:5,1,2 50:5,1,3 51:5,1,4 52:5,2,1 53:5,2,3 54:5,2,4 55:5,3,1 56:5,3,2 57:5,3,4 58:5,4,1 59:5,4,2 60:5,4,3 8. 9.杨辉三角形 在屏幕上显示杨辉三角形 19 ",++count,a,b,c); 作者:huang01 发布时间:2004-10-21 17:00:24

1 1 1 1 3 2 3 1 1 1 1 5 1

1 4 6 4 1 5 10 10 ......................................

*问题分析与算法设计 杨辉三角形中的数,正是(x+y)的 N 次方幂展开式各项的系数。本题作为程序设计中具有代表性的题目,求解的方法很多,这里 仅给出一种。 从杨辉三角形的特点出发,可以总结出: 1)第 N 行有 N+1 个值(设起始行为第 0 行) 2)对于第 N 行的第 J 个值:(N>=2) 当 J=1 或 J=N+1 时:其值为 1 J!=1 且 J!=N+1 时:其值为第 N-1 行的第 J-1 个值与第 N-1 行第 J 个值之和 将这些特点提炼成数学公式可表示为: 1 x=1 或 x=N+1 c(x,y)= c(x-1,y-1)+c(x-1,y) 其它

本程序应是根据以上递归的数学表达式编制的。 *程序说明与注释 #include<stdio.h> void main() { int i,j,n=13; printf("N="); while(n>12) scanf("%d",&n); /*控制输入正确的值以保证屏幕显示的图形正确*/ for(i=0;i<=n;i++) /*控制输出 N 行*/ { for(j-0;j<24-2*i;j++) printf(" "); /*控制输出第 i 行前面的空格*/ for(j=1;j<i+2;j++) printf("%4d",c(i,j)); /*输出第 i 行的第 j 个值*/ printf("\\n"); } } void int c(int x,int y) { int z; if((y==1)||(y==x+1)) return 1; /*若为 x 行的第 1 或第 x+1 列,则输出 1*/ z=c(x-1,y-1)+c(x-1,y); /*否则,其值为前一行中第 y-1 列与第 y 列值之和*/ return z; } ----------------------------------------------------------------------------------9. 10.数制转换 将任一整数转换为二进制形式 20 作者:huang01 发布时间:2004-10-21 17:00:59 /*求杨辉三角形中第 x 行第 y 列的值*/

*问题分析与算法设计 将十进制整数转换为二进制的方法很多,这里介绍的实现方法利用了 C 语言能够对位进行操作的特点。对于 C 语言来说,一 个整数在计算机内就是以二进制的形式存储的,所以没有必要再将一个整数经过一系列的运算转换为二进制形式,只要将整数在内 存中的二进制表示输出即可。 *程序说明与注释 #include<stdio.h> void printb(int,int); void main() { int x;printf("Input number:"); scanf("%d",&x); printf("number of decimal form:%d\\n",x); printf(" it\'s binary form:"); printb(x,sizeof(int)*8); /*x:整数 sizeof(int):int 型在内存中所占的字节数 sizeof(int)*8:int 型对应的位数*/ putchar(\'\\n\'); } void printb(int x,int n) { if(n>0) { putchar(\'0\'+((unsigned)(x&(1<<(n-1)))>>(n-1))); printb(x,n-1); /*归调用,输出 x 的后 n-1 位*/ } } *运行结果 输入:8 输出: number of decimal form:8 it\'s bunary form:0000000000001000 输入:-8 输出:number of decimal form:-8 it\'s binary form:1111111111111000 输入:32767 输出:number of decimal form:32767 it\'s binary form:0111111111111111 输入:-32768 输出:number of decimal form:-32768 it\'s binary form:1000000000000000 输入:128 输出:number of decimal form:128 it\'s binary form:0000000010000000 10. 11.打鱼还是晒网

/*输出第 n 位*/

中国有句俗语叫“三天打鱼两天晒网” 。某人从 1990 年 1 月 1 日起开始“三天打鱼两天晒网” ,问这个人在以后的某一天中是 “打鱼”还是“晒网” 。 *问题分析与算法设计 根据题意可以将解题过程分为三步: 1)计算从 1990 年 1 月 1 日开始至指定日期共有多少天; 2)由于“打鱼”和“晒网”的周期为 5 天,所以将计算出的天数用 5 去除; 3)根据余数判断他是在“打鱼”还是在“晒网” ; 若 余数为 1,2,3,则他是在“打鱼” 否则 是在“晒网” 在这三步中,关键是第一步。求从 1990 年 1 月 1 日至指定日期有多少天,要判断经历年份中是否有闰年,二月为 29 天,平年 21

为 28 天。闰年的方法可以用伪语句描述如下: 如果 ((年能被 4 除尽 且 不能被 100 除尽)或 能被 400 除尽) 则 该年是闰年; 否则 不是闰年。 C 语言中判断能否整除可以使用求余运算(即求模) *程序与程序注释 #include<stdio.h> int days(struct date day); struct date{ int year; int month; int day; }; void main() { struct date today,term; int yearday,year,day; printf("Enter year/month/day:"); scanf("%d%d%d",&today.year,&today.month,&today.day); /*输入日期*/ term.month=12; /*设置变量的初始值:月*/ term.day=31; /*设置变量的初始值:日*/ for(yearday=0,year=1990;year<today.year;year++) { term.year=year; yearday+=days(term); /*计算从 1990 年至指定年的前一年共有多少天*/ } yearday+=days(today); /*加上指定年中到指定日期的天数*/ day=yearday%5; /*求余数*/ if(day>0&&day<4) printf("he was fishing at that day.\\n"); /*打印结果*/ else printf("He was sleeping at that day.\\n"); } int days(struct date day) { static int day_tab[2][13]= {{0,31,28,31,30,31,30,31,31,30,31,30,31,},

/*平均每月的天数*/

{0,31,29,31,30,31,30,31,31,30,31,30,31,}, }; int i,lp; lp=day.year%4==0&&day.year%100!=0||day.year%400==0; /*判定 year 为闰年还是平年,lp=0 为平年,非 0 为闰年*/ for(i=1;i<day.month;i++) /*计算本年中自 1 月 1 日起的天数*/ day.day+=day_tab[lp]; return day.day; } *运行结果 Enter year/month/day:1991 10 25 He was fishing at day. Enter year/month/day:1992 10 25 He was sleeping at day. Enter year/month/day:1993 10 25 He was sleeping at day --------------------------------------------------------------------------------作者:huang01 22

---

发布时间:2004-10-21 17:01:32

11.

12.抓交通肇事犯

一辆卡车违反交通规则,撞人后逃跑。现场有三人目击事件,但都没有记住车号,只记下车号的一些特征。甲说:牌照的前两 位数字是相同的;乙说:牌照的后两位数字是相同的,但与前两位不同; 丙是数学家,他说:四位的车号刚好是一个整数的平方。 请根据以上线索求出车号。 *问题分析与算法设计 按照题目的要求造出一个前两位数相同、后两位数相同且相互间又不同的整数,然后判断该整数是否是另一个整 数的平方。 *程序与程序注释 #include<stdio.h> #include<math.h> void main() { int i,j,k,c; for(i=1;i<=9;i++) for(j=0;j<=9;j++) if(i!=j) { k=i*1000+i*100+j*10+j; /*计算出可能的整数*/ for(c=31;c*c<k;c++); /*判断该数是否为另一整数的平方*/ if(c*c==k) printf("Lorry--No. is %d.\\n",k); /*若是,打印结果*/ } } *运行结果 Lorry _No.is 7744 12. 13.该存多少钱

/*i:车号前二位的取值*/ /*j:车号后二位的取值*/ /*判断二位数字是否相异*/

假设银行一年整存零取的月息为 0.63%。现在某人手中有一笔钱,他打算在今后的五年中的年底取出 1000 元,到第五年时刚 好取完,请算出他存钱时应存入多少。 *问题分析与算法设计 分析存钱和取钱的过程,可以采用倒推的方法。若第五年年底连本带息要取 1000 元,则要先求出第五年年初银行存款的钱数: 第五年初存款=1000/(1+12*0.0063) 依次类推可以求出第四年、第三年......的年初银行存款的钱数: 第四年年初存款=(第五年年初存款+1000)/(1+12*0.0063) 第三年年初存款=(第四年年初存款+1000)/(1+12*0.0063) 第二年年初存款=(第三年年初存款+1000)/(1+12*0.0063) 第一年年初存款=(第二年年初存款+1000)/(1+12*0.0063) 通过以上过程就可以很容易地求出第一年年初要存入多少钱。 *程序与程序注释 #include<stdio.h> void main() { int i; float total=0; for(i=0;i<5;i++) /*i 为年数,取值为 0~4 年*/ total=(total+1000)/(1+0.0063*12); /*累计算出年初存款数额,第五次的计算 结果即为题解*/ printf("He must save %.2f at first.\\n",total); } *运行结果 He must save 4039.44 at first 13. 14.怎样存钱利最大 23

假设银行整存整取存款不同期限的月息利率分别为: 0.63% 期限=1 年 0.66% 期限=2 年 0.69% 期限=3 年 0.75% 期限=5 年 0.84% 期限=8 年 利息=本金*月息利率*12*存款年限。 现在某人手中有 2000 元钱,请通过计算选择一种存钱方案,使得钱存入银行 20 年后得到的利息最多(假定银行对超过存款期 限的那一部分时间不付利息)。 *问题分析与算法 为了得到最多的利息,存入银行的钱应在到期时马上取出来,然后立刻将原来的本金和利息加起来再作为新的本金存入银行, 这样不断地滚动直到满 20 年为止,由于存款的利率不同,所以不同的存款方法(年限)存 20 年得到的利息是不一样的。 分析题意,设 2000 元存 20 年,其中 1 年存 i1 次,2 年存 i2 次,3 年存 i3 次,5 年存 i5 次,8 年存 i8 次,则到期时存款人应 得到的本利合计为: 2000*(1+rate1)i1*(1+rate2)i2*(1+rate3)i3*(1+rate5)i5*(1+rate8)i8 其中 rateN 为对应存款年限的利率。根据题意还可得到以下限制条件: 0<=i8<=2 0<=i5<=(20-8*i8)/5 0<=i3<=(20-8*i8-5*i5)/3 0<=i2<=(20-8*i8-5*i5-3*i3)/2 0<=i1=20-8*i8-5*i5-3*i3-2*i2 可以用穷举法穷举所有的 i8、i5、i3、i2 和 i1 的组合,代入求本利的公式计算出最大值,就是最佳存款方案。 *程序与程序注释 #include<stdio.h> #include<math.h> void main() { int i8,i5,i3,i2,i1,n8,n5,n3,n2,n1; float max=0,term; for(i8=0;i8<3;i8++) /*穷举所有可能的存款方式*/ for(i5=0;i5<=(20-8*i8)/5;i5++) for(i3=0;i3<=(20-8*i8-5*i5)/3;i3++) for(i2=0;i2<=(20-8*i8-5*i5-3*i3)/2;i2++) { i1=20-8*i8-5*i5-3*i3-2*i2; term=2000.0*pow((double)(1+0.0063*12),(double)i1) *pow((double)(1+2*0.0063*12),(double)i2) *pow((double)(1+3*0.0069*12),(double)i3) *pow((double)(1+5*0.0075*12),(double)i5) *pow((double)(1+8*0.0084*12),(double)i8); /*计算到期时的本利合计*/ if(term>max) { max=term;n1=i1;n2=i2;n3=i3;n5=i5;n8=i8; } } printf("For maxinum profit,he should so save his money in a bank:\\n"); printf(" made fixed deposit for 8 year: %d times\\n",n8); printf(" made fixed deposit for 5 year: %d times\\n",n5); printf(" made fixed deposit for 3 year: %d times\\n",n3); printf(" made fixed deposit for 2 year: %d times\\n",n2); printf(" made fixed deposit for 1 year: %d times\\n",n1); printf(" Toal: %.2f\\n",max); /*输出存款方式*/ } *运行结果 For maxinum profit,he should so save his money in a bank: 24

made made made made made

deposit for 8 year: 0times deposit for 5 year: 4times deposit for 3 year: 0times deposit for 2 year: 0times deposit for 1 year: 0times Total:8841.01 可见最佳的存款方案为连续四次存 5 年期。

fixed fixed fixed fixed fixed

*思考题 某单位对职工出售住房,每套为 2 万元。买房付款的方法是: 一次交清,优惠 20% 从第一年开始,每年年初分期付款: 5 年交清,优惠 50%; 10 年交清,优惠 10%; 20 年交清,没有优惠。 现在有人手中正好有 2 万元, 若假定在今后 20 年中物价和银行利率均保持不变, 问他应当选择哪种付款方式可以使应付的钱最 少? ----------------------------------------------------------------------------------14. 15.捕鱼和分鱼 作者:huang01 发布时间:2004-10-21 17:01:57

A、B、C、D、E 五个人在某天夜里合伙去捕鱼,到第二天凌晨时都疲惫不堪,于是各自找地方睡觉。日上三杆,A 第一个醒来, 他将鱼分为五份,把多余的一条鱼扔掉,拿走自己的一份。B 第二个醒来,也将鱼分为五份,把多余的一条鱼扔掉,保持走自己的 一份。C、D、E 依次醒来,也按同样的方法拿走鱼。问他们合伙至少捕了多少条鱼? *问题分析与算法设计 根据题意,总计将所有的鱼进行了五次平均分配,每次分配时的策略是相同的,即扔掉一条鱼后剩下的鱼正好分成五份,然后 拿走自己的一份,余下其它的四份。 假定鱼的总数为 X,则 X 可以按照题目的要求进行五次分配:X-1 后可被 5 整除,余下的鱼为 4*(X-1)、5。若 X 满足上述要求, 则 X 就是题目的解。 *程序与程序注释 #include<stdio.h> void main() { int n,i,x,flag=1; for(n=6;flag;n++) { for(x=n,i=1&&flag;i<=5;i++) if((x-1)%5==0) x=4*(x-1)/5; else flag=0; /*若不能分配则置标记 falg=0 退出分配过程*/ if(flag) break; /*若分配过程正常结束则找到结果退出试探的过程*/ else flag=1; /*否则继续试探下一个数*/ } printf("Total number of fish catched=%d\\n",n); } *运行结果 Total number of fish catched = 3121 *问题的进一步讨论 程序采用试探法,试探的初值为 6,每次试探的步长为 1。这是过分保守的做法。可以在进一步分析题目的基础上修改此值,增 大试探的步长值,以减少试探次数。 *思考题 25 /*输出结果*/

/*flag:控制标记*/ /*采用试探的方法。令试探值 n 逐步加大*/

请使用其它的方法求解本题 15. 16.出售金鱼

买卖提将养的一缸金鱼分五次出售系统上一次卖出全部的一半加二分之一条;第二次卖出余下的三分之一加三分之一条;第三 次卖出余下的四分之一加四分之一条;第四次卖出余下的五分之一加五分之一条;最后卖出余下的 11 条。问原来的鱼缸中共有几条 金鱼? *题目分析与算法设计 题目中所有的鱼是分五次出售的,每次卖出的策略相同;第 j 次卖剩下的(j+1)分之一再加 1/(j+1)条。第五次将第四次余下的 11 条全卖了。 假定第 j 次鱼的总数为 X,则第 j 次留下: x-(x+1)/(j+1) 当第四次出售完毕时,应该剩下 11 条。若 X 满足上述要求,则 X 就是题目的解。 应当注意的是:"(x+1)/(j+1)"应满足整除条件。试探 X 的初值可以从 23 开始,试探的步长为 2,因为 X 的值一定为奇数。 *程序说明与注释 #include<stdio.h> void main() { int i,j,n=0,x; for(i=23;n==0;i+=2) { for(j=1,x=i;j<=4&&x>=11;j++) /*完成出售四次的操作*/ if((x+1)%(j+1)==0) /*若满足整除条件则进行实际的出售操作*/ x-=(x+1)/(j+1); else {x=0;break;} if(j==5&&x==11) { printf("There are %d fishes at first.\\n",i); n=1; } } } *运行结果 There are 59 fishes at first. *思考题 日本著名数学游戏专家中村义作教授提出这样一个问题:父亲将 2520 个桔子分给六个儿子。分完后父亲说: “老大将分给你的 桔子的 1/8 给老二;老二拿到后连同原先的桔子分 1/7 给老三;老三拿到后连同原先的桔子分 1/6 给老四;老四拿到后连同原先的 桔子分 1/5 给老五;老五拿到后连同原先的桔子分 1/4 给老六;老六拿到后连同原先的桔子分 1/3 给老大” 。结果大家手中的桔子正 好一样多。问六兄弟原来手中各有多少桔子? /*输出结果*/ /*控制退出试探过程*/ /*否则停止计算过程*/ /*若第四次余下 11 条则满足题意*/

/*n 为标志变量*/ /*控制试探的步长和过程*/

16.

1.7 分数四则运算

对输入的两个分数进行+、-、*、/四则运算,输出分数结果。 算法分析如下: 对分数 b/a 与 d/c,不管哪一种运算,其运算结果均为 y/x 形式。对结果 y/x 进行化简,约去分子分母的公因数:试用 i(i=1,...,y) 对 y,x 进行试商,若能同时整除 y,x,则 y,x 同时约去公因数 i,最后打印约简的分数。 程序代码如下: #include<stdio.h> void main() { long int a,b,c,d,i,x,y,z; char op; printf("两分数 b/a,d/c 作+,-,*,/四则运算,结果为分数。\\n"); printf("请输入分数运算式。\\n"); scanf("%ld/%ld%c%ld/%ld",&b,&a,&op,&d,&c); 26

if(a==0||c==0) {printf("分母为 0 输入错误!");exit(0);} if(op==\'+\'){y=b*c+d*a;x=a*c;} /*运算结果均为 y/x*/ if(op==\'-\'){y=b*c-d*a,x=a*c;} if(op==\'*\'){y=b*d;x=a*c;} if(op==\'/\'){y=b/c;x=a/d;} z=x; if(x>y) z=y; i=z; while(i>1) /*y/x 分子分母约去公因数*/ { if(x%i==0&&y%i==0){x=x/i;y=y/i;continue;} i--; } printf("%ld/%ld%c%ld/%ld=%ld/%ld.\\n",b,a,op,d,c,y,x); } ----------------------------------------------------------------------------------17. 17.平分七筐鱼 作者:huang01 发布时间:2004-10-21 17:02:30

甲、乙、丙三位鱼夫出海打鱼,他们随船带了 21 只箩筐。当晚返航时,他们发现有七筐装满了鱼,还有七筐装了半筐鱼,另外 七筐则是空的,由于他们没有秤,只好通过目测认为七个满筐鱼的重量是相等的,7 个半筐鱼的重量是相等的。在不将鱼倒出来的 前提下,怎样将鱼和筐平分为三份? *问题分析与算法设计 根据题意可以知道:每个人应分得七个箩筐,其中有 3.5 筐鱼。采用一个 3*3 的数组 a 来表示三个人分到的东西。其中每个人 对应数组 a 的一行,数组的第 0 列放分到的鱼的整筐数,数组的第 1 列放分到的半筐数,数组的第 2 列放分到的空筐数。由题目可 以推出: 。数组的每行或每列的元素之和都为 7; 。对数组的行来说,满筐数加半筐数=3.5; 。每个人所得的满筐数不能超过 3 筐; 。每个人都必须至少有 1 个半筐,且半筐数一定为奇数 对于找到的某种分鱼方案,三个人谁拿哪一份都是相同的,为了避免出现重复的分配方案,可以规定:第二个人的满筐数等于 第一个人的满筐数;第二个人的半筐数大于等于第一个人的半筐数。 *程序与程序注释 #include<stdio.h> int a[3][3],count; void main() { int i,j,k,m,n,flag; printf("It exists possible distribtion plans:\\n"); for(i=0;i<=3;i++) /*试探第一个人满筐 a[0][0]的值,满筐数不能>3*/ { a[0][0]=i; for(j=i;j<=7-i&&j<=3;j++) { a[1][0]=j; if((a[2][0]=7-j-a[0][0])>3)continue; /*第三个人满筐数不能>3*/ if(a[2][0]<a[1][0])break; /*要求后一个人分的满筐数>=前一个人,以排除重复情况*/ for(k=1;k<=5;k+=2) /*试探半筐 a[0][1]的值,半筐数为奇数*/ { a[0][1]=k; for(m=1;m<7-k;m+=2) /*试探 半筐 a[1][1]的值,半筐数为奇数*/ 27 /*试探第二个人满筐 a[1][0]的值,满筐数不能>3*/

{ a[1][1]=m; a[2][1]=7-k-m; for(flag=1,n=0;flag&&n<3;n++) /*判断每个人分到的鱼是 3.5 筐,flag 为满足题意的标记变量*/ if(a[n][0]+a[n][1]<7&&a[n][0]*2+a[n][1]==7) a[n][2]=7-a[n][0]-a[n][1]; /*计算应得到的空筐数量*/ else flag=0; /*不符合题意则置标记为 0*/ if(flag) { printf("No.%d Full basket Semi--basket Empty\\n",++count); for(n=0;n<3;n++) printf(" fisher %c: %d %d %d\\n", \'A\'+n,a[n][0],a[n][1],a[n][2]); } } } } } } * 运行结果 It exists possible distribution plans: No.1 Full basket fisher A: 1 fisher B: 3 fisher C: 3 No.2 Full basket fisher A: 2 fisher B: 2 fisher C: 3 Semi--basket 5 1 1 Semi--basket 3 3 1 Empty 1 3 3 Empty 2 2 3

*思考题 晏会上数学家出了一道难题:假定桌子上有三瓶啤酒,癣瓶子中的酒分给几个人喝,但喝各瓶酒的人数是不一样的。不过其中 有一个人喝了每一瓶中的酒,且加起来刚好是一瓶,请问喝这三瓶酒的各有多少人? (答案:喝三瓶酒的人数分别是 2 人、3 人和 6 人) 18. 18.有限 5 位数

个位数为 6 且能被 3 整除的五位数共有多少? *题目分析与算法设计 根据题意可知,满足条件的五位数的选择范围是 10006、10016。。99996。可设基础数 i=1000,通过计算 i*10+6 即可得到欲 。 选的数(i 的变化范围是 1000~999),再判断该数能否被 3 整除。 *程序说明与注释 #include<stdio.h> void main() { long int i; int count=0; for(i=1000;i<9999;i++) if(!((i*10+6)%3)) count++;

/*count:统计满足条件的五位数的个数*/ /*判断所选的数能否被 3 整除*/ /*若满足条件则计数*/

printf("count=%d\\n",count); } *运行结果 count=2999

*思考题 28

求 100 到 1000 之间有多少个其数字之和为 5 的整数。 (答案:104,113,122,131,140,203,212,221,230,302,311,320,401,410,500)

19.

19. 8 除不尽的数

一个自然数被 8 除余 1,所得的商被 8 除也余 1,再将第二次的商被 8 除后余 7,最后得到一个商为 a。又知这个自然数被 17 除余 4,所得的商被 17 除余 15,最后得到一个商是 a 的 2 倍。求这个自然数。 *题目分析与算法设计 根据题意,可设最后的商为 i(i 从 0 开始取值),用逆推法可以列出关系式: (((i*8+7)*8)+1)*8+1=((2*i*17)+15)*18+4 再用试探法求出商 i 的值。 *程序说明与注释 #include<stdio.h> void main() { int i; for(i=0;;i++)

/*试探商的值*/

if(((i*8+7)*8+1)*8+1==(34*i+15)*17+4) { /*逆推判断所取得的当前 i 值是否满足关系式*/ /*若满足则输出结果*/ printf("The required number is: %d\\n",(34*i+15)*17+4); break; /*退出循环*/ } } *运行结果 The required number is:1993 20. 20.一个奇异的三位数

一个自然数的七进制表达式是一个三位数,而这个自然数的九进制表示也是一个三位数,且这两个三位数的数码正好相反,求 这个三位数。 *题目分析与算法设计 根据题意可知,七进制和九进制表示的这全自然数的每一位一定小于 7,可设其七进制数形式为 kji(i、j、k 的取值分别为 1~6), 然后设其九进制表示形式为 ijk。 *程序说明与注释 #include<stdio.h> void main() { int i,j,k; for(i=1;i<7;i++) for(j=0;j<7;j++) for(k=1;k<7;k++) if(i*9*9+j*9+k==i+j*7+k*7*7) { printf("The special number with 3 digits is:"); printf("%d%d%d(7)=%d%d%d(9)=%d(10)\\n",k,j,i,i,j,k,i*9*9+j*9+k); } } *运行结果 The special number with 3 digits is:503(7)=305(9)=248(10) ----------------------------------------------------------------------------------29 作者:huang01 发布时间:2004-10-21 17:03:08

21.

21.4 位反序数

设 N 是一个四位数,它的 9 倍恰好是其反序数,求 N。反序数就是将整数的数字倒过来形成的整数。例如:1234 的反序数是 4321。 *题目分析与算法设计 可设整数 N 的千、百、十、个位为 i、j、k、l,其取值均为 0~9,则满足关系式: (i*103+j*102+10*k+l)*9=(l*103+k*102+10*j+i) 的 i、j、k、l 即构成 N。 *程序说明与注释 #include<stdio.h> void main() { int i; for(i=1002;i<1111;i++)

/*穷举四位数可能的值*/

if(i%10*1000+i/10%10*100+i/100%10*10+i/1000==i*9) /*判断反序数是否是原整数的 9 倍*/ printf("The number satisfied stats condition is: %d\\n",i); /*若是则输出*/ } *运行结果 The number satisfied states condition is:1089 22. 22.求车速

一辆以固定速度行驶的汽车,司机在上午 10 点看到里程表上的读数是一个对称数(即这个数从左向右读和从右向左读是完全一 样的),为 95859。两小时后里程表上出现了一个新的对称数。问该车的速度是多少?新的对称数是多少? *题目分析与算法设计 根据题意,设所求对称数为 i,其初值为 95589,对其依次递增取值,将 i 值的每一位分解后与其对称位置上的数进行比较,若 每个对称位置上的数皆相等,则可判定 i 即为所求的对称数。 *程序说明与注释 #include<stdio.h> void main() { int t,a[5]; long int k,i; for(i=95860;;i++) { for(t=0,k=100000;k>=10;t++) { a[t]=(i%k)/(k/10); k/=10; } if((a[0]==a[4])&&(a[1]==a[3])) { printf("The new symmetrical number kelometers is:%d%d%d%d%d\\n", a[0],a[1],a[2],a[3],a[4]); printf("The velocity of the car is: %.2f\\n",(i-95859)/2.0); break; } } } *运行结果 The new symmetrical number kelometers is:95959. The velocity of the car is:50.00 *思考题 将一个数的数码倒过来所得到的新数叫原数的反序数。如果一个数等于它的反序数,则称它为对称数。求不超过 1993 的最大 的二进制的对称数 30 /*从高到低分解所取 i 值的每位数*/ /* 字,依次存放于 a[0]~a[5]中*/

/*数组 a 存放分解的数字位*/ /*以 95860 为初值,循环试探*/

23.

23.阿姆斯特朗数

如果一个正整数等于其各个数字的立方和,则称该数为阿姆斯特朗数(亦称为自恋性数)。 如 407=43+03+73 就是一个阿姆斯特朗数。试编程求 1000 以内的所有阿姆斯特朗数。 *题目分析与算法设计 可采用穷举法,依次取 1000 以内的各数(设为 i),将 i 的各位数字分解后,据阿姆斯特朗数的性质进行计算和判断。 *程序说明与注释 #include<stdio.h> void main() { int i,t,k,a[3]; printf("There are follwing Armstrong number smaller than 1000:\\n"); for(i=2;i<1000;i++) /*穷举要判定的数 i 的取值范围 2~1000*/ { for(t=0,k=1000;k>=10;t++) /*截取整数 i 的各位(从高向低位)*/ { a[t]=(i%k)/(k/10); /*分别赋于 a[0]~a[2}*/ k/=10; } if(a[0]*a[0]*a[0]+a[1]*a[1]*a[1]+a[2]*a[2]*a[2]==i) /*判断 i 是否为阿姆斯特朗数*/ printf("%5d",i); /*若满足条件,则输出*/ } printf("\\n"); } *运行结果 There are following Armstrong number smaller than 1000: 153 370 371 407 ----------------------------------------------------------------------------------24. 24.完全数 作者:huang01 发布时间:2004-10-21 17:03:40

如果一个数恰好等于它的因子之和,则称该数为“完全数” 。 *题目分析与算法设计 根据完全数的定义,先计算所选取的整数 a(a 的取值 1~1000)的因子,将各因子累加于 m,若 m 等于 a,则可确认 a 为完全数。 *程序说明与注释 #include<stdio.h> void main() { int a,i,m; printf("There are following perfect numbers smaller than 1000:\\n"); for(a=1;a<1000;a++) /*循环控制选取 1~1000 中的各数进行判断*/ { for(m=0,i=1;i<=a/2;i++) if(!(a%i))m+=i; if(m==a) printf("%4d ",a); } printf("\\n"); 31 /*计算 a 的因子,并将各因子之和 m=a,则 a 是完全数输出*/

} *运行结果 TThere are following perfect numbers smaller than 1000: 6 28 496 25. 26.亲密数

如果整数 A 的全部因子(包括 1,不包括 A 本身)之和等于 B;且整数 B 的全部因子(包括 1,不包括 B 本身)之和等于 A,则将整 数 A 和 B 称为亲密数。求 3000 以内的全部亲密数。 *题目分析与算法设计 按照亲密数定义,要判断数 a 是否有亲密数,只要计算出 a 的全部因子的累加和为 b,再计算 b 的全部因子的累加和为 n,若 n 等于 a 则可判定 a 和 b 是亲密数。计算数 a 的各因子的算法: 用 a 依次对 i(i=1~a/2)进行模运算,若模运算结果等于 0,则 i 为 a 的一个因子;否则 i 就不是 a 的因子。 *程序说明与注释 #include<stdio.h> void main() { int a,i,b,n; printf("There are following friendly--numbers pair smaller than 3000:\\n"); for(a=1;a<3000;a++) /*穷举 1000 以内的全部整数*/ { for(b=0,i=1;i<=a/2;i++) if(!(a%i))b+=i; /*计算数 a 的各因子,各因子之和存放于 b*/ /*计算 b 的各因子,各因子之和存于 n*/

for(n=0,i=1;i<=b/2;i++) if(!(b%i))n+=i; if(n==a&&a<b) printf("%4d..%4d ",a,b); } } *运行结果

/*若 n=a,则 a 和 b 是一对亲密数,输出*/

There are following friendly--numbers pair smaller than 3000: 220.. 284 1184.. 1210 2620.. 2924 26. 27.自守数

自守数是指一个数的平方的尾数等于该数自身的自然数。例如: 252=625 762=5776 93762=87909376 请求出 200000 以内的自守数 *题目分析与算法设计 若采用“求出一个数的平方后再截取最后相应位数”的方法显然是不可取的,因为计算机无法表示过大的整数。 分析手工方式下整数平方(乘法)的计算过程,以 376 为例: 376 被乘数 X 376 乘数 ---------2256 第一个部分积=被乘数*乘数的倒数第一位 2632 第二个部分积=被乘数*乘数的倒数第二位 1128 第三个部分积=被乘数*乘数的倒数第三位 ---------141376 积 本问题所关心的是积的最后三位。分析产生积的后三位的过程,可以看出,在每一次的部分积中,并不是它的每一位都会对积 的后三位产生影响。总结规律可以得到:在三位数乘法中,对积的后三位产生影响的部分积分别为: 第一个部分积中:被乘数最后三位*乘数的倒数第一位 第二个部分积中:被乘数最后二位*乘数的倒数第二位 第三个部分积中:被乘数最后一位*乘数的倒数第三位 将以上的部分积的后三位求和后截取后三位就是三位数乘积的后三位。这样的规律可以推广到同样问题的不同位数乘积。 按照手工计算的过程可以设计算法编写程序。 *程序说明与注释 #include<stdio.h> 32

void main() { long mul,number,k,ll,kk; printf("It exists following automorphic nmbers small than 200000:\\n"); for(number=0;number<200000;number++) { for(mul=number,k=1;(mul/=10)>0;k*=10); /*由 number 的位数确定截取数字进行乘法时的系数 k*/ kk=k*10; /*kk 为截取部分积时的系数*/ mul=0; /*积的最后 n 位*/ ll=10; /*ll 为截取乘数相应位时的系数*/ while(k>0) { mul=(mul+(number%(k*10))*(number%ll-number%(ll/10)))%kk; /*(部分积+截取被乘数的后 N 位*截取乘数的第 M 位),%kk 再截取部分积*/ k/=10; /*k 为截取被乘数时的系数*/ ll*=10; } if(number==mul) printf("%ld } } *运行结果 It exsts following automorphic numbners smaller than 200000: 0 1 5 6 25 76 376 625 9376 90625 27. 28.回文数 109376

/*判断若为自守数则输出*/ ",number);

打印所有不超过 n(取 n<256) 的其平方具有对称性质的数(也称回文数)。 *题目分析与算法设计 对于要判断的数 n,计算出其平方后(存于 a),将 a 的每一位进行分解,再按 a 的从低到高的顺序将其恢复成一个数 k(如 n=13, 则 a=169 且 k=961),若 a 等于 k 则可判定 n 为回亠数。 *程序说明与注释 #include<stdio.h> void main() { int m[16],n,i,t,count=0; long unsigned a,k; printf("No. number for(n=1;n<256;n++) { k=0;t=1;a=n*n; for(i=1;a!=0;i++) { m=a%10; a/=10; } for(;i>1;i--) { k+=m[i-1]*t; t*=10; } if(k==n*n) printf("%2d%10d%10d\\n",++count,n,n*n); } } *运行结果 33 /*计算 n 的平方*/ /*从低到高分解数 a 的每一位存于数组 m[1]~m[16]*/

it\'s square(palindrome)\\n"); /*穷举 n 的取值范围*/

No. number it\'s square(palindrome) 1 1 1 2 2 4 3 3 9 4 11 121 5 22 484 6 26 676 7 101 10201 8 111 12321 9 121 14641 ----------------------------------------------------------------------------------28. 29.求具有 abcd=(ab+cd)2 性质的四位数 作者:huang01 发布时间:2004-10-21 17:04:07

3025 这个数具有一种独特的性质:将它平分为二段,即 30 和 25,使之相加后求平方,即(30+25)2,恰好等于 3025 本身。请 求出具有这样性质的全部四位数。 *题目分析与算法设计 具有这种性质的四位数没有分布规律,可以采用穷举法,对所有四位数进行判断,从而筛选出符合这种性质的四位数。具体算 法实现,可任取一个四位数,将其截为两部分,前两位为 a,后两位为 b,然后套用公式计算并判断。 *程序说明与注释 #include<stdio.h> void main() { int n,a,b; printf("There are following number with 4 digits satisfied condition\\n"); for(n=1000;n<10000;n++) /*四位数 N 的取值范围 1000~9999*/ { a=n/100; /*截取 N 的前两位数存于 a*/ b=n%100; /*截取 N 的后两位存于 b*/ if((a+b)*(a+b)==n) /*判断 N 是否为符合题目所规定的性质的四位数*/ printf("%d } } *运行结果 There are following numbers with 4 digits satisfied condition: 2025 3025 9801 29. 30.求素数 ",n);

求素数表中 1~1000 之间的所有素数 *问题分析与算法设计 素数就是仅能衩 1 和它自身整除的整数。判定一个整数 n 是否为素数就是要判定整数 n 能否被除 1 和它自身之外的任意整数整 除,若都不能整除,则 n 为素数。 程序设计时 i 可以从 2 开始,到该整数 n 的 1/2 为止,用 i 依次去除需要判定的整数,只要存在可以整除该数的情况,即可确定 要判断的整数不是素数,否则是素数。 *程序与程序注释 #include<stdio.h> void main() { int n1,nm,i,j,flag,count=0; do{ printf("Input START and END=?"); scanf("%d%d",&n1,&nm);

/*输入求素数的范围*/ 34

}while(!(n1>0&&n1<nm));

/*输入正确的范围*/

printf("...........PRIME TABLE(%d--%d)............\\n",n1,nm); if(n1==1||n1==2) /*处理素数 2*/ { printf("%4d",2); n1=3;count++; } for(i=n1;i<=nm;i++) { if(!(i%2))continue; for(flag=1,j=3;flag&&j<i/2;j+=2) /*判定能否被从 3 到整数的一半中的某一数所整除*/ if(!(i%j))flag=0; /*若能整除则不是素数*/ if(flag) printf(++count%15?"%4d":"%4d\\n",i); } } 30. 31.歌德巴赫猜想 /*判定指定范围内的整数是否为素数*/

验证:2000 以内的正偶数都能够分解为两个素数之和(即验证歌德巴赫猜想对 2000 以内的正偶数成立)。 *问题分析与算法设计 为了验证歌德巴赫猜想对 2000 以内的正偶数都是成立的,要将整数分解为两部分,然后判断出分解出的两个整数是否均为素 数。若是,则满足题意;否则重新进行分解和判断。 程序中对判断是否为素数的算法进行了改进,对整数判断“用从 2 开始到该整数的一半”改为“2 开始到该整数的平方根” 。原 因何在请自行分析。 *程序与程序注释 #include<stdio.h> #include<math.h> int fflag(int n); void main() { int i,n; for(i=4;i<=2000;i+=2) { for(n=2;n<i;n++) if(fflag(n))

/*将偶数 i 分解为两个整数*/ /*分别判断两个整数是否均为素数*/

if(fflag(i-n)) { printf("%14d=%d+%d\\n",i,n,i-n); break; } if(n==i) } } int fflag(int i) { int j; if(i<=1)return 0; if(i==2)return 1; if(!(i%2))return 0; /*if no,return 0*/ for(j=3;j<=(int)(sqrt((double)i)+1);j+=2) if(!(i%j))return 0; return 1; /*if yes,return 1*/ } -------------------------------------------------------------------------------35 /*判断是否为素数*/ printf("error %d\\n",i);

/*若均是素数则输出*/

----

作者:huang01 发布时间:2004-10-21 17:05:18

31.

32.要发就发

“1898--要发就发” 。请将不超过 1993 的所有素数从小到大排成第一行,第二行上的每个素数都等于它右肩上的素数之差。编 程求出:第二行数中是否存在这样的若干个连续的整数,它们的和恰好是 1898?假好存在的话,又有几种这样的情况? 第一行:2 3 5 7 11 13 17......1979 1987 1993 第二行:1 2 2 4 2 4...... 8 6 *问题分析与算法设计: 首先从数学上分析该问题: 假设第一行中的素数为 n[1]、n[2]、n[3]....n、...第二行中的差值为 m[1]、m[2]、m[3]...m[j]...。其中 m[j]为: m[j]=n[j+1]-n[j]。 则第二行连续 N 个数的和为: SUM=m[1]+m[2]+m[3]+...+m[j] =(n[2]-n[1])+(n[3]-n[2])+(n[4]-n[3])+...+(n[j+1]-n[j]) =n[j+1]-n[1] 由此题目就变成了:在不超过 1993 的所有素数中是否存在这样两个素数,它们的差恰好是 1898。若存在,则第二行中必有所需整 数序列,其和恰为 1898, 。 对等价问题的求解是比较简单的。 由分析可知,在素数序列中不必包含 2,因为任意素数与 2 的差一定为奇数,所以不必考虑。 *程序与程序注释: #include<stdio.h> #include<math.h> #define NUM 320 int number[NUM];

/*存放不超过 1993 的全部奇数*/

int fflag(int i); void main() { int i,j,count=0; printf("there are follwing primes sequences in first row:\\n"); for(j=0,i=3;i<=1993;i+=2) /*求出不超过 1993 的全部奇数*/ if(fflag(i)) number[j++]=i; for(j--;number[j]>1898;j--) /*从最大的素数开始向 1898 搜索*/ { for(i=0;number[j]-number>1898;i++); /*循环查找满足条件的素数*/ if(number[j]-number==1898) /*若两个素数的差为 1898,则输出*/ printf("(%d).%3d,.....,%d\\n",++count,number,number[j]); } } int fflag(int i) { int j; if(i<=1) return 0;

/*判断是否为素数*/

if(i==2) return 1; if(!(i%2)) return 0; /*if no, return 0*/ for(j=3;j<=(int)(sqrt((double)i)+1);j+=2) if(!(i%j)) return 0; return 1; } *运行结果 There are follwing primes sequences in first row: (1).89,......,1987 (2).53,......,1951 (3). 3,......,1901 36

*思考题 将 1,2,3,。 。。,20 这 20 个连续的自然数排成一圈,使任意两个相邻的自然数之和均为素数。

32.

35.素数幻方

求四阶的素数幻方。即在一个 4X4 的矩阵中,每一个格填 入一个数字,使每一行、每一列和两条对角线上的 4 个数字所组成 的四位数,均为可逆素数。 *问题分析与算法设计 有了前面的基础,本题应当说是不困难的。 最简单的算法是:采用穷举法,设定 4X4 矩阵中每一个元素的值后,判断每一行、每一列和两条对角线上的 4 个数字组成的四 位数是否都是可逆素数,若是则求出了满足题意的一个解。 这种算法在原理是对的,也一定可以求出满足题意的全部解。但是,按照这一思路编出的程序效率很低,在微机上几个小时也 不会运行结束。这一算法致命的缺陷是:要穷举和判断的情况过多。 充分利用题目中的“每一个四位数都是可逆素数”这一条件,可以放弃对矩阵中每个元素进行的穷举的算法,先求出全部的四 位可逆素数(204 个),以矩阵的行为单位,在四位可逆素数的范围内进行穷举,然后将穷举的四位整数分解为数字后,再进行列和对 角线方向的条件判断,改进的算法与最初的算法相比,大大地减少了穷举的次数。 考虑矩阵的第一行和最后一行数字,它们分别是列方向四位数的第一个数字和最后一个数字,由于这些四位数也必须是可逆素 数,所以矩阵的每一行和最后一行中的各个数字都不能为偶数或 5。这样穷举矩阵的第一行和最后一行时,它们的取值范围是:所 有位的数字均不是偶数或 5 的四位可逆数。由于符合这一条件的四位可逆素数很少,所以这一范围限制又一次减少了穷举的次数。 对算法的进一步研究会发现:当设定了第一和第二行的值后,就已经可以判断出当前的这种组合是否一定是错误的(尚不能肯定 该组合一定是正确的)。若按列方向上的四个两位数与四位可逆数的前两位矛盾(不是其中的一种组合),则第一、二行的取值一定是 错误的。同理在设定了前三行数据后,可以立刻判断出当前的这种组合是否一定是错误的,若判断出矛盾情况,则可以立刻设置新 的一组数据。这样就可以避免将四个数据全部设定好以后再进行判断所造成的低效。 根据以上分析,可以用伪语言描述以上改进的算法: 开始 找出全部四位的可逆素数; 确定全部出现在第一和最后一行的四位可逆素数; 在指定范围 内穷举第一行 在指定范围内穷举第二行 若第一、第二、三行已出现矛盾,则继续穷举下一个数; 在指定范围内穷举第四行 判断列和对角方向是否符合题意 若符合题意,则输出矩阵; 否则继续穷举下一个数; 结束 在实际编程中,采用了很多程序设计技巧,假如设置若干辅助数组,其目的就是要最大限度的提高程序的执行效率,缩短运行 时间。下面的程序运行效率是比较高的。 *程序与程序注释 #include<stdio.h> #include<math.h> int number[210][5]; int select[110]; int array[4][5]; int count; int selecount; int larray[2][200]; int lcount[2]; int num(int number); int ok(int number); void process(int i); void copy_num(int i); int comp_num(int n); int find1(int i); 37

/*存放可逆素数及素数分解后的各位数字*/ /*可以放在矩阵第一行和最后一行的素数的下标*/ /*4X4 的矩阵,每行 0 号元素存可逆素数对应的数组下标*/ /*可逆素数的数目*/ /*可以放在矩阵第一行和最后一行的可逆素数的数目*/ /*存放素数前二、三位数的临时数组所对应的数量计数器*/

int find2(void); int find0(int num); void p_array(void);

void main() { int i,k,flag,cc=0,i1,i4; printf("there are magic squares with invertable primes as follw:\\n"); for(i=1001;i<9999;i+=2) /*求满足条件的可逆素数*/ { k=i/1000; if(k%2!=0&&k!=5&&num(i)) { number[count][0]=i; /*存入数组*/ process(count++); /*分解素数的各位数字*/ if(number[count-1][2]%2!=0&& /*若可逆素数满足放在矩阵第一行*/ number[count-1][3]%2!=0&& /*和最后一行的条件,记录可逆素数的*/ number[count-1][2]!=5&& /*下标,计数器加 1*/ number[count-1][3]!=5) select[selecount++]=count-1; } } larray[0][lcount[0]++]=number[0][0]/100; /*临时数组的第一行存前二位*/ larray[1][lcount[1]++]=number[0][0]/10; /*临时数组的第二行存前三位*/ for(i=1;i<count;i++) /*将素数不重复的前二、三位存入临时数组中*/ { if(larray[0][lcount[0]-1]!=number[0]/100) larray[0][lcount[0]++]=number[0]/100; if(larray[1][lcount[1]-1]!=number[0]/10) larray[1][lcount[1]++]=number[0]/10; } for(i1=0;i1<selecount;i1++) { array[0][0]=select[i1]; /*取对应的素数下标*/ copy_num(0); /*复制分解的素数*/ for(array[1][0]=0;array[1][0]<count;array[1][0]++) /*穷举第二行*/ { copy_num(1); /*复制分解的数字*/ if(!comp_num(2)) continue; /*若每列的前两位的组成与素数相矛盾,则试探下一个数*/ for(array[2][0]=0;array[2][0]<count;array[2][0]++) /*穷举第三行*/ { copy_num(2); /*复制分解的数字*/ if(!comp_num(3)) continue; /*若每列的前三位的组成与素数相矛盾,则试探下一个数*/ for(i4=0;i4<selecount;i4++) /*在最后一行允许的范围内穷举*/ { array[3][0]=select[i4]; copy_num(3); /*复制分解的数字*/ for(flag=1,i=1;flag&&i<=4;i++) /*判断每列是否可逆素数*/ if(!find1(i))flag=0; if(flag&&find2()) /*判断对角线是否为可逆素数*/ { printf("No.%d\\n",++cc); p_array(); } /*输出幻方矩阵*/ } } } 38 /*在第一行允许的汇聚围内穷举*/ /*若可逆素数的第一位不是偶数或 5*/

} } int num(int number) { int j; if(!ok(number)) return 0; for(j=0;number>0;number/=10) j=j*10+number%10; if(!ok(j)) return 0; return 1; } int ok(int number) { int i,j; if(number%2==0) return 0; j=sqrt((double)number)+1; for(i=3;i<=j;i+=2) if(number%i==0) return 0; return 1; } void process(int i) { int j,num; num=number[0]; for(j=4;j>=1;j--,num/=10) number[j]=num%10; } void copy_num(int i) { int j; for(j=1;j<=4;j++) array[j]=number[array[0>[j]; } int comp_num(int n) { static int ii; /*用内部静态变量保存前一次查找到的元素下标*/ static int jj; /*ii:前一次查找前二位的下标,jj:前一次查找前三位的下标*/ int i,num,k,*p; /*p:指向对应的要使用的前一次下标 ii 或 jj*/ int *pcount; /*pcount:指向要使用的临时数组数量的计数器*/ switch(n){ /*根据 n 的值选择对应的一组控制变量*/ case 2:pcount=&lcount[0];p=&ii;break; case 3:pcount=&lcount[1];p=&jj;break; default:return 0; } for(i=1;i<=4;i++) { for(num=0,k=0;k<n;k++) /*计算前 n 位数字代表的数值*/ num=num*10+array[k]; if(num<=larray[n-2][*p]) /*与前一次最后查找到的元素进行比较*/ for(;*p>=0&&num<larray[n-2][*p];(*p)--);/*若前次查找到的元素大,则向前找*/ else for(;p<pcount&&num>larray[n-2][*p];(*p)++); /*否则向后找*/ 39 /*对四列分别进行处理*/ /*判断 array 中每列的前 n 位是否与可逆素数允许的前 n 位矛盾*/ /*将 array[0]指向的素数的各位数字复制到 array 中*/ /*将第 i 个整数分解为数字并存入数组*/ /*判断是否为素数*/ /*判断是否可逆素数*/

/*将素数变为反序数*/

/*判断反序数是否为素数*/

if(*p<0||*p>=*pcount) { *p=0; return 0; } if(num!=larray[n-2][*p]) return 0; } return 1; }

/*前 n 位不是可逆素数允许的值则返回 0*/

int find1(int i) /*判断列方向是否是可逆素数*/ { int num,j; for(num=0,j=0;j<4;j++) num=num*10+array[j]; return find0(num); } int find2(void) { int num1,num2,i,j; for(num1=0,j=0;j<4;j++) num1=num1*10+array[j][j+1]; for(num2=0,j=0,i=4;j<4;j++,i--) num2=num2*10+array[j]; if(find0(num1)) return(find0(num2)); else return 0; } int find0(int num) { static int j; if(num<=number[j][0])for(;j>=0&&num<number[j][0];j--); else for(;j<count&&num>number[j][0];j++); if(j<0||j>=count){ j=0;return 0; } if(num==number[j][0]) return 1; else return 0; } void p_array(void) { int i,j; for(i=0;i<4;i++) { for(j=1;j<=4;j++) printf("%d ",array[j]); printf("\\n"); } } ----------------------------------------------------------------------------------33. 36.百钱百鸡问题 作者:huang01 发布时间:2004-10-21 17:06:06 /*输出矩阵*/ /*查找是否为满足要求的可逆素数*/ /*判断对角线方向是否是可逆素数*/

中国古代数学家张丘建在他的《算经》中提出了著名的“百钱买百鸡问题” :鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱 40

一,百钱买百鸡,问翁、母、雏各几何? *题目分析与算法设计 设鸡翁、鸡母、鸡雏的个数分别为 x,y,z,题意给定共 100 钱要买百鸡,若全买公鸡最多买 20 只,显然 x 的值在 0~20 之间; 同理,y 的取值范围在 0~33 之间,可得到下面的不定方程: 5x+3y+z/3=100 x+y+z=100 所以此问题可归结为求这个不定方程的整数解。 由程序设计实现不定方程的求解与手工计算不同。在分析确定方程中未知数变化范围的前提下,可通过对未知数可变范围的穷 举,验证方程在什么情况下成立,从而得到相应的解。 *程序说明与注释 #include<stdio.h> void main() { int x,y,z,j=0; printf("Folleing are possible plans to buy 100 fowls with 100 Yuan.\\n"); for(x=0;x<=20;x++) /*外层循环控制鸡翁数*/ for(y=0;y<=33;y++) /*内层循环控制鸡母数 y 在 0~33 变化*/ { z=100-x-y; /*内外层循环控制下,鸡雏数 z 的值受 x,y 的值的制约*/ if(z%3==0&&5*x+3*y+z/3==100) /*验证取 z 值的合理性及得到一组解的合理性*/ printf("%2d:cock=%2d hen=%2d chicken=%2d\\n",++j,x,y,z); } } *运行结果 Follwing are possible plans to buy 100 fowls with 100 Yuan. 1:cock=0 hen=25 chicken=75 2:cock=4 hen=18 chicken=78 3:cock=8 hen=11 chicken=81 4:cock=12 hen=4 chicken=84 *总是的进一步讨论 这类求解不定方程总理的实现,各层循环的控制变量直接与方程未知数有关,且采用对未知数的取值范上穷举和组合的方法来 复盖可能得到的全部各组解。能否根据题意更合理的设置循环控制条件来减少这种穷举和组合的次数,提高程序的执行效率,请读 者考虑。 37.爱因斯坦的数学题 爱因斯坦出了一道这样的数学题:有一条长阶梯,若每步跨 2 阶,则最最后剩一阶,若每步跨 3 阶,则最后剩 2 阶,若每步跨 5 阶,则最后剩 4 阶,若每步跨 6 阶则最后剩 5 阶。只有每次跨 7 阶,最后才正好一阶不剩。请问这条阶梯共有多少阶? *题目分析与算法设计 根据题意,阶梯数满足下面一组同余式: x≡1 (mod2) x≡2 (mod3) x≡4 (mod5) x≡5 (mod6) x≡0 (mod7) *程序说明与注释 #include<stdio.h> void main() { int i=1;

/*i 为所设的阶梯数*/

while(!((i%2==1)&&(i%3==2)&&(i%5==4)&&(i%6==5)&&(i%7==0))) ++i; /*满足一组同余式的判别*/ printf("Staris_number=%d\\n",i); } *运行结果 Staris_number=119 *问题的进一步讨论 41

此题算法还可考虑求 1、2、4、5 的最小公倍数 n,然后判 t(t 为 n-1)≡0(mod7)是否成立,若不成立则 t=t+n,再进行判别,直 至选出满足条件的 t 值。请自行编写程序实现。 39.年龄几何 张三、李四、王五、刘六的年龄成一等差数列,他们四人的年龄相加是 26,相乘是 880,求以他们的年龄为前 4 项的等差数列 的前 20 项。 *题目分析与算法设计 设数列的首项为 a, 则前 4 项之和为"4*n+6*a",前 4 项之积为"n*(n+a)*(n+a+a)*(n+a+a+a)"。 同时"1<=a<=4","1<=n<=6"。 可采用穷举法求出此数列。 *程序说明与注释 #include<stdio.h> void main() { int n,a,i; printf("The series with equal difference are:\\n"); for(n=1;n<=6;n++) /*公差 n 取值为 1~6*/ for(a=1;a<=4;a++) /*首项 a 取值为 1~4*/ if(4*n+6*a==26&&n*(n+a)*(n+a+a)*(n+a+a+a)==880) for(i=0;i<20;i++) printf("%d ",n+i*a); } *运行结果 The series with equal difference are: 2 5 8 11 14 17 20 23 26 29 32 35 38 41 44 47 50 53 56 59 38.换分币 用一元人民币兑换成 1 分、2 分和 5 分硬币,共有多少种不同的兑换方法。 *题目分析与算法设计 根据题意设 i,j,k 分别为兑换的 1 分、2 分、5 分硬币所具有的钱数(分),则 i,j,k 的值应满足: i+j+k=100 *程序说明与注释 #include<stdio.h> void main() { int i,j,k,count=1; printf("There are follwing small exchange plans for 1 Yuan note:\\n"); for(i=0;i<=100;i++) /*i 为 1 分硬币钱数,可取值 0,1,2...,100*/ for(j=0;j<=100-i;j+=2) /*j 为 2 分硬币钱数,可取 0 值,2,4,...,100*/ for(k=0;k<=100-i-2*j;k+=5) /*k 为 5 分硬币钱数*/ if(i+j+k==100) printf(count%4?"%d:1*%d+2*%d+5*%d\\t":"%d:1*%d+2*%d+5*%d\\n",count++,i,j/2,k/5); } 40.三色球问题 若一个口袋中放有 12 个球,其中有 3 个红的。3 个白的和 6 个黒的,问从中任取 8 个共有多少种不同的颜色搭配? *题目分析与算法设计 设任取的红球个数为 i,白球个数为 j,则黒球个数为 8-i-j,根据题意红球和白球个数的取值范围是 0~3,在红球和白球个数确 定的条件下,黒球个数取值应为 8-i-j<=6。 *程序说明与注释 #include<stdio.h> void main() { int i,j,count=0; printf(" RED BALL WHITE BALL BLACKBALL\\n"); printf("..................................................\\n"); for(i=0;i<=3;i++) /*循环控制变量 i 控制任取红球个数 0 ̄3*/ for(j=0;j<=3;j++) /*循环控制变量 j 控制任取白球个数 0 ̄3*/ if((8-i-j)<=6) 42

/*判断结果*/

/*输出前 20 项*/

printf(" %2d: } 34. 41.马克思手稿中的数学题

%d

%d

%d\\n",++count,i,j,8-i-j);

马克思手稿中有一道趣味数学问题:有 30 个人,其中有男人、女人和小孩,在一家饭馆吃饭花了 50 先令;每个男人花 3 先令, 每个女人花 2 先令,每个小孩花 1 先令;问男人、女人和小孩各有几人? *题目分析与算法设计 设 x,y,z 分别代表男人、女人和小孩。按题目的要求,可得到下面的方程: x+y+z=30 (1) 3x+2y+z=50 (2) 用方程程序求此不定方程的非负整数解,可先通过(2)-(1)式得: 2x+y=20 (3) 由(3)式可知,x 变化范围是 0~10 *程序说明与注释 #include<stdio.h> void main() { int x,y,z,count=0; printf(" Men Women Children\\n"); printf("........................................\\n"); for(x=0;x<=10;x++) { y=20-2*x; /*x 定值据(3)式求 y*/ z=30-x-y; /*由(1)式求 z*/ if(3*x+2*y+z==50) /*当前得到的一组解是否满足式(2)*/ printf(" %2d: %d %d %d\\n",++count,x,y,z); } } 42.最大公约数和最小公倍数 求任意两个正整数的最大公约数和(GCD)和最小公倍数(LCM) *问题分析与算法设计 手工方式求两个正整数的蝚大公约数的方法是用辗转相除法,在程序中可以模拟这种方式。 *程序与程序注释 #include<stdio.h> void main() { int a,b,num1,num2,temp; printf("Input a & b:"); scanf("%d%d",&num1,&num2); if(num1>num2) /*找出两个数中的较大值*/ { temp=num1; num1=num2; num2=temp; } a=num1; b=num2; while(b!=0) { temp=a%b; a=b; b=temp; } printf("The GCD of %d and %d is: %d\\n",num1,num2,a); /*输出最大公约数*/ printf("The LCM of them is: %d\\n",num1*num2/a); /*输出最小公倍数*/ } *运行结果 1.Input a & b: 20 55 The GCD of 20 and 55 is: 5 The LCM of them is: 220 43 /*交换两个整数*/

/*采用辗转相除法求最大公约数*/

2.Input a & b: 17 71 The GCD of 17 and 71 is: 1 The LCM of them is: 1207 3.Input a & b: 24 88 The GCD of 24 and 88 is: 8 The LCM of them is: 264 4.Input a & b: 35 85 The GCD of 35 and 85 is: 5 The LCM of them is: 595 43.分数比较 比较两个分数的大小。 *问题分析与算法设计 人工方式下比较分数大小最常用的方法是:进行分数的通分后比较分子的大小。可以编程模拟手式方式。 *程序与程序注释 #include<stdio.h> int zxgb(int a,int b); void main() { int i,j,k,l,m,n; printf("Input two FENSHU:\\n"); scanf("%d/%d,%d/%d",&i,&j,&k,&l); /*输入两个分数*/ m=zxgb(j,l)/j*i; /*求出第一个分数通分后的分子*/ n=zxgb(j,l)/l*k; /*求出第二个分数通分后的分子*/ if(m>n) printf("%d/%d>%d/%d\\n",i,j,k,l); /*比较分子的大小*/ else if(m==n) printf("%d/%d=%d/%d\\n",i,j,k,l); /*输出比较的结果*/ else } int zxgb(int a,int b) { long int c; int d; if(a<b) c=a,a=b,b=c; for(c=a*b;b!=0;) { d=b; b=a%b; } return (int)c/a; printf("%d/%d<%d/%d\\n",i,j,k,l);

/*若 a<b,则交换两变量的值*/

a=d;

} *运行结果 输入: 4/5,6/7 输入: 8/4,16/32 输入:16/32,4/8 35. 44.分数之和

输出: 4/5<6/7 输出: 8/4>16/32 输出: 16/32=4/8

求这样的四个自然数 p,q,r,s(p<=q<=r<=s),使得以下等式成立: 1/p+1/q+1/r+1/s+1

*问题分析与算法设计 若规定 p<=q<=r<=s,将原式通分、化简并整理后得到: 2<=p<5 p<=q<7 q<r<13 采用最简单的穷举方法可以很方便的求解。 程序与程序注释: 44

#include<stdio.h> void main() { int p,q,r,s,count=0; printf("The 4 fractions which sum is equal 1 are:\\n"); for(p=2;p<5;p++) /*穷举分母*/ for(q=p;q<7;q++) for(r=q;r<13;r++) if(p*q*r-q*r-p*r-p*q!=0) { s=(p*q*r)/(p*q*r-q*r-p*r-p*q); /*求出 s 的值*/ if(!((p*q*r)%(p*q*r-q*r-p*r-p*q))&&s>=r) printf("[%2d] 1/%d+1/%d+1/%d+1/%d=1\\n",++count,p,q,r,s); /*输出结果*/ } } ----------------------------------------------------------------------------------36. 45.将真分数分解为埃及分数 作者:huang01 发布时间:2004-10-21 17:06:39

分子为 1 的分数称为埃及分数,现输入一个真分数,请将该分数分解为埃及分数。 如:8/11=1/2+1/5+1/55+1/110。 *问题分析与算法设计 若真分数的分子 a 能整除分母 b,则真分数经过化简就可以得到埃及分数,若真分数的分子不能整除分母,则可以从原来的分 数中分解出一个分母为 b/a+1 的埃及分数。用这种方法将剩余部分反复分解,最后可得到结果。 *程序与程序注释 #include<stdio.h> void main() { long int a,b,c; printf("Please enter a optional fraction(a/b):"); scanf("%ld/%ld",&a,&b); /*输入分子 a 和分母 b*/ printf("It can be decomposed t"); while(1) { if(b%a) /*若分子不能整除分母*/ c=b/a+1; /*则分解出一个分母为 b/a+1 的埃及分数*/ else{ c=b/a; a=1;} /*否则,输出化简后的真分数(埃及分数)*/ if(a==1) { printf("1/%ld\\n",c); break; /*a 为 1 标志结束*/ } else printf("1/%ld + ",c); a=a*c-b; /*求出余数的分子*/ b=b*c; /*求出余数的分母*/ if(a==3) /*若余数为 3,输出最后两个埃及分数*/ { } } *运行结果 45 printf("1/%ld + 1/%ld\\n",b/2,b); break;}

1. Please enter a optional fraction (a/b): 1/6 It can be decomposed t 1/6 2. Please enter a optional fraction (a/b): 20/33 It can be decomposed t 1/2+1/10+1/165 3. Please enter a optional fraction (a/b): 10/89 It can be decomposed t 1/9+1/801 4. Please enter a optional fraction (a/b): 19/99 It can be decomposed t 1/6+1/40+1/3960 5. Please enter a optional fraction (a/b): 8/89 It can be decomposed t 1/11+1/957 37. 46.列出真分数序列

按递增顺序依次列出所有分母为 40,分子小于 40 的最简分数。 *问题分析与算法设计 对分子采用穷举法,利用最大公约数的方法,判断分子与 40 是否构成真分数。 *程序与程序注释 #include<stdio.h> void main() { int i,num1,num2,temp; printf("The fraction serials with demominator 40 is:\\n"); for(i=1;i<=40;i++) /*穷举 40 以内的全部分子*/ { num1=40; num2=i; while(num2!=0) { temp=num1%num2; num1=num2; num2=temp; } if(num1==1) printf("%d/40 ",i); /*若最大公约数为 1,则为最简真分数*/

/*采用辗转相除法求出最大公约数*/

} } *运行结果 The fraction serials with demominator 40 is: 1/40 3/40 7/40 9/40 11/40 21/40 23/40 27/40 29/40 31/40

13/40 33/40

17/40 37/40

19/40 39/40

*思考题 按递增顺序依次列出所有分母小于等于 40 的最简真分数

----------------------------------------------------------------------------------38. 47.计算分数的精确值 作者:huang01 发布时间:2004-10-21 17:08:53

使用数组精确计算 M/N(0<M<N<=100)的值。如果 M/N 是无限循环小数,则计算并输出它的第一循环节,同时要求输出 循环 节的起止位置(小数位的序号) *问题分析与算法设计 46

由于计算机字长的限制,常规的浮点运算都有精度限制,为了得到高精度的计算结果,就必须自行设计实现方法。 为了实现高精度的计算,可将商存放在一维数组中,数组的每个元素存放一位十进制数,即商的第一位存放在第一个元素中, 商的第二位存放在第二个元素中....,依次类推。这样就可以使用数组不表示一个高精度的计算结果。 进行除法运算时可以模拟人的手工操作,即每次求出商的第一位后,将余数乘以 10,再计算商的下一位,重复以上过程,当某 次计算后的余数为 0 时,表示 M/N 为有限不循环小数某次计算后的余数与前面的某个余数相同时,则 M/N 为无限循环小数,从该 余数第一次出现之后所求得的各位数就是小数的循环节。 程序具体实现时,采用了数组和其它一些技巧来保存除法运算所得到的余数和商的各位数。 *程序与程序注释 #include<stdio.h> int remainder[101],quotient[101]; /*remainder:存放除法的余数; quotient:依次存放商的每一位*/

void main() { int m,n,i,j; printf("Please input a fraction(m/n)(<0<m<n<=100):"); scanf("%d/%d",&m,&n); /*输入被除数和除数*/ printf("%d/%d it\'s accuracy value is:0.",m,n); for(i=1;i<=100;i++) /*i: 商的位数*/ { remainder[m]=i; m*=10; quotient=m/n; m=m%n; if(m==0) { for(j=1;j<=1;j++) printf("%d",quotient[j]); break; /*退出循环*/ } if(remainder[m]!=0) { for(j=1;j<=i;j++) printf("%d",quotient[j]); /*则输出循环小数*/ printf("\\n\\tand it is a infinite cyclic fraction from %d\\n",remainder[m]); printf("\\tdigit to %d digit after decimal point.\\n",i); /*输出循环节的位置*/ break; /*退出*/ } } } ----------------------------------------------------------------------------------39. 51.谁是窃贼 作者:huang01 发布时间:2004-10-21 17:09:40 /*输出商*/ /*m:除的余数 remainder[m]:该余数对应的商的位数*/ /*余数扩大 10 位*/ /*商*/ /*求余数*/ /*余数为 0 则表示是有限小数*/

/*若该余数对应的位在前面已经出现过*/

公安人员审问四名窃贼嫌疑犯。已知,这四人当中仅有一名是窃贼,还知道这四人中每人要么是诚实的,要么总是说谎的。在 回答公安人员的问题中: 甲说: “乙没有偷,是丁偷的。 ” 乙说: “我没有偷,是丙便的。 ” 丙说: “甲没有偷,是乙偷的。 ” 丁说: “我没有偷。 ” 请根据这四人的答话判断谁是盗窃者。 *问题分析与算法设计 假设 A、B、C、D 分别代表四个人,变量的值为 1 代表该人是窃贱。 由题目已知:四人中仅有一名是窃贱,且这四个人中的每个人要么说真话,要么说假话,而由于甲、乙、丙三人都说了两句话: 47

“X 没偷,X 偷了” ,故不论该人是否说谎,他提到的两人中必有一人是小偷。故在列条件表达式时,可以不关心谁说谎,谁说实话。 这样,可以列出下列条件表达式: 甲说: ”乙没有偷,是丁偷的。 ” B+D=1 乙说: “我没有偷,是丙偷有。 ” B+C=1 丙说: “甲没有偷,是乙偷的。 ” A+B=1 丁说: “我没有偷。 ” A+B+C+D=1 其中丁只说了一句话,无法判定其真假,表达式反映了四人中仅有一名是窃贱的条件。 *程序与程序注释 #include<stdio.h> void main() { int i,j,a[4]; for(i=0;i<4;i++) { for(j=0;j<4;j++) /*将第 i 个人设置为 1 表示窃贱,其余为 0*/ if(j==i)a[j]=1; else a[j]=0; if(a[3]+a[1]==1&&a[1]+a[2]==1&&a[0]+a[1]==1) { printf("The thief is "); for(j=0;j<=3;j++) if(a[j])printf("%c.",j+\'A\'); printf("\\n"); } } } *运行结果 The thief is B. /*成立*/ /*输出计算结果*/

/*假定只有第 i 个人为窃贱*/

/*判断条件是否成立*/

(乙为窃贱。)

---------------------------------------------------40. 52.黑与白

有 A、B、C、D、E 五人,每人额头上都帖了一张黑或白的纸。五人对坐,每人都可以看到其它人额头上的纸的颜色。五人相互 观察后, A 说: “我看见有三人额头上帖的是白纸,一人额头上帖的是黑纸。 ” B 说: “我看见其它四人额头上帖的都是黑纸。 ” C 说: “我看见一人额头上帖的是白纸,其它三人额头上帖的是黑纸。 ” D 说: “我看见四人额头上帖的都是白纸。 ” E 什么也没说。 现在已知额头上帖黑纸的人说的都是谎话,额头帖白纸的人说的都是实话。问这五人谁的额头是帖白纸,谁的额头是帖黑纸? *问题分析与算法设计 假如变量 A、B、C、D、E 表示每个人额头上所帖纸的颜色,0 代表是黑色,1 代表是白色。根据题目中 A、B、C、D 四人所说 的话可以总结出下列关系: A 说: a&&b+c+d+e==3||!a&&b+c+d+e!=3 B 说: b&&a+c+d+e==0||!b&&a+c+d+e!=0 C 说: c&&a+b+d+e==1||!c&&a+b+d+e!=1 D 说: d&&a+b+c+e==4||!d&&a+b+c+e!=4 穷举每个人额头所帖纸的颜色的所有可能的情况,代入上述表达式中进行推理运算,使上述表达式为“真”的情况就是正确的 结果。 *程序与程序注释 #include<stdio.h> void main() { int a,b,c,d,e; for(a=0;a<=1;a++)

/*黑色:0

白色:1*/ 48

for(b=0;b<=1;b++)

/*穷举五个人额头帖纸的全部可能*/

for(c=0;c<=1;c++) for(d=0;d<=1;d++) for(e=0;e<=1;e++) if((a&&b+c+d+e==3||!a&&b+c+d+e!=3) &&(b&&a+c+d+e==0||!b&&a+c+d+e!=0) &&(c&&a+b+d+e==1||!c&&a+b+d+e!=1) &&(d&&a+b+c+e==4||!d&&a+b+c+e!=4)) { printf("A is pasted a piece of %s paper on his forehead.\\n", a?"white":"black"); printf("B is pasted a piece of %s paper on his forehead.\\n", b?"white":"black"); printf("C is pasted a piece of %s paper on his forehead.\\n", c?"white":"black"); printf("D is pasted a piece of %s paper on his forehead.\\n", d?"white":"black"); printf("E is pasted a piece of %s paper on his forehead.\\n", e?"white":"black"); } } *运行结果 A is pasted a paper of black paper on his forehead. B is pasted a paper of black paper on his forehead. C is pasted a paper of white paper on his forehead. D is pasted a paper of black paper on his forehead. E is pasted a paper of white paper on his forehead

(黑) (黑) (白) (黑) (白)

----------------------------------------------------------------------------------41. 53.迷语博士的难题(1) 作者:huang01 发布时间:2004-10-21 17:10:39

诚实族和说谎族是来自两个荒岛的不同民族,诚实族的人永远说真话,而说谎族的人永远说假话。迷语博士是个聪明的人,他 要来判断所遇到的人是来自哪个民族的。 迷语博士遇到三个人,知道他们可能是来自诚实族或说谎族的。为了调查这三个人是什么族的,博士分别问了他们的问题,这 是他们的对话: 问第一个人: “你们是什么族?” ,答: “我们之中有两个来自诚实族。 ”第二个人说: “不要胡说,我们三个人中只有一个是诚实 族的。 ”第三个人听了第二个人的话后说: “对,就是只有一个诚实族的。 ” 请根据他的回答判断他们分别是哪个族的。 *问题分析与算法设计 假设这三个人分别为 A、B、C,若说谎其值为 0,若诚实,其值为 1。根据题目中三个人的话可分别列出: 第一个人: a&&a+b+c==2||!a&&a+b+c!=2 第二个人: b&&a+b+c==1||!b&&a+b+c!=1 第三个人: c&&a+b+c==1||!c&&a+b+c!=1 利用穷举法,可以很容易地推出结果。 *程序与程序注释 #include<stdio.h> void main() { int a,b,c; 49

for(a=0;a<=1;a++) for(b=0;b<=1;b++)

/*穷举每个人是说谎还是诚实的全部情况*/ /*说谎:0 诚实:1*/

for(c=0;c<=1;c++) if((a&&a+b+c==2||!a&&a+b+c!=2) /*判断是否满足题意*/ &&(b&&a+b+c==1||!b&&a+b+c!=1) &&(c&&a+b+c==1||!c&&a+b+c!=1)) { printf("A is a %s.\\n",a?"honest":"lier"); /*输出判断结果*/ printf("B is a %s.\\n",b?"honest":"lier"); printf("C is a %s.\\n",c?"honest":"lier"); } } *运行结果 A is a lier B is a lier C is a lier

(说谎族) (说谎族) (说谎族)

*思考题 迷语博士遇到四个人,知道他们可能是来自诚实族和说谎族的。为了调查这四个人是什么族的,博士照例进行询问: ”你们是什 么族的?“ 第一人说: ”我们四人全都是说谎族的。 “ 第二人说: ”我们之中只有一人是说谎族的。 “ 第三人说: ”我们四人中有两个是说谎族的。 “ 第四人说: ”我是诚实族的。 “ 问自称是“诚实族”的第四个人是否真是诚实族的? (答案:第四个人是诚实族的。) ---------------------------------------------------------42. 54.迷语博士的难题(2)

两面族是荒岛上的一个新民族,他们的特点是说话真一句假一句且真假交替。如果第一句为真,则第二句是假的;如果第一句 为假的,则第二句就是真的,但是第一句是真是假没有规律。 迷语博士遇到三个人,知道他们分别来自三个不同的民族:诚实族、说谎族和两面族。三人并肩站在博士前面。 博士问左边的人: “中间的人是什么族的?” ,左边的人回答: “诚实族的” 。 博士问中间的人: “你是什么族的?” ,中间的人回答: “两面族的” 。 博士问右边的人: “中间的人究竟是什么族的?” ,右边的人回答: “说谎族的” 。 请问:这三个人都是哪个民族的? *问题分析与算法设计 这个问题是两面族问题中最基本的问题,它比前面只有诚实族和说谎族的问题要复杂。解题时要使用变量将这三个民族分别表 示出来。 令:变量 A=1 表示:左边的人是诚实族的(用 C 语言表示为 A); 变量 B=1 表示:中间的人是诚实族的(用 C 语言表示为 B); 变量 C=1 表示:右边的人是诚实族的(用 C 语言表示为 C); 变量 AA=1 表示:左边的人是两面族的(用 C 语言表示为 AA); 变量 BB=1 表示:中间的人是两面族的(用 C 语言表示为 BB); 变量 CC=1 表示:右边的人是两面族的(用 C 语言表示为 CC); 则左边的人是说谎族可以表示为:A!=1 且 AA!=1 (不是诚实族和两面族的人) 用 C 语言表示为:!A&&!AA 中间的人是说谎族可以表示为:B!=1 且 BB!=1 用 C 语言表示为:!B&&!BB 右边的人是说谎族可以表示为:C!=0 且 CC!=1 用 C 语言表示为:!C&&!CC 根据题目中“三人来自三个民族”的条件,可以列出: a+aa!=2&&b+bb!=2&&c+cc!=2 且 a+b+c==1&&aa+bb+cc==1 50

根据左边人的回答可以推出:若他们是诚实族,则中间的人也是诚实族;若他不是诚实族,则中间的人也不是诚实族。以上条 件可以表示为: c&&!b&&!bb||(!c&&!cc)&&(b||bb)||!c&&cc 将全部逻辑条件联合在一起,利用穷举的方法求解,凡是使上述条件同时成立的变量取值就是题目的答案。 *程序与程序注释 #include<stdio.h> void main() { int a,b,c,aa,bb,cc; for(a=0;a<=1;a++)

/*穷举全部情况*/

for(b=0;b<=1;b++) for(c=0;c<=1;c++) for(aa=0;aa<=1;aa++) for(bb=0;bb<=1;bb++) for(cc=0;cc<=1;cc++) if(a+aa!=2&&b+bb!=2&&c+cc!=2&&

/*判断逻辑条件*/

a+b+c==1&&aa+bb+cc==1 && (a&&!aa&&b&&!bb||!a&&!b)&& !b && (c&&!b&&!bb||(!c&&!cc)&&(b||bb)||!c&cc)) { printf("The man stand on left is a %s.\\n", aa?"double--dealer":(a?"honest":"lier")); printf("The man stand on left is a %s.\\n", bb?"double--dealer":(b?"honest":"lier")); printf("The man stand on left is a %s.\\n", cc?"double--dealer":(c?"honest":"lier")); /*输出最终的推理结果*/ } } *运行结果 The man stand on left is a double--dealer. The man stand on center is a lier. The man stand on right is a honest.

(左边的人是两面族的) (中间的人是说谎族的) (右边的人是诚实族的)

*思考题 迷语博士遇到三个人,便问第一个人: “你是什么族的?” ,回答: “诚实族的。 ”问第二个人: “你是什么族的?” ,答: “说谎族 的。 ”博士又问第二个人: “第一个人真的是诚实族的吗?” ,答: “是的。 ”问第三个人: “你是什么族的?” ,答: “诚实族的。 ”博士 又问第三个人: “第一个人是什么族的?” ,答: “两面族的。 ” 请判断这个人到底是哪个民族的? (答案:第一个人是诚实族的,第二个人是两面族的,第三人是说谎族。) 55.哪个大夫哪天值班 医院有 A、B、C、D、E、F、G 七位大夫,在一星期内(星期一至星期天)每人要轮流值班一天。现在已知: A 大夫比 C 大夫晚一天值班; D 大夫比 E 大夫晚二天值班; B 大夫比 G 大夫早三天值班; F 大夫的值班日在 B 和 C 大夫的中间,且是星期四; 请确定每天究竟是哪位大夫值班? *问题分析与算法设计 由题目可推出如下已知条件: *F 是星期四值班; *B 值班的日期在星期一至星期三,且三天后是 G 值班; *C 值班的日期在星期五至星期六,且一天后是 A 值班; *E 两天后是 D 值班;E 值班的日期只能在星期一至星期三; 在编程时用数组元素的下标 1 到 7 表示星期一到星期天,用数组元素的值分别表示 A~F 七位大夫。 51

*程序与程序注释 #include<stdio.h> #include<stdlib.h> int a[8]; char *day[]={"","MONDAY","TUESDAY","WEDNESDAY","THURSDAYT", "FRIDAY","SATUDAY","SUNDAY"}; /*建 立星期表*/ void main() { int i,j,t; a[4]=6;

/*星期四是 F 值班*/

for(i=1;i<=3;i++) { a=2; /*假设 B 值班的日期*/ if(!a[i+3]) a[i+3]=7; /*若三天后无人值班则安排 G 值班*/ else{ a=0;continue;} /*否则 B 值班的日期不断对*/ for(t=1;t<=3;t++) /*假设 E 值班的时间*/ { if(!a[t]) a[t]=5; /*若当天无人值班则安排 E 值班*/ else continue; if(!a[t+2]) a[t+2]=4; /*若 E 值班两天后无人值班则应为 D*/ else{ a[t]=0;continue;} /*否则 E 值班的日期不对*/ for(j=5;j<7;j++) { if(!a[j]) a[j]=3;

/*若当天无人值班,则安排 C 值班*/

else continue; if(!a[j+1]) a[j+1]=1; /*C 之后一天无人值班则应当是 A 值班*/ else{ a[j]=0;continue;} /*否则 A 值班日期不对*/ for(i=1;i<=7;i++) /*安排完毕,输出结果*/ printf("Doctor %c is on duty %s.\\n",\'A\'+a-1,day); exit(0); } } } } *运行结果 Doctor Doctor Doctor Doctor Doctor Doctor Doctor

E is on duty MONDAY. B is on duty TUESDAY. D is on duty WEDNESDAY. F is on duty THUESDAY. G is on duty FRIDAY. C is on duty SATURDAY. A is on duty SUNDAY.

(星期一:E) (星期二:B) (星期三:D) (星期四:F) (星期五:G) (星期六:C) (星期日:A)

*思考题 在本题的求解过程中,我们只考虑了一星期之内的情况,没有考虑跨周的情况。对于“B 大夫比 G 大夫早三天值班的”条件只 是简单的认为是在同一周内早三天。若考虑跨周的情况就可能出现:B 大夫星期一值班,而 G 大夫是上周的星期五。同样,对“F 大夫的值班日在 B 和 C 大夫的中间”这个条件,也可以扩展为: “只要 F 大夫的值班日在 B 和 C 大夫的中间就可以” 。 请考虑允许跨周的情况下,可能的时间安排表。 ------------------------------------------------------43. 56.区分旅客国籍

在一个旅馆中住着六个不同国籍的人,他们分别来自美国、德国、英国、法国、俄罗斯和意大利。他们的名字叫 A、B、C、D、 E 和 F。名字的顺序与上面的国籍不一定是相互对应的。现在已知: 52

1)A 美国人是医生。 2)E 和俄罗斯人是技师。 3)C 和德国人是技师。 4)B 和 F 曾经当过兵,而德国人从未参过军。 5)法国人比 A 年龄大;意大利人比 C 年龄大。 6)B 同美国人下周要去西安旅行,而 C 同法国人下周要去杭州度假。 试问由上述已知条件,A、B、C、D、E 和 F 各是哪国人? *问题分析与算法设计 首先进行题目分析,尽可能利用已知条件,确定谁不是哪国人。 由:1) 2) 3)可知:A 不是美国人,E 不是俄罗斯人,C 不是德国人。另外因为 A 与德国人的职业不同,E 与美、德人的职业不 同,C 与美、俄人的职业不同,故 A 不是俄罗斯人或德国人,E 不是美国人或德国人,C 不是美国人或俄罗斯人。 由 4)和 5)可知 B 和 F 不是德国人,A 不是法国人,C 不是意大利人。 由 6)可知 B 不是美国人,也不是法国人(因 B 与法国人下周的旅行地点不同);C 不是法国人。 将以上结果汇总可以得到下列条件矩阵: . 美(医生) 英 法 德(技师) 意大利 俄(教师) A(医生) X . X X . X BX.XX.. C(技师) X . X X X X D...... E(教师) X . . X . X F...X..

根据此表使用消元法进行求解,可以方便地得到问题的答案。 将条件矩阵输入计算机,用程序实现消去算法是很容易的。 *程序与程序注释 #include<stdio.h> char *m[7]={" ","U.S","U.K","FRANCE","GER","ITALI","EUSSIAN"}; void main() { int a[7][7],i,j,t,e,x,y; for(i=0;i<7;i++) for(j=0;j<7;j++) /*国名*/

/*初始化条件矩阵*/ /*行为人,列为国家,元素的值表示某人是该国人*/

a[j]=j; for(i=1;i<7;i++) /*条件矩阵每一列的第 0 号元素作为该列数据处理的标记*/ a[0]=1; /*标记该列尚未处理*/ a[1][1]=a[2][1]=a[3][1]=a[5][1]=0; /*输入条件矩阵中的各种条件*/ a[1][3]=a[2][3]=a[3][3]=0; /*0 表示不是该国的人*/ a[1][4]=a[2][4]=a[3][4]=a[5][4]=a[6][4]=0; a[3][5]=0; a[1][6]=a[3][6]=a[5][6]=0; while(a[0][1]+a[0][2]+a[0][3]+a[0][4]+a[0][5]+a[0][6]>0) { /*当所有六列均处理完毕后退出循环*/ for(i=1;i<7;i++) /*i:列坐标*/ if(a[0]) /*若该列尚未处理,则进行处理*/ { for(e=0,j=1;j<7;j++) if(a[j]) { if(e==1) { for(t=1;t<7;t++) if(t!=i)a[x][t]=0; a[0][y]=0; } } } 53 /*将非零元素所在的行的其它元素置 0*/ /*设置该列已处理完毕的标记*/ /*j:行坐标 e:该列中非 0 元素计数器*/ x=j;y=i;e++;} /*若该列只有一个元素为非零,则进行消去操作*/

for(i=1;i<7;i++) {

/*输出推理结果*/

printf("%c is coming from ",\'A\'-1+i); for(j=1;j<7;j++) if(a[j]!=0) { printf("%s.\\n",m[a[j>); break;} } } *运行结果 A is coming from ITALY. (意大利人) B is coming from EUSSIAN. (俄罗斯人) C is coming from U.K.. (英国人) D is coming from GER. (德国人) E is coming from FRANCE. (法国人) F is coming from U.S.. (美国人) *问题的进一步讨论 生成条件矩阵然后使用消去法进行推理判断是一种常用的方法。对于解决较为复杂的逻辑问题是十分有效的。 *思考题 地理课上老师给出一张没有说明省份的中国地图,从中选出五个省从 1 到 5 编号,要大家写出省份的名称。交卷后五位同学每 人只答了二个省份的名称如下,且每人只答对了一个省,问正确答案是什么? A 答:2 号陕西,5 号甘肃 B 答:2 号湖北,4 号山东 C 答:1 号山东,5 号吉林 D 答:3 号湖北,4 号吉林 E 答:2 号甘肃,3 号陕西

44.

57.谁家孩子跑最慢

张王李三家各有三个小孩。一天,三家的九个孩子在一起比赛短跑,规定不分年龄大小,跑第一得 9 分,跑第 2 得 8 分,依此 类推。比赛结果各家的总分相同,且这些孩子没有同时到达终点的,也没有一家的两个或三个孩子获得相连的名次。已知获第一名 的是李家的孩子,获得第二的是王家的孩子。问获得最后一名的是谁家的孩子? *问题分析与算法设计 按题目的条件,共有 1+2+3+...+9=45 分,每家的孩子的得分应为 15 分。根据题意可知:获第一名的是李家的孩子,获第二 名的是王家的孩子,则可推出:获第三名的一定是张家的孩子。由“这些孩子没有同时到达终点的”可知:名次不能并列,由“没 有一家的两个或三个孩子获得相连的名次”可知:第四名不能是张家的孩子。 程序中为了方便起见,直接用分数表示。 *程序与程序注释 #include<stdio.h> int score[4][4]; void main() { int i,j,k,who; score[1][1]=7; /*按已知条件进行初始化:score[1]:张家三个孩子的得分*/ score[2][1]=8; /*score[2]:王家三个孩子的得分*/ score[3][1]=9; /*李家三个孩子的得分*/ for(i=4;i<6;i++) /*i:张家孩子在 4 到 6 分段可能的分数*/ for(j=4;j<7;j++) /*j:王家孩子在 4 到 6 分段可能的分数*/ for(k=4;i!=j&&k<7;k++) /*k:李家孩子在 4 到 6 分段可能的分数*/ if(k!=i&&k!=j&&15-i-score[1][1]!=15-j-score[2][1] /*分数不能并列*/ &&15-i-score[1][1]!=15-k-score[3][1] &&15-j-score[2][1]!=15-k-score[3][1]) { score[1][2]=i;score[1][3]=15-i-7; score[2][2]=j;score[2][3]=15-j-8; score[3][2]=k;score[3][3]=15-k-9; } for(who=0,i=1;i<=3;i++,printf("\\n")) 54 /*将满足条件的结果记入数组*/

for(j=1;j<=3;j++) { printf("%d",score[j]); if(score[j]==1)who=i; } if(who==1)

/*输出各家孩子的得分情况*/ /*记录最后一名的家庭序号*/ /*输出最后判断的结果*/

printf("The last one arrived to end is a child from family Zhang.\\n"); else if(who==2) printf("The last one arrived to end is a child from family Wang.\\n"); else printf("The last one arrived to end is a child from family Li.\\n"); } *运行结果 7 5 3 8 6 1 9 4 2 The last one arrived to end is a child from family Wang. (获得最后一名的是王家的孩子。) ---------------------------------------------------------------------------------作者:huang01 发布时间:2004-10-21 17:11:13

-58.拉丁方 构造 NXN 阶的拉丁方阵(2<=N<=9),使方阵中的每一行和每一列中数字 1 到 N 只出现一次。如 N=4 时: 1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3 *问题分析与算法设计 构造拉丁方阵的方法很多,这里给出最简单的一种方法。观察给出的例子,可以发现:若将每 一行中第一列的数字和最后一列 的数字连起来构成一个环,则该环正好是由 1 到 N 顺序构成;对于第 i 行,这个环的开始数字为 i。按照 此规律可以很容易的写出 程序。下面给出构造 6 阶拉丁方阵的程序。 *程序与程序注释 #include<stdio.h> #define N 6 /*确定 N 值*/

void main() { int i,j,k,t; printf("The possble Latin Squares of order %d are:\\n",N); for(j=0;j<N;j++) /*构造 N 个不同的拉丁方阵*/ { for(i=0;i<N;i++) { t=(i+j)%N; /*确定该拉丁方阵第 i 行的第一个元素的值*/ for(k=0;k<N;k++) /*按照环的形式输出该行中的各个元素*/ printf("%d",(k+t)%N+1); printf("\\n"); } printf("\\n"); } } *运行结果 The possble Latin Squares of order 6 are: 123456 234561 234561 345612 345612 456123 55

3 4 5 6 4 5 6 1 2 3

4 5 6 1 5 6 1 2 3 4

5 6 1 2 6 1 2 3 4 5

6 1 2 3 1 2 3 4 5 6

1 2 3 4 2 3 4 5 6 1

2 3 4 5 3 4 5 6 1 2

4 5 6 1 5 6 1 2 3 4

5 6 1 2 6 1 2 3 4 5

6 1 2 3 1 2 3 4 5 6

1 2 3 4 2 3 4 5 6 1

2 3 4 5 3 4 5 6 1 2

3 4 5 6 4 5 6 1 2 3

5 6 1 2 6 1 2 3 4 5

6 1 2 3 1 2 3 4 5 6

1 2 3 4 2 3 4 5 6 1

2 3 4 5 3 4 5 6 1 2

3 4 5 6 4 5 6 1 2 3

4 5 6 1 5 6 1 2 3 4

---------------------------------------------------------------45. 59.填表格

将 1、2、3、4、5 和 6 填入下表中,要使得每一列右边的数字比左边的数字大,每一行下面的数字比上面的数字大。按此要求, 可有几种填写方法? . . . . . . /*两个点之间为表格*/

*问题分析与算法设计 按题目的要求进行分析,数字 1 一定是放在第一行第一列的格中,数字 6 一定是放在第二行第三列的格中。在实现时可用一个 一维数组表示,前三个元素表示第一行,后三个元素表示第二行。先根据原题初始化数组, 再根据题目中填 写数字的要求进行试探。 *程序与程序注释 #include<stdio.h> int jud1(int s[]); void print(int u[]); int count; /*计数器*/ void main() { static int a[]={1,2,3,4,5,6};

/*初始化数组*/

printf("The possble table satisfied above conditions are:\\n"); for(a[1]=a[0]+1;a[1]<=5;++a[1]) /*a[1]必须大于 a[0]*/ for(a[2]=a[1]+1;a[2]<=5;++a[2]) /*a[2]必须大于 a[1]*/ for(a[3]=a[0]+1;a[3]<=5;++a[3]) /*第二行的 a[3]必须大于 a[0]*/ for(a[4]=a[1]>a[3]?a[1]+1:a[3]+1;a[4]<=5;++a[4]) /*第二行的 a[4]必须大于左侧 a[3]和上边 a[1]*/ if(jud1(a)) print(a); /*如果满足题意,打印结果*/ } int jud1(int s[]) { int i,l; for(l=1;l<4;l++) for(i=l+1;i<5;++i) if(s[l]==s) return 0; return 1; } void print(int u[]) { int k; printf("\\nNo.:%d",++count); for(k=0;k<6;k++) if(k%3==0) /*输出数组的前三个元素作为第一行*/ 56

/*若数组中的数字有重复的,返回 0*/ /*若数组中的数字没有重复的,返回 1*/

else } *运行结果

printf("\\n%d",u[k]); /*输出数组的后三个元素作为第二行*/ printf("%d",u[k]);

The possble table satisfied above conditions are: No.1: No.2: No.3: No.4: 123 124 125 134 456 356 346 256 -------------------------------------------------------46. 60.1~9 分成 1:2:3 的三个 3 位数

No.5: 135 246

将 1 到 9 这九个数字分成三个 3 位数,分求第一个 3 位数,正好是第二个 3 位数的二倍,是第三个 3 位数的三倍。问应当怎样 分法。 *问题分析与算法设计 问题中的三个数之间是有数学关系的,实际上只要确定第一个三位数就可以解决问题。 试探第一个三位数之后,计算出另外两个数,将其分别分解成三位数字,进行判断后确定所试探的数是否就是答案。 需要提醒的是:试探的初值可以是 123,最大值是 333。因为不可能超出该范围。 *程序与程序设计 #include<stdio.h> int ok(int t,int *z); int a[9]; void main() { int m,count=0; for(m=123;m<=333;m++) /*试探可能的三位数*/ if(ok(m,a)&&ok(2*m,a+3)&&ok(3*m,a+6)) /*若满足题意*/ printf("No.%d: %d %d %d\\n",++count,m,2*m,3*m); /*输出结果*/ } int ok(int t,int *z) { int *p1,*p2; for(p1=z;p1<z+3;p1++) { *p1=t%10; /*分解 t 的值,将其存入 z 指向的三个数组元素,若满足要求返回 1*/

/*分解整数*/

t/=10; for(p2=a;p2<p1;p2++) /*查询分解出的数字是否已经出现过*/ if(*p1==0||*p2==*p1)return 0; /*若重复则返回*/ } return 1; } *运行结果 No.1:192 No.2:219 No.3:273 No.4:327 384 438 546 654 576 657 819 981 /*否则返回 1*/

*思考题 求出所有可能的以下形式的算式,每个算式中有九个数位,正好用尽 1 到 9 这九个数字。 1)○○○+○○○=○○○ (共有 168 种可能的组合) 2)○×○○○○=○○○○ (共有 2 种可能的组合) 3)○○×○○○=○○○○ (共有 7 种可能的组合) 4)○×○○○=○○×○○○ (共有 13 种可能的组合) 57

5)○×○○○=○×○○○○ 6)○○×○○=○×○○○○ 7)○○×○○=○○×○○○

(共有 28 种可能的组合) (共有 7 种可能的组合) (共有 11 种可能的组合)

----------------------------------------------------------------------------------47. 61.1~9 组成三个 3 位的平方数 作者:huang01 发布时间:2004-10-21 17:12:08

将 1、2、3、4、5、6、7、8、9 九个数字分成三组,每个数字只能用一次,即每组三个数不允许有重复数字,也不许同其它组 的三个数字重复,要求每组中的三位数都组成一个平方数。 *问题分析与算法设计 本问题的思路很多,这里介绍一种简单快速的算法。 首先求出三位数中不包含 0 且是某个整数平方的三位数,这样的三位数是不多的。然后将满足条件的三位数进行组合,使得所 选出的 3 个三位数的 9 个数字没有重复。 程序中可以将寻找足条件的三位数的过程和对该三位数进行数字分解的过程结合起来。 *程序与程序注释 #include<stdio.h> void main() { int a[20],num[20][3],b[10];

/*a:存放满足条件的三位数*/ /*若不是 10 的倍数,则分解三位数*/ /*分解该三位数中的每一个数字*/

int i,j,k,m,n,t,flag; printf("The 3 squares with 3 different digits each are:\\n"); for(j=0,i=11;i<=31;i++) /*求出是平方数的三位数*/ if(i%10!=0) /*若不是 10 的倍数,则分解三位数*/ { k=i*i; /*分解该三位数中的每一个数字*/ num[j+1][0]=k/100; /*百位*/ num[j+1][1]=k/10%10; /*十位*/ num[j+1][2]=k%10; /*个位*/ if(!(num[j+1][0]==num[j+1][1]||num[j+1][0]==num[j+1][2]|| num[j+1][1]==num[j+1][2])) /*若分解的三位数字均不相等*/ a[++j]=k; /*j:计数器,统计已找到的满足要求的三位数*/ } for(i=1;i<=j-2;++i) /*从满足条件的三位数中选出三个进行组合*/ { b[1]=num[0]; b[2]=num[1]; b[3]=num[2]; for(t=i+1;t<=j-1;++t) { b[4]=num[t][0]; /*取第 t 个数的三位数字*/ b[5]=num[t][1]; b[6]=num[t][2]; for(flag=0,m=1;!flag&&m<=3;m++) /*flag:出现数字重复的标记*/ for(n=4;!flag&&n<=6;n++) /*判断两个数的数字是否有重复*/ if(b[m]==b[n])flag=1; /*flag=1:数字有重复*/ if(!flag) for(k=t+1;k<=j;k++) { b[7]=num[k][0];

/*取第 k 个数的三位数字*/ 58

b[8]=num[k][1]; b[9]=num[k][2]; for(flag=0,m=1;!flag&&m<=6;m++) /*判断前两个数字是否*/ for(n=7;!flag&&n<=9;n++) /*与第三个数的数字重复*/ if(!flag) } } } } *运行结果 The 3 squares with 3 different digits each are: 361,529,784 *思考题 将 1、2、3、4、5、6、7、8、9 九个数字分成二组,每个数字只能用一次,一组形成一个 5 位数,另一组形成一个 4 位数,使 得前者为后者的 n 倍。求所有满足条件的 5 位数和 4 位数。(注意:N 的最大值等于 68,68 以内的某些 N 也是不可能的。不可能的 N 值包括:1、10、11、20、21、25、30、31 等共 32 个。) ------------------------------------------------------48. 62.由 8 个整数形成奇特的立方体 if(b[m]==b[n])flag=1; /*若均不重复则打印结果*/

printf("%d,%d,%d\\n",a,a[t],a[k]);

任意给出 8 个整数,将这 8 个整数分别放在一个立方体的八个顶点上,要求每个面上的四个数之和相等。 *问题分析与算法设计 简化问题:将 8 个顶点对应数组中的 8 个元素,将“每个面上的四个数之和皆相等”转换为数组无素之间和的相等关系。这里 的关键在于正确地将立方体的 8 个顶点与数组的 8 个元素对应。 可以利用简单的穷举方法建立 8 个数的全部排列。 *程序与程序注释 #include<stdio.h> #include<stdlib.h> void main() { int a[9],ii=0,i,a1,a2,a3,a4,b1,b2,b3,b4,flag; for(i=1;i<=8;i++) /*输入个数*/ { printf("Please enter [%d]number:",i); scanf("%d",&a); ii+=a; } printf("******************************************\\n"); if(ii%2) /*和为奇数则输入的 8 个数不可用*/ { printf("Sorry they can\'t be constructed required cube!\\n"); exit(0); } for(flag=0,a1=1;a1<=8;a1++) /*flag:完成标记.flag=1;表示完成*/ for(a2=1;a2<=8;a2++) /*采用八重循环建立八个整数的全排列*/ if(a2!=a1) /*前两个数不能相同*/ for(a3=1;a3<=8;a3++) if(a3!=a2&&a3!=a1) /*前三个数不能相同*/ /*前四个数不能相同*/ /*不能相同*/

for(a4=1;a4<=8;a4++) if(a4!=a3&&a4!=a2&&a4!=a1)

for(b1=1;b1<=8;b1++) if(b1!=a4&&b1!=a3&&b1!=a2&&b1!=a1) for(b2=1;b2<=8;b2++) 59

if(b2!=b1&&b2!=a4&&b2!=a3&&b2!=a2&&b2!=a1) for(b3=1;b3<=8;b3++) if(b3!=b2&&b3!=b1&&b3!=a4&&b3!=a3&&b3!=a2&&b3!=a1) /*不能取相同的数*/ for(b4=1;b4<=8;b4++) if(b4!=b2&&b4!=b1&&b4!=b3&&b4!=a4&&b4!=a3&&b4!=a2&&b4!=a1) if(a[b1]+a[b2]+a[b3]+a[b4]==ii/2 &&a[a1]+a[a2]+a[b1]+a[b2]==ii/2 &&a[a1]+a[a4]+a[b1]+a[b4]==ii/2) { flag=1;goto out; /*满足条件则将 flag 置 1 后退出*/ } out: if(flag) { printf("They can be constructed required cube as follow:\\n"); printf(" /%2d............/%2d\\n",a[a4],a[a3]); printf(" %2d/............%2d/|\\n",a[a1],a[a2]); printf(" | | | |\\n"); printf(" | | | |\\n"); printf(" | %2d| | |%2d\\n",a[b4],a[b3]); printf(" /................/\\n"); printf(" %2d/.............%2d/\\n",a[b1],a[b2]); } else printf("Sorry they can\'t be constructed required cube!\\n");

----------------------------------------------------------------------------------49. 63.减式还原 作者:huang01 发布时间:2004-10-21 17:12:50

编写程序求解下式中各字母所代表的数字,不同的字母代表不同的数字。 PEAR - ARA -------PEA *问题分析与算法设计 类似的问题从计算机算法的角度来说是比较简单的,可以采用最常见的穷举方法解决。程序中采用循环穷举每个字母所可能代 表的数字,然后将字母代表的数字转换为相应的整数,代入算式后验证算式是否成立即可解决问题。 *程序与程序注释 #include<stdio.h> void main() { int p,e,a,r; for(p=1;p<=9;p++) /*从 1 到 9 穷举字母 p 的全部可能取值*/ for(e=0;e<=9;e++) /*从 0 到穷举字母 e 的全部可能取值*/ if(p!=e) /*p 不等于 e*/ for(a=1;a<=9;a++) /*从 0 到 9 穷举字母 a 的全部可能取值*/ if(a!=p&&a!=e) for(r=0;r<=9;r++) /*从 0 到 9 穷举字母 r 的全部可能取值*/

if(r!=p&&r!=e&&r!=a&&p*1000+e*100+a*10+r-(a*100+r*10+a) ==p*100+e*10+a) { 60

printf(" PEAR %d%d%d%d\\n",p,e,a,r); printf(" -ARA %d%d%d\\n",a,r,a); printf(".........................\\n"); printf(" PEA %d%d%d\\n",p,e,a); } } *运行结果 PEAR ARA ---------PEA 1098 - 989 -----109

*思考题 请复原下面的和式。不同的字母代表不同的数字。 SEVEN THREE + TWO ---------TWELVE 82524 19722 + 106 ----------102352 82526 19722 + 104 102352

答案:

-----------

----------------------------------------------------------50. 64.乘式还原

A 代表数字 0 到 9 中的前五个数字,Z 代表后五个数字,请还原下列乘式。 AZA × AAZ -----------AAAA AAZZ ZAA -----------ZAZAA *问题分析与算法设计 问题本身并不复杂,可以对乘式中的每一位使用穷举法,最终可以得到结果。本题的关键在于怎样有效的判断每个部分积的每一 位是否满足题意,这一问题处理不好,编写的程序会很长。程序实现中采用了一个判断函数,通过传入函数的标志字符串对所有的 数进行统一的判断处理。 *程序与程序注释 #include<stdio.h> void print(long a,long b,long s1,long s2,long s3); int jud(long q,char *pflag); void main() { long i,j,k,l,m,n,term,t1,t2,t3; int flag; for(i=0;i<=4;++i) /*被乘数的第一位*/ for(j=5;j<=9;++j) /*被乘数的第二位*/ for(k=0;k<=4;++k) /*被乘数的第三位*/ { term=100*i+10*j+k; /*被乘数*/ for(flag=0,n=0;n<4&&!flag;) /*乘数的第一位*/ flag=jud((t3=++n*100*term)/100,"001"); /*判断第三个部分积*/ if(flag) { for(flag=0,m=0;m<4&&!flag;) /*乘数的第二位*/ flag=jud((t2=++m*10*term)/10,"1100"); /*判断第二个部分积*/ if(flag) 61

{ for(flag=0,l=5;l<9&&!flag;) /*乘数的第三位*/ flag=jud(t1=++l*term,"0000"); /*判断第一个部分积*/ if(flag&&jud(t1+t2+t3,"00101")) /*判断乘式的积*/ print(term,n*100+m*10+l,t1,t2,t3); } } } } void print(long a,long b,long s1,long s2,long s3) { printf("\\n %ld\\n",a); printf("*) %ld\\n",b); printf("......................\\n"); printf(" %ld\\n %ld\\n printf("......................\\n"); printf(" %ld\\n",a*b); /*打印结果*/

%ld\\n",s1,s2/10,s3/100);

} int jud(long q,char *pflag) /*判断一个数的每一位是否满足要求的判断函数*/ /*q:需要判断的数。pflag:标志字符串,A 用 1 表示,Z 用 0 表示。标志串排列顺序:个十百...*/ { while(q!=0&&*pflag!=NULL) /*循环判断对应位的取值范围是否正确*/ if(*pflag-\'0\'!=(q%10>=5?1:0)) /*标志位与对应的位不符,返回 0*/ return 0; else { q/=10;++pflag; /*若相符则取下一位进行判断*/ } if(q==0&&*pflag==NULL) return 1; else return 0; } *运行结果 372 × 246 ---------2232 1488 744 -----------91512 /*q 的位数与标志字符串的长度相同时,返回 1*/

*思考题 E 代表数字 0 到 9 中的偶数数字,O 代表奇数数字,请还原下列乘式。 EEO 285 × OO 答案 × 39 --------------------EOEO 2565 EOO 855 --------------------OOOOO 11115 51. 65.乘式还原(2)

有乘法算式如下: 62

×

○○○ ○○

-----------○○○○ ○○○○ -----------○○○○○ 18 个○的位置上全部是素数(1、3、5 或 7),请还原此算式。 *问题分析与算法设计 问题中虽然有 18 数位,但只要确定乘数和被乘数后经过计算就可确定其它的数位。 乘数和被乘数共有 5 个数位,要求每个数都是质数。完全可以采用穷举的方法对乘数和被乘数进行穷举,经过判断后找出答案。 但是这种方法给人的感觉是“太笨了” ,因为组成的数字只是质数(4 个),完全没有必要在那么大的范围内进行穷举,只需要试探每 一位数字为质数时的情况即可。 采用五重循环的方法实现对于 5 个数字的穷举,前面的许多例题中都已见过。循环实现简单易行,但嵌套的层次太多,需要穷 举的变量的数量直接影响到循环嵌套的层数,这种简单的实现方法缺少技巧性。本例的程序中给出了另外一种同样功能的算法,该 算法的实现思想请阅读程序。 程序中并没有直接对质数进行穷举,而是将每个质数与 1 到 4 顺序一一对应,在穷举时为处理简单仅对 1 到 4 进行穷举处理, 待要判断产生的乘积是否满足条件时再利用一个数组完成向对应质数的转换。请体会程序中的处理方法。程序中使用的算法实际上 是回朔法。 *程序与程序注释 #include<stdio.h> #define NUM 5 /*需要穷举的变量数目*/ #define C_NUM 4 /*每个变量的值的变化范围*/ int a[NUM+1]; /*为需要穷举的变量开辟的数组*/ /*a[1]:被乘数的百位,a[2]:十位,aa[3]:个位 a[4]:被乘数的十位 a[5]:个位*/ int b[]={0,2,3,5,7}; /*存放质数数字的数组,不使用第 0 号元素*/ int f(long sum); void main() { int i,not_finish=1; i=2; a[1]=1; while(not_finish) { while(not_finish&&i<=NUM) /*处理包括第 i 个元素在内的后续元素,找出当前条件下的一种各个变量的一种可能的取值方法*/ if(a>=C_NUM) /*当要处理的元素取超过规定的 C_NUM 时*/ if(i==1&&a[1]==C_NUM) not_finish=0; /*若 1 号元素已经到 C_NUM,则处理全部结束*/ else a[i--]=0; /*将要处理的元素置 0,下标-1(回退一个元素)*/ else a[i++]++; /*当前元素值加 1 后下标指针加 1*/ if(not_finish) { long int sum1,sum2,sum3,sum4; /*定义临时变量*/ sum1=b[a[1>*100+b[a[2>*10+b[a[3>; /*计算被乘数*/ /*利用数组的下标与质数的对应关系完成序号 1 到 4 向质数的转换*/ sum2=sum1*b[a[5>; /*计算乘数个位与被乘数的部分积*/ sum3=sum1*b[a[4>; /*计算乘数十位与被乘数的部分积*/ if(sum2>=2222&&sum2<=7777&&f(sum2)&&sum3>=2222&&sum3<=7777&&f(sum3)) /*判断两部分积是否满足题目条件*/ if((sum4=sum2+sum3*10)>=22222&&sum4<=77777&&f(sum4)) /*判断乘式的积是否满足题目条件*/ { printf(" %d\\n",sum1); /*若满足题意,则打印结果*/ 63 printf("* %d%d\\n",b[a[4>,b[a[5>);

/*i:将要进行处理的元素的指针下标。设置初始值*/ /*为第 1 号元素设置初始值*/ /*not_finish:程序运行没结束标记*/

printf("........................\\n"); printf(" %d\\n",sum2); printf(" %d\\n",sum3); printf("........................\\n"); printf(" %d\\n",sum4); } i=NUM; } } } int f(long sum) { int i,k,flag; while(sum>0) { i=sum%10; /*为穷举下一个可能取值作准备*/

/*判断 sum 的每一位数字是否是质数,若不是返回 0,若是返回 1*/ /*flag=1:数字是质数的标记*/

/*取个位的数字*/

for(flag=0,k=1;!flag&&k<=C_NUM;k++) if(b[k]==i) { flag=1;break; } if(!flag) return 0; else sum=sum/10; } return 1; } *运行结果 775 × 33 ---------2325 2325 ----------25575 *思考题 以下乘式中,A、B、C 代表一确定的数字,○代表任意数字,请复原。 ABC × BAC ------------○○○○ ○○A ○○○B 286 × 826 -----------1716 572 2288

答案:

---------------------------○○○○○○ 236236 --------------------------------------------------------------------------------- 作者:huang01 -- 发布时间:2004-10-21 17:13:25 -52. 66.除式还原(1)

给定下列除式,其中包含 5 个 7,其它打×的是任意数字,请加以还原。 × 7 × --------------商

-------------除数------××| ×××××-------------被除数 ×7 7 64

-------------× 7× × 7× ---------× × × × ---------○ *题目分析与算法设计 首先分析题目,由除式本身尽可能多地推出已知条件。由除式本身书已知: 1、被除数的范围是 10000 到 99999,除数的范围是 10 到 99,且可以整除; 2、商为 100 到 999 之间,且十位数字为 7; 3、商的第一位与除数的积为三位数,且后两位为 77; 4、被除数的第三位一定为 4; 5、 7 乘以除数的积为一个三位数,且第二位为 7; 6、商的最后一位不能为 0,且与除数的积为一个二位数。 由已知条件就可以采用穷举的方法找出结果。 *程序与程序注释 #include<stdio.h> void main() { long int i; int j,l; for(i=10000;i<=99999;i++) if(i%1000-i%100==400) for(j=10;j<=99;j++)

/*1. i:被除数*/ /*4. 被除数的第三位一定为 4*/ /*1. j: 余数*/

if(i%j==0&&(l=i/j)%100>=70&&l%100<80&&l%10!=0&&l>100&&l<=999) /*1. 可以整除&& 2.商 l 在 100 到 999 之间且十位数字为 7&&6.商的个数不能为 0*/ if((j*(l%10))<100&&j*(l%10)>10) /*6. 商的个数与除数的积为二位数*/ if(j*7%100>=70&&j*7%100<80) /*5. 7 乘以除数的积的第二位为 7*/ if(j*(l/100)%100==77&&j*(l/100)>100) /*商的第一位与除数的积的后两位为 77*/ printf("%ld/%ld=%d\\n",i,j,l); } *运行结果 51463/53=971。 可以看作为下列算式: 971 ------------5 3| 5 1 4 6 3 477 ------------376 371 ----------53 53 ----------○ *问题的进一步讨论 在推出的已知条件中,几所有的条件都是十分明显的,换句话说,推出的已知条件就是对题目的平铺直叙。这种推已知条件的 方法十分简单,并且行之有效。 *思考题 下列除式中仅给定了一个 8,其它打×的位置上是任意数字,请还原。 65

× 8 × 除数-------×××|

----------------商

---------------××××××---------------被除数 ×××× --------------××× ××× --------------×××× ×××× --------------○

-------------------------------------------------------53. 67.除式还原(2)

下列除式中仅在商中给定了一个 7,其它打×的位置全部是任意数字,请还原。 ×7××× 除数 -------------------×××| -------------商

-----------------×××××××× -------------被除数 ×××× --------------××× ××× --------------×××× ××× ----------------×××× ×××× ----------------0 -------------1) -------------2) -------------3) -------------4) -------------5) -------------6) -------------7)

*题目分析与算法设计 这道题是不可能用单纯的穷举法求解的,一则计算时间太长,二则难于求出除式中各部分的值。 对除式进行分析,改可能多地推出限制条件: 由 3)可以看出,商的第二位 7 乘除数得一个三位数,所以除数<=142。 由除数乘商的第一位为一个四位数可知,商的第一位只能为 8 或 9 且除数>=112。同时商的第五位也为 8 或 9 数的前四位一定 <=142*9+99 且>=1000+10。 由 4)、5)、6)可以看出,4)的前两位一定为“10” ;5)的第一位一定为“9” ;6)的前两位一定在 10 到 99 之间;商的第四位一 定为为 0。 由 5)的第一位一定是“9”和“112”<=除数<=142 可知:商的第三位可能为 7 或 8。 由除式本身可知:商的第四位为 0。 由 1)可知:除数 X 商的第一位应当为一个四位数。 由 5)可知:除数 X 商的第三位应当为一个三位数。 编程时为了方便,将被除数分解:前四位用 a[0]表示,第五位用 a[1],第六位用 a[2],第七八两位用 a[3];除数用变量 b 表示; 分解商:第一位用 c[0],第五位用 c[2];其它的部分商分别表示为:2)的前两位为 d[0],4)的前三位为 d[1],6)的前二位为 d[2]。将 上述分析用数学的方法综合起来可以表示为: 被除数: 1010<=a[0]<=1377 0<=a[1]<=9 除数: 商: 2)的前两位: 4)的前三位: 6)的前两位: 0<=a[2]<=9 112<=b <=142 8<=c[0]<=9 10<=d[0]<=99 100<=d[1]<b 10<=d[2]<=99 0<=a[3]<=99 7<=c[1]<=8 8<=c[2]<=9

66

1)式部分积: b*c[0]>1000 5)式部分积: 100<b*c[1]<1000 *程序与程序注释 #include<stdio.h> void main() { int a[4],b,c[3],d[4],i=1; for(a[0]=1010;a[0]<=1377;a[0]++) for(b=112;b<=142;b++) for(c[0]=8;c[0]<=9;c[0]++) if(b*c[0]>1000&&(d[0]=a[0]-b*c[0])>=10&&d[0]<100) for(a[1]=0;a[1]<=9;a[1]++) if((d[1]=d[0]*10+a[1]-b*7)>=100&&d[1]<b) for(a[2]=0;a[2]<=9;a[2]++) for(c[1]=7;c[1]<=8;c[1]++) if(b*c[1]<1000&&(d[2]=d[1]*10+a[2]-b*c[1])>=10&&d[2]<100) for(a[3]=0;a[3]<=99;a[3]++) for(c[2]=8;c[2]<=9;c[2]++) if(d[2]*100+a[3]-b*c[2]==0) { printf("No%2d:",i++); printf("%d%d%d%d%d/",a[0],a[1],a[2],a[3]/10,a[3]%10); printf("%d=",b); printf("%d%d%d%d%d\\n",c[0],7,c[1],0,c[2]); } } *运行结果: No 1:12128316/124=97809 *思考题 下列除式中“×”所在的位置全部是任意数字,请还原。 ××××× ------------------×××××××× ×××× -----------------×××× ××× --------------××× ××× ----------×××× ×××× -----------

××× |

0 -------------------------------------------------------------------------------68.九位累进可除数 求九位累进可除数。所谓九位累进可除数就是这样一个数:这个数用到 1 到 9 这九个数字组成,每个数字刚好只出现一次。这 九个位数的前两位能被 2 整除,前三位能被 3 整除......前 N 位能被 N 整除,整个九位数能被 9 整除。 *问题分析与算法设计 问题本身可以简化为一个穷举问题:只要穷举每位数字的各种可能取值,按照题目的要求对穷举的结果进行判断就一定可以得 到正确的结果。 问题中给出了“累进可除”这一条件,就使得我们可以在穷举法中加入条件判断。在穷举的过程中,当确定部分位的值后,马 上就判断产生的该部分是否符合“累进可除”条件,若符合,则继续穷举下一位数字;否则刚刚产生的那一位数字就是错误的。这 样将条件判断引入到穷举法之中,可以尽可能早的发现矛盾,尽早地放弃不必要穷举的值,从而提高程序的执行效率。 为了达到早期发现矛盾的目的,不能采用多重循环的方法实行穷举,那样编出的程序质量较差。程序中使用的算法不再是穷举 67

法,而是回朔法。 *程序与程序注释 #include<stdio.h> #define NUM 9 int a[NUM+1]; void main() { int i,k,flag,not_finish=1; long sum; i=1; /*i:正在处理的数组元素,表示前 i-1 个元素已经满足要求,正处理的是第 i 个元素*/ a[1]=1; /*为元素 a[1]设置初值*/ while(not_finish) /*not_finish=1:处理没有结束*/ { while(not_finish&&i<=NUM) { for(flag=1,k=1;flag&&k<i;k++) if(a[k]==a)flag=0; /*判断第 i 个元素是否与前 i-1 个元素重复*/ for(sum=0,k=1;flag&&k<=i;k++) { sum=10*sum+a[k]; if(sum%k)flag=0; /*判断前 k 位组成的整数是否能被 k 整除*/ } if(!flag) /*flag=0:表示第 i 位不满足要求,需要重新设置*/ { if(a==a[i-1]) /*若 a 的值已经经过一圈追上 a[i-1]*/ { i--; /*i 值减 1,退回处理前一个元素*/ if(i>1&&a==NUM) a=1; /*当第 i 位的值达到 NUM 时,第 i 位的值取 1*/ else if(i==1&&a==NUM) /*当第 1 位的值达到 NUM 时结束*/ not_finish=0; /*置程序结束标记*/ else a++; /*第 i 位的值取下一个,加 1*/ } else if(a==NUM) a=1; else a++; } else /*第 i 位已经满足要求,处理第 i+1 位*/ if(++i<=NUM) /*i+1 处理下一元素,当 i 没有处理完毕时*/ if(a[i-1]==NUM) a=1; /*若 i-1 的值已为 NUM,则 a 的值为 1*/ else a=a[i-1]+1; /*否则,a 的初值为 a[i-1]值的"下一个"值*/

} if(not_finish) { printf("\\nThe progressire divisiable number is:"); for(k=1;k<=NUM;k++) /*输出计算结果*/ printf("%d",a[k]); if(a[NUM-1]<NUM) a[NUM-1]++; else a[NUM-1]=1; not_finish=0; printf("\\n"); } } } *运行结果 The progressire divisible number is: 381654729 68

*思考题 求 N 位累进可除数。用 1 到 9 这九个数字组成一个 N(3<=N<=9)位数,位数字的组成不限,使得该 N 位数的前两位能被 2 整 除,前 3 位能被 3 整除,......,前 N 位能被 N 整除。求满足条件的 N 位数。 69.魔术师的猜牌术(1) 魔术师利用一副牌中的 13 张黑桃,预先将它们排好后迭在一起,牌面朝下。对观众说:我不看牌,只数数就可以猜到每张牌是 什么,我大声数数,你们听,不信?你们就看。魔术师将最上面的那张牌数为 1,把它翻过来正好是黑桃 A,将黑桃 A 放在桌子上, 然后按顺序从上到下数手上的余牌,第二次数 1、2,将第一张牌放在这迭牌的下面,将第二张牌翻过来,正好是黑桃 2,也将它放 在桌子上,第三次数 1、2、3,将前面两张依次放在这迭牌的下面,再翻第三张牌正好是黑桃 3。这样依次进行将 13 张牌全翻出来, 准确无误。问魔术师手中的牌原始顺序是怎样安排的? *问题分析与算法设计 题目已经将魔术师出牌的过程描述清楚,我们可以利用倒推的方法,很容易地推出原来牌的顺序。 人工倒推的方法是:在桌子上放 13 空盒子排成一圈,从 1 开始顺序编号,将黑桃 A 放入 1 号盒子中,从下一个空盒子开始对 空的盒子计数,当数到第二个空盒子时,将黑桃 2 放入空盒子中,然后再从下一个空盒子开始对空盒子计数,顺序放入 3、4、5..., 直到放入全部 3 张牌。注意在计数时要跳过非空的盒子,只对空盒子计数。最后牌在盒子中的顺序,就是魔术师手中原来牌的顺序。 这种人工的方法是行之有效的,计算机可以模拟求解。 *程序与程序注释 #include<stdio.h> int a[14]; void main() { int i,n,j=1;

/*j:数组(盒子)下标,初始时为 1 号元素*/

printf("The original order of cards is:"); for(i=1;i<=13;i++) /*i:要放入盒子中的牌的序号*/ { n=1; do{ if(j>13) j=1; /*由于盒子构成一个圈,j 超过最后一个元素则指向 1 号元素*/ if(a[j]) j++; /*跳过非空的盒子,不进行计数*/ else{ if(n==i) a[j]=i; /*若数到第 i 个空盒子,则将牌放入空盒中*/ j++;n++; /*对空盒计数,数组下标指向下一个盒子*/ } }while(n<=i); } for(i=1;i<=13;i++) printf("%d ",a); printf("\\n"); } *运行结果 The original order of cards is:1 8 2 5 10 3 12 11 9 4 7 6 13 /*控制空盒计数为 i*/ /*输出牌的排列顺序*/

70.魔术师的猜牌术(2) 魔术师再次表演,他将红桃和黑桃全部迭在一起,牌面朝下放在手中,对观众说:最上面一张是黑桃 A,翻开后放在桌上。以 后,从上至下每数两张全依次放在最底下,第三张给观众看,便是黑桃 2,放在桌上后再数两张依次放在最底下,第三张给观众看, 是黑桃 3。如此下去,观众看到放在桌子上牌的顺序是: 黑桃 A 2 3 4 5 6 7 8 9 10 J Q K 红桃 A 2 3 4 5 6 7 8 9 10 J Q K 问魔术师手中牌的原始顺序是什么? *问题分析与算法设计 本题可在上题的基础上进行编程,不同的在于计数的方法和牌的张数,这些并不影响我们求解题目的思路,仍可按照倒推的方 法,得到原来魔术师手中的牌的顺序。 *程序与程序注释 #include<stdio.h> int a[27]; void main() { 69

int i,n,j=1; a[1]=1;

/*初始化第一张牌*/

printf("The original order of cards is:(r:rad b:block):\\n"); for(i=2;i<=26;i++) { n=1; do{ if(j>26) j=1; /*超过最后一个元素则指向 1 号元素*/ if(a[j]) j++; /*跳过非空的盒子,不进行计数*/ else{ if(n==3) a[j]=i; /*若数到第 3 个空盒子,则将牌放入空盒中*/ j++; n++; /*对空盒计数,数组下标指向下一个盒子*/ } }while(n<=3); } for(i=1;i<=26;i++) { printf("%c",a>13? \'r\':\'b\'); printf("%d ",a>13? a-13:a); if(i==13) printf("\\n"); } printf("\\n"); } *运行结果 The original order of cards is:(r:rad b:black): b1 r6 b10 b2 r12 r3 b3 b11 r9 b4 r7 b12 b5 r4 r13 b6 b13 r11 b7 r5 r1 b8 r8 r10 b9 r2 71.约瑟夫问题 这是 17 世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事:15 个教徒和 15 个非教徒在深海上遇险,必须将一 半的人投入海中,其余的人才能幸免于难,于是想了一个办法:30 个人围成一圆圈,从第一个人开始依次报数,每数到第九个人就 将他扔入大海,如此循环进行直到仅余 15 个人为止。问怎样排法,才能使每次投入大海的都是非教徒。 *问题分析与算法设计 约瑟夫问题并不难,但求解的方法很多;题目的变化形式也很多。这里给出一种实现方法。 题目中 30 个人围成一圈,因而启发我们用一个循环的链来表示。可以使用结构数组来构成一个循环链。结构中有两个成员,其 一为指向下一个人的指针,以构成环形的链;其二为该 人是否被扔下海的标记,为 1 表示还在船上。从第一个人开始对还未扔下海 的人进行计数,每数到 9 时,将结构中的标记改为 0,表示该人已被扔下海了。这样循环计数直到有 15 个人被扔下海为止。 *程序与程序注释 #include<stdio.h> struct node { int nextp; int no_out; }link[31]; /*控制空盒计数为 3*/ /*输出牌的排列顺序*/

/*指向下一个人的指针(下一个人的数组下标)*/ /*是否被扔下海的标记。1:没有被扔下海。0:已被扔下海*/ /*30 个人,0 号元素没有使用*/

void main() { int i,j,k; printf("The original circle is(+:pagendom,@:christian):\\n"); for(i=1;i<=30;i++) /*初始化结构数组*/ { link.nextp=i+1; /*指针指向下一个人(数组元素下标)*/ link.no_out=1; /*标志置为 1,表示人都在船上*/ } link[30].nextp=1; j=30; for(i=0;i<15;i++) { 70 /*第 30 个人的指针指向第一个人以构成环*/ /*j:指向已经处理完毕的数组元素,从 link 指向的人开始计数*/ /*i:已扔下海的人数计数器*/

for(k=0;;)

/*k:决定哪个人被扔下海的计数器*/

if(k<15) { j=link[j].nextp; k+=link[j].no_out; } else break; link[j].no_out=0;

/*修改指针,取下一个人*/ /*进行计数。因已扔下海的人计标记为 0*/

/*计数到 15 则停止计数*/ /*将标记置 0,表示该人已被扔下海*/

} for(i=1;i<=30;i++) /*输出结果*/ printf("%c",link.no_out? \'@\':\'+\'); /*+:被扔下海, @:在船上*/ printf("\\n"); } *运行结果 The original circle is(+:pagandom, @:christian): +++@@+@+@@@+@+++@@+@@@+++@+@@+ (+"表示被扔下海海的非教徒 @:留在船上活命的教徒) *思考题 有 N 个小孩围 成一圈并依次编号,教师指定从第 M 个小孩开始报数,报到第 S 个小孩即令其出列。然后从下一个孩子继续报 数,数到第 S 个小孩又令其出列,如此直到所有的孩子都出列。求小孩出列的先后顺序。 ----------------------------------------------------------------------------------72.邮票组合 某人有四张 3 分的邮票和三张 5 分的邮票,用这些邮票中的一张或若干张可以得到多少种不同的邮资? *问题分析与算法设计 将问题进行数学分析,不同张数和面值的邮票组成的邮资可用下列公式计算: S=3*i+5*j 其中 i 为 3 分邮柰的张数,j 为 5 分的张数 按题目的要求,3 分的邮票可以取 0、1、2、3、4 张,5 分的邮票可以取 0、1、2、3 张。采用穷举方法进行组合,可以求出这 些不同面值不同张数的邮标组合后的邮资。 *程序与程序注释 #include<stdio.h> int a[27]; void main() { int i,j,k,s,n=0; for(i=0;i<=4;i++) /*i:取三分邮票的张数*/ for(j=0;j<=3;j++) /*j:取 5 分邮票的张数*/ { s=i*3+j*5; /*计算组成的邮票面值*/ for(k=0;a[k];k++) /*查找是否有相同的邮资*/ if(s==a[k])break; if(!a[k]&&s) /*没有找到相同的邮资则满足要求存入数组*/ { a[k]=s; n++; } } printf("%d kinds:",n); for(k=0;a[k];k++) 71 /*输出结果*/ 作者:huang01 发布时间:2004-10-21 17:15:55

printf("%d ",a[k]); printf("\\n"); } *运行结果 19 kinds: 5 10 15 3 8 13 18 6 11 16 21 9 14 19 24 12 17 22 27

------------------------------------------------------------73 和数能表示 1~23 的 5 个正整数 已知五个互不相同的正整数之和为 23,且从这五个数中挑选若干个加起来可以表示从 1 到 23 之内的全部自然数。问这五个数 是什么? *问题分析与算法设计 从计算机程序设计的角度来说,可以用穷举法分解 23,然后判断所分解的五个数是否可以表示 1 到 23 之间的全部整数。 *程序与程序注释 #include<stdio.h> void main() { int a,b,c,d,e,i,j,k,l,m,x,count=0,f=0;

/*f:分解的 5 个数可以表示出 1~23 的标记*/

printf("There are following possble result:\\n"); for(a=1;a<=23;a++) /*将 23 分解为 a,b,c,d,e 五个数*/ for(b=1+a;b<=23-a;b++) for(c=1+b;c<=23-a-b;c++) for(d=1+c;d<=23-a-b-c;d++) { f=1; if((e=23-a-b-c-d)>d) for(f=0,x=1;x<24&&!f;x++) for(f=1,i=0;i<2&&f;i++)

/*判断 5 个数可否表示 1~23*/ /*穷举 5 个数的全部取舍*/

for(j=0;j<2&&f;j++) for(k=0;k<2&&f;k++) for(l=0;l<2&&f;l++) for(m=0;m<2&&f;m++) if(x==a*i+b*j+c*k+d*l+e*m) f=0; if(!f) printf("[%d]: %d %d %d %d %d\\n",++count,a,b,c,d,e); } } *运行结果 There [1]: 1 [2]: 1 [3]: 1 [4]: 1 [5]: 1 [6]: 1 are 23 23 23 24 24 24 following possble result: 5 12 6 11 7 10 5 11 6 10 79

74.可称 1~40 磅的 4 块砝码 法国数学家梅齐亚克在他著名的《数字组合游戏》(1962)中提出了一个问题:一位商人有一个重 40 磅的砝码,一天不小心将砝 码摔成了四块。后来商人称得每块的重量都是整磅数,而且发现这四块碎片可以在天平上称 1 至 40 磅之间的任意重量。请问这四块 碎片各重多少? *问题分析与算法设计 本题是上一题的发展。题目中给出的条件是“在天平上” ,这意味着:同一砝码既可以放在天平的左侧,也可以放在天平的右侧。 若规定重物只能放在天平的左侧,则当天平平衡时有: 重物重量+左侧砝码重量总和=右侧砝码重量总和 由此可得: 72

重物重量=右侧砝码重量总和-左侧砝码重量总和 编程时只要根据以上公式,使“右侧砝码重量总和-左侧砝码重量总和”可以表示 1 到 40 之间的全部重量即可。编程中要注意 的是:怎样采用一种简单的方法来表示一个砝码是在天平的左侧还是在天平的右侧,或是根本没有使用。 以下程序采用 1、 -1 和 0 分别表示上述三种情况,请注意理解。 *程序与程序注释 #include<stdio.h> #include<math.h> void main() { int weight1,weight2,weight3,weight4,d1,d2,d3,d4,x,flag; /*flag:满足题意的标记*/ printf("The weight is broke up as following 4 pieces:"); for(weight1=1;weight1<=40;weight1++) /*将 40 分解成 4 份*/ for(weight2=weight1+1;weight2<=40-weight1;weight2++) for(weight3=weight2+1;weight3<=40-weight1-weight2;weight3++) if((weight4=40-weight1-weight2-weight3)>=weight3) { for(flag=1,x=1;x<41&&flag;x++) /*判断可否称出 1~40 之间的全部重量*/ for(flag=0,d1=1;d1>-2;d1--) /*将重物放在天平的左边*/ for(d2=1;d2>-2&&!flag;d2--) /*1:砝码在天平右边*/ for(d3=1;d3>-2&&!flag;d3--) /*0:不用该砝码*/ for(d4=1;d4>-2&&!flag;d4--) /*-1:砝码在天平的左边*/ if(x==weight1*d1+weight2*d2+weight3*d3+weight4*d4) flag=1; if(flag) printf("%d %d %d %d\\n",weight1,weight2,weight3,weight4); flag=0; } } *运行结果 The weight is broke up as following 4 pieces: 1 ---------------------------------------------------------75.10 个小孩分糖果 十个小孩围成一圈分糖果,老师分给第一个小孩 10 块,第二个小孩 2 块,第三个小孩 8 块,第四个小孩 22 块,第五个小孩 16 块,第六个小孩 4 块,第七个小孩 10 块,第八个小孩 6 块,第九个小孩 14 块,第十个小孩 20 块。然后所有的小孩同时将手中的 糖分一半给右边的小孩;糖块数为奇数的人可向老师要一块。问经过这样几次后大家手中的糖的块数一样多?每人各有多少块糖? *问题分析与算法设计 题目描述的分糖过程是一个机械的重复过程,编程算法完全可以按照描述的过程进行模拟。 *程序与程序注释 #include<stdio.h> void print(int s[]); int judge(int c[]); int j=0; void main() { static int sweet[10]={10,2,8,22,16,4,10,6,14,20}; /*初始化数组数据*/ int i,t[10],l; printf(" child\\n"); printf(" round 1 2 3 4 5 6 7 8 9 10\\n"); printf(".............................\\n"); print(sweet); /*输出每个人手中糖的块数*/ while(judge(sweet)) /*若不满足要求则继续进行循环*/ { for(i=0;i<10;i++) /*将每个人手中的糖分成一半*/ if(sweet%2==0) /*若为偶数则直接分出一半*/ 73 3 9 27

else

t=sweet=sweet/2; /*若为奇数则加 1 后再分出一半*/

t=sweet=(sweet+1)/2; for(l=0;l<9;l++) /*将分出的一半糖给右(后)边的孩子*/ sweet[l+1]=sweet[l+1]+t[l]; sweet[0]+=t[9]; print(sweet); /*输出当前每个孩子中手中的糖数*/ } } int judge(int c[]) { int i; for(i=0;i<10;i++) if(c[0]!=c) return 1; return 0; } void print(int s[]) { int k; printf(" %2d ",j++); for(k=0;k<10;k++) printf("%4d",s[k]); printf("\\n"); }

/*判断每个孩子手中的糖是否相同*/ /*不相同返回 1*/

/*输出数组中每个元素的值*/

----------------------------------------------------------------------------------54. 76.小明买书 作者:huang01 发布时间:2004-10-21 17:16:52

小明假期同爸爸一起去书店,他选中了六本书,每本书的单价分别为:3.1,1.7,2,5.3,0.9 和 7.2。不巧的是,小明的爸爸只 带了十几块钱,为了让小明过一个愉快的假期,爸爸扔然同意买书,但提邮购一个要求,要小明从六本书中选出若干本,使得单价 相加所得的和同 10 最接近。你能够帮助小明解决这个问题吗? *问题分析与算法设计 分析题意,可将题目简化为:从六个数中选出若干个求和,使得和与 10 的差值最小。 题目中隐含两个问题,其一是怎样从六个数中选出若干个数;其二是求与 10 的差。 从六个数中选出若干个数实质是从六个数中选出若干个进行组合。每个数在组合过程中只有两种情况:要么是选中参加求和,要 么是没选中不参加求和。这样就可以使用六重循环对每个数是否参加求和进行全部可能情况的组合。 关于求与 10 的差值应当注意的是:差值的含义是指差的绝对值。例如: “9-10=-1"和"11-10=1",但 9 和 11 这两者与 10 的差值 都是 1。若认为”9“与”10 的差值为-1 就错了。 *程序与程序注释 #include<stdio.h> #include<math.h> void main() { int d[6],m,i,j; long b[63],flag; float c[6],min,x; printf("Please enter the prices of 6 books:"); for(i=0;i<6;i++) scanf("%f",&c); /*输入六个浮点数*/ for(i=0,min=-1,d[0]=0;d[0]<2;d[0]++) /*建立六个数的全部组合并处理*/ for(d[1]=0;d[1]<2;d[1]++) /*i:差值具有 min 组合的数量*/ for(d[2]=0;d[2]<2;d[2]++) /*min:与 10 的最小差值*/ 74

for(d[3]=0;d[3]<2;d[3]++)

/*d[]:组合时是否取该数的标志*/

for(d[4]=0;d[4]<2;d[4]++) for(d[5]=0;d[5]<2;d[5]++) { for(flag=0,x=0,j=5;j>=0;j--) /*flag:将六个数的组合用对应的一个十进制位表示 {

x:对应六个数组合的和*/

x+=c[j]*d[j]; flag=flag*10+d[j]; } x=((x-10>0)? x-10:10-x); /*x: 组合的和与 10 的差*/ if(min<0) { min=x; b[i++]=flag;

/*对第一次计算出的差 min 进行处理*/ /*b[]:有相同的 min 的 flag 的数组 i:b[]数组的下标*/ /*对新的 min 的处理*/

} else if(min-x>1.e-6) { min=x; b[0]=flag; i=1;

} else if(fabs((double)x-min)<1.e-6) b[i++]=flag; /*对相等 min 的处理*/ } for(m=0;m<i;m++) { printf("10(+ -)%.2f=",min); for(flag=b[m],j=0;flag>0;j++,flag/=10) if(flag%10) /*将 b[]中存的标记 flag 还原为各个数的组合*/ if(flag>1) printf("%.2f+",c[j]); else printf("%.2f\\n",c[j]); } } *运行结果 Please enter the prices of 6 books:3.1 10(+ -)0.10=2.00+0.90+7.20 10(+ -)0.10=1.70+2.00+5.30+0.90 10(+ -)0.10=3.10+1.70+5.30 1.7 2.0 5.3 0.9 7.2 /*输出全部 i 个与 10 的差值均为 min 的组合*/

*思考题 可以看出,程序中求六个数所能产生全部组合的算法并不好,使用六重循环进行处理使程序显得不够简洁。可以设计出更通用、 优化的算法产生全部组合。 55. 77.波松瓦酒的分酒趣题

法国著名数学家波瓦松在表年时代研究过一个有趣的数学问题:某人有 12 品脱的啤酒一瓶,想从中倒出 6 品脱,但他没有 6 品 脱的容器,仅有一个 8 品脱和 5 品脱的容器,怎样倒才能将啤酒分为两个 6 品脱呢? *问题分析与算法设计 将 12 品脱酒 8 品脱和 5 品脱的空瓶平分,可以抽象为解不定方程: 8x-5y=6 其意义是:从 12 品脱的瓶中向 8 品脱的瓶中倒 x 次,并且将 5 品脱瓶中的酒向 12 品脱的瓶中倒 y 次,最后在 12 品脱的瓶中剩 余 6 品脱的酒。 用 a,b,c 代表 12 品脱、8 品脱和 5 品脱的瓶子,求出不定方程的整数解,按照不定方程的意义则倒法为: a -> b -> c ->a x y 倒酒的规则如下: 1) 按 a -> b -> c ->a 的顺序; 2) b 倒空后才能从 a 中取 3) c 装满后才能向 a 中倒 75

按以上规则可以编写出程序如下: *程序与程序注释 #include<stdio.h> void getti(int a,int y,int z); int i; /*最后需要分出的重量*/ void main() { int a,y,z; printf("input Full a,Empty b,c,Get i:"); /*a 满瓶的容量

y:第一个空瓶的容量

z:第二个空瓶的容量*/

scanf("%d%d%d%d",&a,&y,&z,&i); getti(a,y,z); /*按 a -> y -> z -> a 的操作步骤*/ getti(a,z,y); /*按 a -> z -> y -> a 的步骤*/ } void getti(int a,int y,int z) { int b=0,c=0; /* b:第一瓶实际的重量 c:第二瓶实际的重量*/ printf(" a%d b%d c%d\\n %4d%4d%4d\\n",a,y,z,a,b,c); while(a!=i||b!=i&&c!=i) /*当满瓶!=i 或另两瓶都!=i*/ { if(!b) { a-=y; b=y;} /*如果第一瓶为空,则将满瓶倒入第一瓶中*/ else if(c==z) { a+=z; c=0;} /*如果第二瓶满,则将第二瓶倒入满瓶中*/ else if(b>z-c) /*如果第一瓶的重量>第二瓶的剩余空间*/ { b-=(z-c);c=z;} /*则将装满第二瓶,第一瓶中保留剩余部分*/ else{ c+=b; b=0;} /*否则,将第一瓶全部倒入第二瓶中*/ printf(" %4d %4d %4d\\n",a,b,c); } } 56. 78.求π的近似值 /*a:满瓶的容量 y:第一个空瓶的容量 z:第二个空瓶的容量*/

请利用“正多边形逼近”的方法求出π的近似值 *问题分析与算法设计 利用“正多边形逼近”的方法求出π值在很早以前就存在,我们的先人祖冲之就是用这种方法在世界上第一个得到精确度达小数 点后第 6 位的π值的。 利用圆内接正六边形边长等于半径的特点将边数翻番,作出正十二边形,求出边长,重复这一过程,就可获得所需精度的π的近 似值。 假设单位圆内接多边形的边长为 2b,边数为 i,则边数加倍后新的正多边形的边长为:

周长为: y=2 * i * x *程序与程序注释

i:为加倍前的正多边形的边数

#include<stdio.h> #include<math.h> void main() { double e=0.1,b=0.5,c,d; long int i; /*i: 正多边形边数*/ for(i=6;;i*=2) /*正多边形边数加倍*/ { d=1.0-sqrt(1.0-b*b); /*计算圆内接正多边形的边长*/ b=0.5*sqrt(b*b+d*d); if(2*i*b-i*e<1e-15) break; /*精度达 1e-15 则停止计算*/ 76

e=b;

/*保存本次正多边形的边长作为下一次精度控制的依据*/ /*输出π值和正多边形的边数*/

} printf("pai=%.15lf\\n",2*i*b);

printf("The number of edges of required polygon:%ld\\n",i); } *运行结果 pai=3.141592653589794 The number of edges of required polygon:100663296 *思考题 请用外切正多边形逼近的方法求π的近似值。

57.

79.求π的近似值(2)

利用随机数法求π的近似值 *问题分析与算法设计 随机数法求π的近似值的思路:在一个单位边长的正方形中,以边长为半径,以一个顶点为圆心,在政权方形上作四分之一圆。 随机的向正方形内扔点,若落入四分之一圆内则计数。重复向正方形内扔足够多的点,将落入四分之一圆内的计数除以总的点数, 其值就是π值四分之一的近似值。 按此方法可直接进行编程,注意:本方法求出的π值只有统计次数足够多时才可能准确。 *程序与程序注释 #include<time.h> #include<stdlib.h> #include<stdio.h> #define N 30000 void main() { float x,y; int c=0,d=0; randomize(); while(c++<=N) { x=random(101); /*x:坐标。产生 0 到 100 之间共 101 个的随机数*/ y=random(101); /*y:坐标。产生 0 到 100 之间共 101 个的随机数*/ if(x*x+y*y<=10000) /*利用圆方程判断点是否落在圆内*/ d++; } printf(" pi=%f\\n",4. *d/N); /*输出求出的π值*/ } *运行结果 多次运行程序,可能得到多个不同的对口果,这是因为采用的是统计规律求出的近似值,只有当统计的次数足够大时,才可能 逼近π值。运行四次,可能的结果是: 3.122267 3.139733 3.133733 3.106800 58. 80.奇数平方的一个有趣性质

编程验证“大于 1000 的奇数其平方与 1 的差是 8 的倍数” 。 *问题分析与算法设计 本题是一个很容易证明的数学定理,我们可以编写程序验证它。 题目中给出的处理过程很清楚,算法不需要特殊设计。可以按照题目的叙述直接进行验证(程序中仅验证到 3000)。 *程序与程序注释 #include<stdio.h> void main() { 77

long int a; for(a=1001;a<=3000;a+=2) { printf("%ld:",a); /*输出奇数本身*/ printf("(%ld*%ld-1)/8",a,a); /*输出(奇数的平方减 1)/8*/ printf("=%ld",(a*a-1)/8); /*输出被 8 除后的商*/ printf("+%ld\\n",(a*a-1)%8); /*输出被 8 除后的余数*/ } } 59. 81.角谷猜想

日本一位中学生发现一个奇妙的“定理” ,请角谷教授证明,而教授无能为力,于是产生角谷猜想。猜想的内容是:任给一个自 然数,若为偶数除以 2,若为奇数则乘 3 加 1,得到一个新的自然数后按照上面的法则继续演算,若干次后得到的结果必然为 1。请 编程验证。 *问题分析与算法设计 本题是一个沿未获得一般证明的猜想,但屡试不爽,可以用程序验证。 题目中给出的处理过程很清楚,算法不需特殊设计,可按照题目的叙述直接进行证。 *程序与程序注释 #include<stdio.h> void main() { int n,count=0; printf("Please enter number:"); scanf("%d",&n); /*输入任一整数*/ do{ if(n%2) { n=n*3+1; } else { n/=2; printf("[%d]: } }while(n!=1); } /*若为偶数 n 除以 2*/ %d/2=%d\\n",++count,2*n,n); /*n 不等于 1 则继续以上过程*/

/*若为奇数,n 乘 3 加 1*/

printf("[%d]:%d*3+1=%d\\n",++count,(n-1)/3,n);

60.

82.四方定理

数论中著名的“四方定理”讲的是:所有自然数至多只要用四个数的平方和就可以表示。 请编程证此定理。 *问题分析与算法设计 本题是一个定理,我们不去证明它而是编程序验证。 对四个变量采用试探的方法进行计算,满足要求时输出计算结果。 *程序与程序注释 #include<stdio.h> #include<stdlib.h> void main() { int number,i,j,k,l; printf("Please enter a number="); scanf("%d",&number); /*输入整数*/ for(i=1;i<number/2;i++) /*试探法。试探 i,j,k,k 的不同值*/ for(j=0;j<=i;j++) 78

for(k=0;k<=j;k++) for(l=0;l<=k;l++) if(number==i*i+j*j+k*k+l*l) {

/*若满足定理要求则输出结果*/

printf(" %d=%d*%d+%d*%d+%d*%d+%d*%d\\n",number,i,i,j,j,k,k,l,l); exit(0); } } *运行结果 1) Please enter a number = 110 110=7*7+6*6+4*4+3*3 2) Please enter a number = 211 211=8*8+7*7+7*7+7*7 3) Please enter a number = 99 99=7*7+5*5+4*4+3*3 61. 83.卡布列克常数

验证卡布列克运算。任意一个四位数,只要它们各个位上的数字是不全相同的,就有这样的规律: 1)将组成该四位数的四个数字由大到小排列,形成由这四个数字构成的最大的四位数; 2)将组成该四位数的四个数字由小到大排列,形成由这四个数字构成的最小的四位数(如果四个数中含有 0,则得到的数不足四 位); 3)求两个数的差,得到一个新的四位数(高位零保留)。 重复以上过程,最后得到的结果是 6174,这个数被称为卡布列克数。 *问题分析与算法设计 题目中给出的处理过程很清楚,算法不需要特殊设计,可按照题目的叙述直接进行验证。 *程序与程序注释 #include<stdio.h> void vr6174(int); void parse_sort(int num,int *each); void max_min(int *each,int *max,int *min); void parse_sort(int num,int *each); int count=0; void main() { int n; printf("Enter a number:"); scanf("%d", &n); /*输入任意正整数*/ vr6174(n); /*调用函数进行验证*/ } void vr6174(int num) { int each[4],max,min; if(num!=6174&&num) { parse_sort(num,each); /*将整数分解,数字存入 each 数组中*/ max_min(each,&max,&min); /*求数字组成的最大值和最小值*/ num=max-min; /*求最大值和最小值的差*/ printf("[%d]: %d-%d=%d\\n",++count,max,min,num); /*输出该步计算过程*/ vr6174(num); /*递归调用自身继续进行卡布列克运算*/ } } void parse_sort(int num,int *each) { int i,*j,*k,temp; for(i=0;i<=4;i++) /*将 NUM 分解为数字*/ { 79

/*若不等于 74 且不等于 0 则进行卡布列克运算*/

j=each+3-i; *j=num%10; num/=10; } for(i=0;i<3;i++) /*对各保数字从小到大进行排序*/

for(j=each,k=each+1;j<each+3-i;j++,k++) if(*j>*k) { temp=*j;*j=*k;*k=temp;} return; } void max_min(int *each,int *max,int *min) /*将分解的数字还原为最大整数和最小整数*/ { int *i; *min=0; for(i=each;i<each+4;i++) /*还原为最小的整数*/ *min=*min*10+*i; *max=0; for(i=each+3;i>=each;i--) *max=*max*10+*i; return; } *运行结果 1) Enter a number:4312 [1]:4312-1234=3078 [2]:8730-378=8352 [3]:8532-2358=6174 2) Enter a number:8720 [1]:8720-278=8442 [2]:8442-2448=5994 [3]:9954-4599=5355 [4]:5553-3555=1998 [5]:9981-1899=8082 [6]:8820-288=8523 [7]:8532-2358=6174 3)Enter a number:9643 [1]:9643-3469=6174 ----------------------------------------------------------------------------------62. 84.尼科彻斯定理 作者:huang01 发布时间:2004-10-21 17:17:41

/*还原为最大的整数*/

验证尼科彻斯定理,即:任何一个整数的立方都可以写成一串连续奇数的和。×× *问题分析与算法设计 本题是一个定理,我们先来证明它是成立的。 对于任一正整数 a,不论 a 是奇数还是偶数,整数(a×a-a+1)必然为奇数。 构造一个等差数列,数列的首项为(a×a-a+1),等差数列的差值为 2(奇数数列),则前 a 项的和为: a× ((a× a-a+1))+2× a(a-1)/2 =a× a× a-a× a+a+a× a-a =a× a× a 定理成立。证毕。 通过定理的证明过程可知 L 所要求的奇数数列的首项为(a×a-a+1),长度为 a。编程的算法不需要特殊设计,可按照定理的证 明过直接进行验证。 *程序与程序注释 80

#include<stdio.h> void main() { int a,b,c,d; printf("Please enter a number:"); scanf("%d",&a); /*输入整数*/ b=a*a*a; /*求整数的三次方*/ printf("%d*%d*%d=%d=",a,a,a,b); for(d=0,c=0;c<a;c++) /*输出数列,首项为 a*a-a+1,等差值为 2*/ { d+=a*a-a+1+c*2; } if(d==b)printf(" Y\\n"); else printf(" N\\n"); } *运行结果 1) Please enter a number:13 13*13*13=2197=157+159+161+163+165+167+169+171+173+175+177+179+181 Y 2) Please enter a number:14 14*14*14=2744=183+185+187+189+191+193+195+197+199+201+203+205+207+209 Y *思考题 本题的求解方法是先证明,在证明的过程中找到编程的算法,然后实现编程。实际上我们也可以不进行证明,直接使用编程中 常用的试探方法来找出该数列,验证该定理。请读者自行设计算法。当然这样得到的数列可能与用定理方法得到的数列不一样。 /*求数列的前 a 项的和*/ printf(c?"+%d":"%d",a*a-a+1+c*2); /*若条件满足则输出“Y”*/ /*否则输出“N”*/

63.

85.回文数的形成

任取一个十进制整数,将其倒过来后与原来的整数相加,得到一个新的整数后重复以上步聚,则最终可得到一个回文数。请编 程验证。 *问题分析与算法设计 回文数的这一形成规则目前还属于一个猜想,尚未得到数学上的证明。有些回文数要经历上百个步聚才能获得。这里通过编程 验证。 题目中给出的处理过程很清楚,算法不需要特殊设计。可按照题目的叙述直接进行验证。 *程序与程序注释 #include<stdio.h> #define MAX 2147483647 long re(long int); int nonres(long int s); void main() { long int n,m; int count=0; printf("Please enetr a number optionaly:"); scanf("%ld",&n); printf("The generation process of palindrome:\\n"); while(!nonres((m=re(n))+n)) /*判断整数与其反序数相加后是否为回文数*/ { if(m+n>=MAX) { printf(" input error,break.\\n"); break; } else { printf("[%d]:%ld+%ld=%ld\\n",++count,n,m,m+n); 81

n+=m; } } printf("[%d]:%ld+%ld=%ld\\n",++count,n,m,m+n); printf("Here we reached the aim at last!\\n"); } long re(long int a) /*求输入整数的反序数*/ { long int t; for(t=0;a>0;a/=10) t=t*10+a%10; return t; } int nonres(long int s) { if(re(s)==s) return 1; else return 0; } 64. 86.自动发牌 /*若是回文数则返回1*/ /*否则返回 0*/ /*判断给定的整数是否是回文数*/ /*将整数反序*/ /*输出最后得到的回文数*/

一副扑克有 52 张牌,打桥牌时应将牌分给四个人。请设计一个程序完成自动发牌的工作。要求:黑桃用 S(Spaces)表示;红桃 用 H(Hearts)表示;方块用 D(Diamonds)表示;梅花用 C(Clubs)表示。 *问题分析与算法设计 按照打桥牌的规定,每人应当有 13 张牌。在人工发牌时,先进行洗牌,然后将洗好的牌按一定的顺序发给每一个人。为了便于 计算机模拟,可将人工方式的发牌过程加以修改:先确定好发牌顺序:1、2、3、4;将 52 张牌顺序编号:黑桃 2 对应数字 0,红桃 2 对应数字 1,方块 2 对应数字 2,梅花 2 对应数字 3,黑桃 3 对应数字 4,红桃 3 对应数字 5,...然后从 52 张牌中随机的为每个 人抽牌。 这里采用 C 语言库函数的随机函数,生成 0 到 51 之间的共 52 个随机数,以产生洗牌后发牌的效果。 *程序与程序注释 #include<stdlib.h> #include<stdio.h> int comp(const void *j,const void *i); void p(int b[],char n[]); void main() { static char n[]={\'2\',\'3\',\'4\',\'5\',\'6\',\'7\',\'8\',\'9\',\'T\',\'J\',\'Q\',\'K\',\'A\'}; int a[53],b1[13],b2[13],b3[13],b4[13]; int b11=0,b22=0,b33=0,b44=0,t=1,m,flag,i; while(t<=52) /*控制发 52 张牌*/ { m=random(52); /*产生 0 到 51 之间的随机数*/ for(flag=1,i=1;i<=t&&flag;i++) /*查找新产生的随机数是否已经存在*/ if(m==a) flag=0; /*flag=1:产生的是新的随机数 flag=0:新产生的随机数已经存在*/ if(flag) { a[t++]=m; /*如果产生了新的随机数,则存入数组*/ if(t%4==0) b1[b11++]=a[t-1]; /*根据 t 的模值,判断当前*/ else if(t%4==1) b2[b22++]=a[t-1]; /*的牌应存入哪个数组中*/ else if(t%4==2) b3[b33++]=a[t-1]; else if(t%4==3) b4[b44++]=a[t-1]; } } qsort(b1,13,sizeof(int),comp); qsort(b2,13,sizeof(int),comp); qsort(b3,13,sizeof(int),comp); 82

/*将每个人的牌进行排序*/

qsort(b4,13,sizeof(int),comp); p(b1,n); p(b2,n); p(b3,n); p(b4,n);

/*分别打印每个人的牌*/

} void p(int b[],char n[]) { int i; printf("\\n\\006 "); /*打印黑桃标记*/ for(i=0;i<13;i++) /*将数组中的值转换为相应的花色*/ if(b/13==0) printf("%c ",n[b%13]); /*该花色对应的牌*/ printf("\\n\\003 "); /*打印红桃标记*/ for(i=0;i<13;i++) if((b/13)==1) printf("%c ",n[b%13]); printf("\\n\\004 "); /*打印方块标记*/ for(i=0;i<13;i++) if(b/13==2) printf("%c ",n[b%13]); printf("\\n\\005 "); /*打印梅花标记*/ for(i=0;i<13;i++) if(b/13==3||b/13==4) printf("%c ",n[b%13]); printf("\\n"); } int comp(const void *j,const void *i) { return(*(int*)i-*(int*)j); } 65. 87.黑白子交换 /*qsort 调用的排序函数*/

有三个白子和三个黑子如下图布置: ○ ○ ○ . ● ● ● 游戏的目的是用最少的步数将上图中白子和黑子的位置进行交换: ● ● ● . ○ ○ ○ 游戏的规则是:(1)一次只能移动一个棋子; (2)棋子可以向空格中移动,也可以跳过一个对方的棋子进入空格,但不能向后跳, 也不能跳过两个子。请用计算机实现上述游戏。 *问题分析与算法设计 计算机解决胜这类问题的关键是要找出问题的规律,或者说是要制定一套计算机行动的规则。分析本题,先用人来解决问题,可 总结出以下规则: (1) 黑子向左跳过白子落入空格,转(5) (2) 白子向右跳过黑子落入空格,转(5) (3) 黑子向左移动一格落入空格(但不应产生棋子阻塞现象),转(5) (4) 白子向右移动一格落入空格(但不应产生棋子阻塞现萌),转(5) (5) 判断游戏是否结束,若没有结束,则转(1)继续。 所谓的“阻塞”现象就是:在移动棋子的过程中,两个尚未到位的同色棋子连接在一起,使棋盘中的其它棋子无法继续移动。例 如按下列方法移动棋子: 0 ○ ○ ○ . ● ● ● 1 ○ ○ . ○ ● ● ● 2 △ ○ ○ ● ○ . ● ● 3 ○ ○ ● . ○ ● ● 4 两个●连在一起产生阻塞 ○ ○ ● ● ○ . ● 或4 两个白连在一起产生阻塞 ○ . ● ○ ○ ● ● 产生阻塞的现象的原因是在第 2 步(△状态)时,棋子○不能向右移动,只能将●向左移动。 83

总结产生阻塞的原因,当棋盘出现“黑、白、空、黑”或“白、空、黑、白”状态时,不能向左或向右移动中间的棋子,只移动 两边的棋子。 按照上述规则, 可以保证在移动棋子的过程中, 不会出现棋子无法移动的现象, 且可以用最少的步数完成白子和黑子的位置交换。 *程序与程序注释 #include<stdio.h> int number; void print(int a[]); void change(int *n,int *m); void main() { int t[7]={1,1,1,0,2,2,2};

/*初始化数组 1:白子

2:黑子

0:空格*/

int i,flag; print(t); while(t[0]+t[1]+t[2]!=6||t[4]+t[5]+t[6]!=3) /*判断游戏是否结束 若还没有完成棋子的交换则继续进行循环*/ { flag=1; /*flag 为棋子移动一步的标记 1:尚未移动棋子 0:已经移动棋子*/ for(i=0;flag&&i<5;i++) /*若白子可以向右跳过黑子,则白子向右跳*/ if(t==1&&t[i+1]==2&&t[i+2]==0) {change(&t,&t[i+2]); print(t); flag=0;} for(i=0;flag&&i<5;i++) /*若黑子可以向左跳过白子,则黑子向左跳*/ if(t==0&&t[i+1]==1&&t[i+2]==2) {change(&t,&t[i+2]); print(t); flag=0;} for(i=0;flag&&i<6;i++) /*若向右移动白子不会产生阻塞,则白子向右移动*/ if(t==1&&t[i+1]==0&&(i==0||t[i-1]!=t[i+2])) {change(&t,&t[i+1]); print(t);flag=0;} for(i=0;flag&&i<6;i++) /*若向左移动黑子不会产生阻塞,则黑子向左移动*/ if(t==0&&t[i+1]==2&&(i==5||t[i-1]!=t[i+2])) { change(&t,&t[i+1]); print(t);flag=0;} } } void print(int a[]) { int i; printf("No. %2d:.............................\\n",number++); printf(" "); for(i=0;i<=6;i++) printf(" | %c",a==1?\'*\':(a==2?\'@\':\' \')); printf(" |\\n .............................\\n\\n"); } void change(int *n,int *m) { int term; term=*n; *n=*m; *m=term; }

----------------------------------------------------------------------------------66. 88.常胜将军 作者:huang01 发布时间:2004-10-21 17:18:12

现有 21 根火柴,两人轮流取,每人每次可以取走 1 至 4 根,不可多取,也不能不取,谁取最后一楰火柴谁输。请编写一个程序 进行人机对弈,要求人先取,计算机后取;计算机一方为“常胜将军” 。 84

*问题分析与算法设计 在计算机后走的情况下,要想使计算机成为“常胜将军” ,必须找出取 关键。根据本题的要求枷以总结出,后走一方取子的数量 与对方刚才一步取子的数量之和等于,就可以保证最后一个子是留给先取子的那个人的。 据此分析进行算法设计就是很简单的工作,编程实现也十分容易。

相关文章:
C语言大赛题目精选(带答案)
C语言大赛题目精选(带答案)_IT认证_资格考试/认证_教育专区。第1题 歌手大赛问题 题目:青年歌手参加歌曲大奖赛,有 10 个评委进行打分,试编程求 这位选手的平均得...
C语言竞赛题目大全
C 语言竞赛题目大全 C 语言竞赛题目大全 语言竞赛题目大全 POWERED BY SYD168 寄存器操作 问题: 问题: 假设在一个 32 位的机器上, 需要将某个外设寄存器的第 ...
c语言程序设计竞赛题及其答案
数学与统计学院 第三届计算机程序设计竞赛题 竞赛需知: 1、 答案必须写在答题...2、 程序采用 C/JAVA /VB/VFP 语言实现均可。 3、 考虑到各种因素,程序的...
C语言竞赛练习题40题(答案)
C语言竞赛练习题40题(答案)_IT/计算机_专业资料。C 语言竞赛练习题 1 1. 求最大数 .问 555555 的约数中最大的三位数是多少? *问题分析与算法设计 根据约数...
C语言程序设计大赛题目
C语言程序设计大赛题目_工学_高等教育_教育专区。1.角谷猜想 日本一位中学生发现一个奇妙的“定理”,请角谷教授证明,而教授无能为力,于是产生角谷 猜想。猜想的...
C语言程序设计大赛题目和答案
C语言程序设计大赛题目和答案C语言程序设计大赛题目和答案隐藏>> C 语言程序设计...五题 平面上有 n 个点(n≤8000),每两个点之间都有一条红色或者是 黑色的...
c语言竞赛题目
c语言竞赛题目精选 27页 免费 c语言竞赛题目收集 16页 免费 C语言竞赛题目大全...题目1 1. 字符串替换(30 分) 题目描述:请编写程序,根据指定的对应关系,把一...
c语言竞赛题目精选
(s2); } 第六题: 金字塔数 space 为塔底边距离左边空白长度 x 塔底中心字母 例:当 space=0,x='C' 输出: A ABA ABCBA 当 space=2,x='E' A ABA...
C语言竞赛题目大全--重点--多看看题目类型!!!
如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 C语言竞赛题目大全--重点--多看看题目类型!!! 隐藏>> C 语言竞赛题目...
C语言竞赛练习题(答案)
C语言竞赛练习题(答案)_IT认证_资格考试/认证_教育专区。计算机二级C 语言竞赛练习题目录 一、穷举 1、求最大数 2、高次方数的尾数 3、借书方案知多少 6、抓...
更多相关标签:
c语言竞赛编程题目 | c语言竞赛 | c语言竞赛题 | c语言程序设计竞赛 | 大学生c语言竞赛 | c语言编程竞赛 | c语言题目 | c语言编程题目 |