C语言竞赛题目大全(10)

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 void main() { int i,num1,num2,temp; printf(\ for(i=1;i<=40;i++) /*穷举40以内的全部分子*/ { num1=40; num2=i; while(num2!=0) /*采用辗转相除法求出最大公约数*/ { temp=num1%num2; num1=num2; num2=temp; } if(num1==1) /*若最大公约数为1，则为最简真分数*/ printf(\ \ } } *运行结果 The fraction serials with demominator 40 is: 1/40 3/40 7/40 9/40 11/40 13/40 17/40 19/40 21/40 23/40 27/40 29/40 31/40 33/40 37/40 39/40 *思考题 按递增顺序依次列出所有分母小于等于40的最简真分数 -------------------------------------------------------------------------------- -- 作者：huang01 -- 发布时间：2004-10-21 17:08:53 -- 38． 47.计算分数的精确值 使用数组精确计算M/N(0

46

由于计算机字长的限制，常规的浮点运算都有精度限制，为了得到高精度的计算结果，就必须自行设计实现方法。 为了实现高精度的计算，可将商存放在一维数组中，数组的每个元素存放一位十进制数，即商的第一位存放在第一个元素中，商的第二位存放在第二个元素中....，依次类推。这样就可以使用数组不表示一个高精度的计算结果。 进行除法运算时可以模拟人的手工操作，即每次求出商的第一位后，将余数乘以10，再计算商的下一位，重复以上过程，当某次计算后的余数为0 时，表示M/N为有限不循环小数某次计算后的余数与前面的某个余数相同时，则M/N为无限循环小数，从该余数第一次出现之后所求得的各位数就是小数的循环节。 程序具体实现时，采用了数组和其它一些技巧来保存除法运算所得到的余数和商的各位数。 *程序与程序注释 #include int remainder[101],quotient[101]; /*remainder:存放除法的余数； quotient:依次存放商的每一位*/ void main() { int m,n,i,j; printf(\ scanf(\ /*输入被除数和除数*/ printf(\ for(i=1;i<=100;i++) /*i: 商的位数*/ { remainder[m]=i; /*m:除的余数 remainder[m]:该余数对应的商的位数*/ m*=10; /*余数扩大10位*/ quotient=m/n; /*商*/ m=m%n; /*求余数*/ if(m==0) /*余数为0 则表示是有限小数*/ { for(j=1;j<=1;j++) printf(\ /*输出商*/ break; /*退出循环*/ } if(remainder[m]!=0) /*若该余数对应的位在前面已经出现过*/ { for(j=1;j<=i;j++) printf(\ /*则输出循环小数*/ printf(\ printf(\ /*输出循环节的位置*/ break; /*退出*/ } } } -------------------------------------------------------------------------------- -- 作者：huang01 -- 发布时间：2004-10-21 17:09:40 -- 39． 51.谁是窃贼 公安人员审问四名窃贼嫌疑犯。已知，这四人当中仅有一名是窃贼，还知道这四人中每人要么是诚实的，要么总是说谎的。在回答公安人员的问题中： 甲说：“乙没有偷，是丁偷的。” 乙说：“我没有偷，是丙便的。” 丙说：“甲没有偷，是乙偷的。” 丁说：“我没有偷。” 请根据这四人的答话判断谁是盗窃者。 *问题分析与算法设计 假设A、B、C、D分别代表四个人，变量的值为1代表该人是窃贱。 由题目已知：四人中仅有一名是窃贱，且这四个人中的每个人要么说真话，要么说假话，而由于甲、乙、丙三人都说了两句话：

47

“X没偷，X偷了”，故不论该人是否说谎，他提到的两人中必有一人是小偷。故在列条件表达式时，可以不关心谁说谎，谁说实话。这样，可以列出下列条件表达式： 甲说：”乙没有偷，是丁偷的。” B+D=1 乙说：“我没有偷，是丙偷有。” B+C=1 丙说：“甲没有偷，是乙偷的。” A+B=1 丁说：“我没有偷。” A+B+C+D=1 其中丁只说了一句话，无法判定其真假，表达式反映了四人中仅有一名是窃贱的条件。 *程序与程序注释 #include void main() { int i,j,a[4]; for(i=0;i<4;i++) /*假定只有第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(\ \ /*成立*/ for(j=0;j<=3;j++) /*输出计算结果*/ if(a[j])printf(\ printf(\ } } } *运行结果 The thief is B. (乙为窃贱。) ---------------------------------------------------- 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 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?\ printf(\ b?\ printf(\ c?\ printf(\ d?\ printf(\ e?\ } } *运行结果 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 (白) -------------------------------------------------------------------------------- -- 作者：huang01 -- 发布时间：2004-10-21 17:10:39 -- 41． 53.迷语博士的难题(1) 诚实族和说谎族是来自两个荒岛的不同民族，诚实族的人永远说真话，而说谎族的人永远说假话。迷语博士是个聪明的人，他要来判断所遇到的人是来自哪个民族的。 迷语博士遇到三个人，知道他们可能是来自诚实族或说谎族的。为了调查这三个人是什么族的，博士分别问了他们的问题，这是他们的对话： 问第一个人：“你们是什么族？”，答：“我们之中有两个来自诚实族。”第二个人说：“不要胡说，我们三个人中只有一个是诚实族的。”第三个人听了第二个人的话后说：“对，就是只有一个诚实族的。” 请根据他的回答判断他们分别是哪个族的。 *问题分析与算法设计 假设这三个人分别为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 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(\ /*输出判断结果*/ printf(\ printf(\ } } *运行结果 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