c语言小程序
-
2023年3月20日发(作者：带阻滤波器)C/C++语言经典、实用、趣味程序设计编程百例精解（1）
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
#include
intmain()
{
doubley;
intx,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 printf("*");/*控制打印左侧的*号*/ for(;x<62-m;x++)printf(""); printf("*n");/*控制打印同一行中对称的右侧*号*/ } return0; } *思考题 如何实现用“*”显示0~360度的sin(x)曲线。 在屏幕上显示0~360度的cos(x)曲线与直线f(x)=45*(y-1)+31的迭加图形。其中cos(x) 图形用“*”表示，f(x)用“+”表示，在两个图形相交的点上则用f(x)图形的符号。 2.绘制余弦曲线和直线 *问题分析与算法设计 本题可以在上题的基础上进行修改。图形迭加的关键是要在分别计算出同一行中两个图形的列方 向点坐标后，正确判断相互的位置关系。为此，可以先判断图形的交点，再分别控制打印两个不 同的图形。 *程序注释与说明 #include #include intmain() { doubley; intx,m,n,yy; for(yy=0;yy<=20;yy++)/*对于第一个y坐标进行计算并在一行中打印图形*/ { y=0.1*yy;/*y：屏幕行方向坐标*/ m=acos(1-y)*10;/*m:cos(x)曲线上y点对应的屏幕列坐标*/ n=45*(y-1)+31;/*n:直线上y点对应的列坐标*/ for(x=0;x<=62;x++)/*x:屏幕列方向坐标*/ if(x==m&&x==n)printf("+");/*直线与cos(x)相交时打印“+”*/ elseif(x==n)printf("+");/*打印不相交时的直线图形*/ elseif(x==m||x==62-m)printf("*");/*打印不相交时的cos(x)图形*/ elseprintf("");/*其它情况打印空格*/ printf("n"); } return0; } *思考题 如何实现sin(x)曲线与cos(x)曲线图形的同时显示。 3.绘制圆 在屏幕上用“*”画一个空心的圆 *问题分析与算法设计 打印圆可利用图形的左右对称性。根据圆的方程： R*R=X*X+Y*Y 可以算出圆上每一点行和列的对应关系。 *程序说明与注释 #include #include intmain() { doubley; intx,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");/*圆的右侧*/ } return0; } *思考题 实现函数y=x2的图形与圆的图形叠加显示 4.歌星大奖赛 在歌星大奖赛中，有10个评委为参赛的选手打分，分数为1~100分。选手最后得分为：去掉 一个最高分和一个最低分后其余8个分数的平均值。请编写一个程序实现。 *问题分析与算法设计 这个问题的算法十分简单，但是要注意在程序中判断最大、最小值的变量是如何赋值的。 *程序说明与注释 #include intmain() { intinteger,i,max,min,sum; max=-32768;/*先假设当前的最大值max为C语言整型数的最小值*/ min=32767;/*先假设当前的最小值min为C语言整型数的最大值*/ sum=0;/*将求累加和变量的初值置为0*/ for(i=1;i<=10;i++) { printf("Inputnumber%d=",i); scanf("%d",&integer);/*输入评委的评分*/ sum+=integer;/*计算总分*/ if(integer>max)max=integer;/*通过比较筛选出其中的最高分*/ if(integer } printf("Canceledmaxscore:%dnCanceledminscore:%dn",max,min); printf("Averagescore:%dn",(sum-max-min)/8);/*输出结果*/ } *运行结果 Inputnumber1=90 Inputnumber2=91 Inputnumber3=93 Inputnumber4=94 Inputnumber5=90 Inputnumber6=99 Inputnumber7=97 Inputnumber8=92 Inputnumber9=91 Inputnumber10=95 Canceledmaxscore:99 Canceledminscore:90 Averagescore:92 *思考题 题目条件不变，但考虑同时对评委评分进行裁判，即在10个评委中找出最公平(即评分最接返 平均分)和最不公平(即与平均分的差距最大)的评委，程序应该怎样实现？ 5.求最大数 问555555的约数中最大的三位数是多少？ *问题分析与算法设计 根据约数的定义，对于一个整数N，除去1和它自身外，凡能整除N的数即为N的约数。因此， 最简单的方法是用2到N-1之间的所有数去除N，即可求出N的全部约数。本题只要求取约数 中最大的三位数，则其取值范围可限制在100到999之间。 *程序说明与注释 #include intmain() { longi; intj; printf("Pleaseinputnumber:"); scanf("%ld",&i); for(j=999;j>=100;j–) if(i%j==0) { printf("Themaxfactorwith3digitsin%ldis:%d,n",i,j); break; } } *运行结果 输入：555555 输出：Themaxfactorwith3digitsin555555is:777 6.高次方数的尾数 求13的13次方的最后三位数 *问题分析与算法设计 解本题最直接的方法是：将13累乘13次方截取最后三位即可。 但是由于计算机所能表示的整数范围有限，用这种“正确”的算法不可能得到正确的结果。事实上， 题目仅要求最后三位的值，完全没有必要求13的13次方的完整结果。 研究乘法的规律发现：乘积的最后三位的值只与乘数和被乘数的后三位有关，与乘数和被乘数的 高位无关。利用这一规律，可以大大简化程序。 *程序说明与注释 #include intmain() { inti,x,y,last=1;/*变量last保存求X的Y次方过程中的部分乘积的后三位*/ printf("InputXandY(X**Y):"); scanf("%d**%d",&x,&y); for(i=1;i<=y;i++)/*X自乘Y次*/ last=last*x%1000;/*将last乘X后对1000取模，即求积的后三位*/ printf("Thelast3digitsof%d**%dis:%dn",x,y,last%1000);/*打印结果*/ } *运行结果 InputXandY(X**Y):13**13 Thelast3digitsof13**13is:253 InputXandY(X**Y):13**20 Thelast3digitsof13**20is:801 7.阶乘尾数零的个数 100!的尾数有多少个零？ *问题分析与算法设计 可以设想：先求出100!的值，然后数一下末尾有多少个零。事实上，与上题一样，由于计 算机所能表示的整数范围有限，这是不可能的。 为了解决这个问题，必须首先从数学上分析在100!结果值的末尾产生零的条件。不难看 出：一个整数若含有一个因子5，则必然会在求100!时产生一个零。因此问题转化为求1到100 这100个整数中包含了多少个因子5。若整数N能被25整除，则N包含2个因子5；若整数 N能被5整除，则N包含1个因子5。 *程序说明与注释 #include intmain() { inta,count=0; for(a=5;a<=100;a+=5)//循环从5开始，以5的倍数为步长，考察整数 { ++count;//若为5的倍数，计数器加1 if(!(a%25))++count;//若为25的倍数，计数器再加1 } printf("Thenumberof0intheendof100!is:%d.n",count);//打印结果 return0; } *运行结果 Thenumberof0intheendof100!is:24. *问题进一步讨论 本题的求解程序是正确的，但是存在明显的缺点。程序中判断整数N包含多少个因子5的方法 是与程序中的100有关的，若题目中的100改为1000，则就要修改程序中求因子5的数目的 算法了。 *思考题 修改程序中求因子5的数目的算法，使程序可以求出任意N!的末尾有多少个零。 8.借书方案知多少 小明有五本新书，要借给A，B，C三位小朋友，若每人每次只能借一本，则可以有多少种不同 的借法？ *问题分析与算法设计 本问题实际上是一个排列问题，即求从5个中取3个进行排列的方法的总数。首先对五本书从 1至5进行编号，然后使用穷举的方法。假设三个人分别借这五本书中的一本，当三个人所借的 书的编号都不相同时，就是满足题意的一种借阅方法。 *程序说明与注释 intmain() { inta,b,c,count=0; printf("TherearediffrentmethodsforXMtodistributebooksto3readers: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,%dn",++count,a,b,c); /*打印可能的借阅方法*/ } *运行结果 TherearediffrentmethodsforXMtodistributebooksto3readers: 1:1,2,32:1,2,43:1,2,54:1,3,25:1,3,4 6:1,3,57:1,4,28:1,4,39:1,4,510:1,5,2 11:1,5,312:1,5,413:2,1,314:2,1,415:2,1,5 16:2,3,117:2,3,418:2,3,519:2,4,120:2,4,3 21:2,4,522:2,5,123:2,5,324:2,5,425:3,1,2 26:3,1,427:3,1,528:3,2,129:3,2,430:3,2,5 31:3,4,132:3,4,233:3,4,534:3,5,135:3,5,2 36:3,5,437:4,1,238:4,1,339:4,1,540:4,2,1 41:4,2,342:4,2,543:4,3,144:4,3,245:4,3,5 46:4,5,147:4,5,248:4,5,349:5,1,250:5,1,3 51:5,1,452:5,2,153:5,2,354:5,2,455:5,3,1 56:5,3,257:5,3,458:5,4,159:5,4,260:5,4,3 9.杨辉三角形 在屏幕上显示杨辉三角形 1 11 121 1331 14641 15101051 ……………………………….. *问题分析与算法设计 杨辉三角形中的数，正是(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个值 之和 将这些特点提炼成数学公式可表示为： 1x=1或x=N+1 c(x,y)= c(x-1,y-1)+c(x-1,y)其它 本程序应是根据以上递归的数学表达式编制的。 *程序说明与注释 #include intmain() { inti,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 printf("n"); } } voidintc(intx,inty)/*求杨辉三角形中第x行第y列的值*/ { intz; if((y==1)||(y==x+1))return1;/*若为x行的第1或第x+1列，则输出1*/ z=c(x-1,y-1)+c(x-1,y);/*否则，其值为前一行中第y-1列与第y列值之和*/ returnz; } *思考题 自行设计一种实现杨辉三角形的方法 10.数制转换 将任一整数转换为二进制形式 *问题分析与算法设计 将十进制整数转换为二进制的方法很多，这里介绍的实现方法利用了C语言能够对位进行操作 的特点。对于C语言来说，一个整数在计算机内就是以二进制的形式存储的，所以没有必要再 将一个整数经过一系列的运算转换为二进制形式，只要将整数在内存中的二进制表示输出即可。 *程序说明与注释 #include voidprintb(int,int); intmain() { intx;printf("Inputnumber:"); scanf("%d",&x); printf("numberofdecimalform:%dn",x); printf("it'sbinaryform:"); printb(x,sizeof(int)*8);/*x:整数sizeof(int):int型在内存中所占的字节数 sizeof(int)*8:int型对应的位数*/ putchar('n'); } voidprintb(intx,intn) { if(n>0) { putchar('0'+((unsigned)(x&(1<>(n-1)));/*输出第n位*/ printb(x,n-1);/*归调用，输出x的后n-1位*/ } } *运行结果 输入：8 输出： numberofdecimalform:8 it'sbunaryform:1000 输入：-8 输出：numberofdecimalform:-8 it'sbinaryform:11000 输入：32767 输出：numberofdecimalform:32767 it'sbinaryform:1111 输入：-32768 输出：numberofdecimalform:-32768 it'sbinaryform:1000 输入：128 输出：numberofdecimalform:128 it'sbinaryform:0000 *问题的进一步讨论 充分利用C语言可以对位进行操作的特点，可以编写许多其它高级语言不便于编写甚至根本无 法编写的程序。位操作是C语言的一大特点，在深入学习C语言的过程中应力求很好掌握。 程序中使用的位运算方法不是最佳的，也可以不用递归操作，大家可以自行对程序进行优化。 *思考题 将任意正整数转换为四进制或八进制数 C/C++语言经典、实用、趣味程序设计编程百例精解（2） 11.打鱼还是晒网 中国有句俗语叫“三天打鱼两天晒网”。某人从1990年1月1日起开始“三天打鱼两天晒网”， 问这个人在以后的某一天中是“打鱼”还是“晒网”。 *问题分析与算法设计 根据题意可以将解题过程分为三步： 1)计算从1990年1月1日开始至指定日期共有多少天； 2)由于“打鱼”和“晒网”的周期为5天，所以将计算出的天数用5去除； 3)根据余数判断他是在“打鱼”还是在“晒网”； 若余数为1，2，3，则他是在“打鱼” 否则是在“晒网” 在这三步中，关键是第一步。求从1990年1月1日至指定日期有多少天，要判断经历年份中 是否有闰年，二月为29天，平年为28天。闰年的方法可以用伪语句描述如下： 如果((年能被4除尽且不能被100除尽)或能被400除尽) 则该年是闰年； 否则不是闰年。 C语言中判断能否整除可以使用求余运算(即求模) *程序说明与注释 #include intdays(structdateday); structdate{ intyear; intmonth; intday; }; intmain() { structdatetoday,term; intyearday,year,day; printf("Enteryear/month/day:"); scanf("%d%d%d",&,&,&);/*输入日期*/ =12;/*设置变量的初始值：月*/ =31;/*设置变量的初始值：日*/ for(yearday=0,year=1990;year<;year++) { =year; yearday+=days(term);/*计算从1990年至指定年的前一年共有多少天*/ } yearday+=days(today);/*加上指定年中到指定日期的天数*/ day=yearday%5;/*求余数*/ if(day>0&&day<4)printf("hewasfishingatthatday.n");/*打印结果*/ elseprintf("Hewassleepingatthatday.n"); } intdays(structdateday) { staticintday_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,}, }; inti,lp; lp=%4==0&&%100!=0||%400==0; /*判定year为闰年还是平年，lp=0为平年，非0为闰年*/ for(i=1;i<;i++)/*计算本年中自1月1日起的天数*/ +=day_tab[lp][i]; ; } *运行结果 Enteryear/month/day:19911025 Hewasfishingatday. Enteryear/month/day:19921025 Hewassleepingatday. Enteryear/month/day:19931025 Hewassleepingatday. *思考题 请打印出任意年份的日历 12.抓交通肇事犯 一辆卡车违反交通规则，撞人后逃跑。现场有三人目击事件，但都没有记住车号，只记下车号的 一些特征。甲说：牌照的前两位数字是相同的；乙说：牌照的后两位数字是相同的，但与前两位 不同；丙是数学家，他说：四位的车号刚好是一个整数的平方。请根据以上线索求出车号。 *问题分析与算法设计 按照题目的要求造出一个前两位数相同、后两位数相同且相互间又不同的整数，然后判断该整数 是否是另一个整数的平方。 *程序说明与注释 #include #include intmain() { inti,j,k,c; for(i=1;i<=9;i++)/*i:车号前二位的取值*/ for(j=0;j<=9;j++)/*j:车号后二位的取值*/ if(i!=j)/*判断二位数字是否相异*/ { k=i*1000+i*100+j*10+j;/*计算出可能的整数*/ for(c=31;c*c if(c*c==k)printf("Lorry–%d.n",k);/*若是，打印结果*/ } } *运行结果 Lorry_7744 13.该存多少钱 假设银行一年整存零取的月息为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 intmain() { inti; floattotal=0; for(i=0;i<5;i++)/*i为年数，取值为0~4年*/ total=(total+1000)/(1+0.0063*12);/*累计算出年初存款数额，第五次的计算 结果即为题解*/ printf("Hemustsave%.2fatfirst.n",total); } *运行结果 Hemustsave4039.44atfirst 14.怎样存钱利最大 假设银行整存整取存款不同期限的月息利率分别为： 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 #include intmain() { inti8,i5,i3,i2,i1,n8,n5,n3,n2,n1; floatmax=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("Formaxinumprofit,heshouldsosavehismoneyinabank:n"); printf("madefixeddepositfor8year:%dtimesn",n8); printf("madefixeddepositfor5year:%dtimesn",n5); printf("madefixeddepositfor3year:%dtimesn",n3); printf("madefixeddepositfor2year:%dtimesn",n2); printf("madefixeddepositfor1year:%dtimesn",n1); printf("Toal:%.2fn",max); /*输出存款方式*/ } *运行结果 Formaxinumprofit,heshouldsosavehismoneyinabank: madefixeddepositfor8year:0times madefixeddepositfor5year:4times madefixeddepositfor3year:0times madefixeddepositfor2year:0times madefixeddepositfor1year:0times Total:8841.01 可见最佳的存款方案为连续四次存5年期。 *思考题 某单位对职工出售住房，每套为2万元。买房付款的方法是： 一次交清，优惠20% 从第一年开始，每年年初分期付款： 5年交清，优惠50%； 10年交清，优惠10%； 20年交清，没有优惠。 现在有人手中正好有2万元，若假定在今后20年中物价和银行利率均保持不变，问他应当选择 哪种付款方式可以使应付的钱最少？ 15.捕鱼和分鱼 A、B、C、D、E五个人在某天夜里合伙去捕鱼，到第二天凌晨时都疲惫不堪，于是各自找地方 睡觉。日上三杆，A第一个醒来，他将鱼分为五份，把多余的一条鱼扔掉，拿走自己的一份。B 第二个醒来，也将鱼分为五份，把多余的一条鱼扔掉，保持走自己的一份。C、D、E依次醒来， 也按同样的方法拿走鱼。问他们合伙至少捕了多少条鱼？ *问题分析与算法设计 根据题意，总计将所有的鱼进行了五次平均分配，每次分配时的策略是相同的，即扔掉一条鱼后 剩下的鱼正好分成五份，然后拿走自己的一份，余下其它的四份。 假定鱼的总数为X，则X可以按照题目的要求进行五次分配：X-1后可被5整除，余下的鱼为 4*(X-1)、5。若X满足上述要求，则X就是题目的解。 *程序说明与注释 #include intmain() { intn,i,x,flag=1;/*flag：控制标记*/ for(n=6;flag;n++)/*采用试探的方法。令试探值n逐步加大*/ { for(x=n,i=1&&flag;i<=5;i++) if((x-1)%5==0)x=4*(x-1)/5; elseflag=0;/*若不能分配则置标记falg=0退出分配过程*/ if(flag)break;/*若分配过程正常结束则找到结果退出试探的过程*/ elseflag=1;/*否则继续试探下一个数*/ } printf("Totalnumberoffishcatched=%dn",n);/*输出结果*/ } *运行结果 Totalnumberoffishcatched=3121 *问题的进一步讨论 程序采用试探法，试探的初值为6，每次试探的步长为1。这是过分保守的做法。可以在进一步 分析题目的基础上修改此值，增大试探的步长值，以减少试探次数。 *思考题 请使用其它的方法求解本题。 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 intmain() { inti,j,n=0,x;/*n为标志变量*/ for(i=23;n==0;i+=2)/*控制试探的步长和过程*/ { for(j=1,x=i;j=11;j++)/*完成出售四次的操作*/ if((x+1)%(j+1)==0)/*若满足整除条件则进行实际的出售操作*/ x-=(x+1)/(j+1); else{x=0;break;}/*否则停止计算过程*/ if(j==5&&x==11)/*若第四次余下11条则满足题意*/ { printf("Thereare%dfishesatfirst.n",i);/*输出结果*/ n=1;/*控制退出试探过程*/ } } } *运行结果 Thereare59fishesatfirst. *思考题 日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。 分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三； 老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿 到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中 的桔子正好一样多。问六兄弟原来手中各有多少桔子？ 17.平分七筐鱼 甲、乙、丙三位鱼夫出海打鱼，他们随船带了21只箩筐。当晚返航时，他们发现有七筐装满了 鱼，还有七筐装了半筐鱼，另外七筐则是空的，由于他们没有秤，只好通过目测认为七个满筐鱼 的重量是相等的，7个半筐鱼的重量是相等的。在不将鱼倒出来的前提下，怎样将鱼和筐平分为 三份？ *问题分析与算法设计 根据题意可以知道：每个人应分得七个箩筐，其中有3.5筐鱼。采用一个3*3的数组a来表示 三个人分到的东西。其中每个人对应数组a的一行，数组的第0列放分到的鱼的整筐数，数组 的第1列放分到的半筐数，数组的第2列放分到的空筐数。由题目可以推出： 。数组的每行或每列的元素之和都为7； 。对数组的行来说，满筐数加半筐数=3.5； 。每个人所得的满筐数不能超过3筐； 。每个人都必须至少有1个半筐，且半筐数一定为奇数 对于找到的某种分鱼方案，三个人谁拿哪一份都是相同的，为了避免出现重复的分配方案，可以 规定：第二个人的满筐数等于第一个人的满筐数；第二个人的半筐数大于等于第一个人的半筐数。 *程序说明与注释 #include inta[3][3],count; intmain() { inti,j,k,m,n,flag; printf("Itexistspossibledistribtionplans:n"); for(i=0;i3*/ { a[0][0]=i; for(j=i;j<=7-i&&j3*/ { a[1][0]=j; if((a[2][0]=7-j-a[0][0])>3)continue;/*第三个人满筐数不能>3*/ if(a[2][0]=前一个人，以排除重复情况*/ 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]的值，半筐数为奇数*/ { 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];/*计算应得到的空筐数量*/ elseflag=0;/*不符合题意则置标记为0*/ if(flag) { printf("No.%dFullbasketSemi–basketEmptyn",++count); for(n=0;n<3;n++) printf("fisher%c:%d%d%dn", 'A'+n,a[n][0],a[n][1],a[n][2]); } } } } } } *运行结果 Itexistspossibledistributionplans: No.1FullbasketSemi–basketEmpty fisherA:151 fisherB:313 fisherC:313 No.2FullbasketSemi–basketEmpty fisherA:232 fisherB:232 fisherC:313 *思考题 晏会上数学家出了一道难题：假定桌子上有三瓶啤酒，癣瓶子中的酒分给几个人喝，但喝各瓶酒 的人数是不一样的。不过其中有一个人喝了每一瓶中的酒，且加起来刚好是一瓶，请问喝这三瓶 酒的各有多少人？ (答案：喝三瓶酒的人数分别是2人、3人和6人) 18.有限5位数 个位数为6且能被3整除的五位数共有多少？ *题目分析与算法设计 根据题意可知，满足条件的五位数的选择范围是10006、10016。。。99996。可设基础数 i=1000，通过计算i*10+6即可得到欲选的数(i的变化范围是1000~999)，再判断该数能否 被3整除。 *程序说明与注释 #include intmain() { longinti; intcount=0;/*count:统计满足条件的五位数的个数*/ for(i=1000;i<9999;i++) if(!((i*10+6)%3))/*判断所选的数能否被3整除*/ count++;/*若满足条件则计数*/ printf("count=%dn",count); } *运行结果 count=2999 *思考题 求100到1000之间有多少个其数字之和为5的整数。 (答案：104，113，122，131，140，203，212，221，230，302，311，320，401， 410，500) 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 intmain() { inti; for(i=0;;i++)/*试探商的值*/ if(((i*8+7)*8+1)*8+1==(34*i+15)*17+4) {/*逆推判断所取得的当前i值是否满足关系式*/ /*若满足则输出结果*/ printf("Therequirednumberis:%dn",(34*i+15)*17+4); break;/*退出循环*/ } } *运行结果 Therequirednumberis:1993 20.一个奇异的三位数 一个自然数的七进制表达式是一个三位数，而这个自然数的九进制表示也是一个三位数，且这两 个三位数的数码正好相反，求这个三位数。 *问题分析与算法设计 根据题意可知，七进制和九进制表示的这全自然数的每一位一定小于7，可设其七进制数形式为 kji(i、j、k的取值分别为1~6)，然后设其九进制表示形式为ijk。 *程序说明与注释 #include intmain() { inti,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("Thespecialnumberwith3digitsis:"); printf("%d%d%d(7)=%d%d%d(9)=%d(10)n",k,j,i,i,j,k,i*9*9+j*9+k); } } *运行结果 Thespecialnumberwith3digitsis:503(7)=305(9)=248(10) C/C++语言经典、实用、趣味程序设计编程百例精解（3） 位反序数 设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 intmain() { inti; for(i=1002;i<1111;i++)/*穷举四位数可能的值*/ if(i%10*1000+i/10%10*100+i/100%10*10+i/1000==i*9) /*判断反序数是否是原整数的9倍*/ printf("Thenumbersatisfiedstatsconditionis:%dn",i); /*若是则输出*/ } *运行结果 Thenumbersatisfiedstatesconditionis:1089 22.求车速 一辆以固定速度行驶的汽车，司机在上午10点看到里程表上的读数是一个对称数(即这个数从 左向右读和从右向左读是完全一样的)，为95859。两小时后里程表上出现了一个新的对称数。 问该车的速度是多少？新的对称数是多少？ *问题分析与算法设计 根据题意，设所求对称数为i，其初值为95589，对其依次递增取值，将i值的每一位分解后与 其对称位置上的数进行比较，若每个对称位置上的数皆相等，则可判定i即为所求的对称数。 *程序说明与注释 #include intmain() { intt,a[5];/*数组a存放分解的数字位*/ longintk,i; for(i=95860;;i++)/*以95860为初值，循环试探*/ { for(t=0,k=100000;k>=10;t++)/*从高到低分解所取i值的每位数*/ {/*字，依次存放于a[0]~a[5]中*/ a[t]=(i%k)/(k/10); k/=10; } if((a[0]==a[4])&&(a[1]==a[3])) { printf("Thenewsymmetricalnumberkelometersis:%d%d%d%d%dn", a[0],a[1],a[2],a[3],a[4]); printf("Thevelocityofthecaris:%.2fn",(i-95859)/2.0); break; } } } *运行结果 Thenewsymmetricalnumberkelometersis:95959. Thevelocityofthecaris:50.00 *思考题 将一个数的数码倒过来所得到的新数叫原数的反序数。如果一个数等于它的反序数，则称它为对 称数。求不超过1993的最大的二进制的对称数。 23.由两个平方三位数获得三个平方二位数 已知两个平方三位数abc和xyz，其中a、b、c、x、y、z未必是不同的；而ax、by、cz是 三个平方二位数。请编程求三位数abc和xyz。 *问题分析与算法设计 任取两个平方三位数n和n1，将n从高向低分解为a、b、c，将n1从高到低分解为x、y、z。 判断ax、by、cz是否均为完全平方数。 *程序说明与注释 #include #include voidf(intn,float*s); intmain() { inti,t; floata[3],b[3]; print("Thepossibleperfectsquarescombinationsare:n"); for(i=11;i<=31;++i)//穷举平方三位数的取值范围 for(t=11;t<=31;++t) { f(i*i,a);//分解平方三位数的各位，每位数字分别存入数组中 f(t*t,b); if(sqrt(a[0]*10+b[0])==(int)sqrt(a[0]*10+b[0]) &&sqrt(a[1]*10+b[1])==(int)sqrt(a[1]*10+b[1]) &&sqrt(a[2]*10+b[2])==(int)sqrt(a[2]*10+b[2])) { printf("%dand%dn,i*i,t*t");//若三个新的数均是完全平方数，则输出 } } } /*———————————————- 分解三位数n的各位数字，将各个数字从高到低依次存入指针s所指向的数组中 ————————————————*/ voidf(intn,float*s) { intk; for(k=1000;k>=10;++s) { *s=(n%k)/(k/10); k/=10; } } *运行结果 Thepossibleperfectsquarescombinationsare: 400and900 841and196 *思考题 求这样一个三位数，该三位数等于其每位数字的阶乘之和。 即abc=a!+b!+c! (正确结果：145=1!+4!+5!) 24.阿姆斯特朗数 如果一个正整数等于其各个数字的立方和，则称该数为阿姆斯特朗数(亦称为自恋性数)。 如407=43+03+73就是一个阿姆斯特朗数。试编程求1000以内的所有阿姆斯特朗数。 *问题分析与算法设计 可采用穷举法，依次取1000以内的各数(设为i)，将i的各位数字分解后，据阿姆斯特朗数的 性质进行计算和判断。 *程序说明与注释 #include intmain() { inti,t,k,a[3]; printf("TherearefollwingArmstrongnumbersmallerthan1000: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"); } *运行结果 TherearefollowingArmstrongnumbersmallerthan1000: 7 25.完全数 如果一个数恰好等于它的因子之和，则称该数为“完全数”。 *问题分析与算法设计 根据完全数的定义，先计算所选取的整数a(a的取值1~1000)的因子，将各因子累加于m， 若m等于a，则可确认a为完全数。 *程序说明与注释 #include intmain() { inta,i,m; printf("Therearefollowingperfectnumberssmallerthan1000:n"); for(a=1;a<1000;a++)/*循环控制选取1~1000中的各数进行判断*/ { for(m=0,i=1;i<=a/2;i++)/*计算a的因子，并将各因子之和m=a，则a是完全数输出*/ if(!(a%i))m+=i; if(m==a) printf("%4d",a); } printf("n"); } *运行结果 TTherearefollowingperfectnumberssmallerthan1000: 628496 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 intmain() { inta,i,b,n; printf("Therearefollowingfriendly–numberspairsmallerthan3000:n"); for(a=1;a<3000;a++)/*穷举1000以内的全部整数*/ { for(b=0,i=1;i<=a/2;i++)/*计算数a的各因子，各因子之和存放于b*/ if(!(a%i))b+=i;/*计算b的各因子，各因子之和存于n*/ for(n=0,i=1;i<=b/2;i++) if(!(b%i))n+=i; if(n==a&&a printf("%4d..%4d",a,b);/*若n=a，则a和b是一对亲密数，输出*/ } } *运行结果 Therearefollowingfriendly–numberspairsmallerthan3000: 220..2841184..12102620..2924 27.自守数 自守数是指一个数的平方的尾数等于该数自身的自然数。例如： 252=625762=577693762=87909376 请求出200000以内的自守数 *问题分析与算法设计 若采用“求出一个数的平方后再截取最后相应位数”的方法显然是不可取的，因为计算机无法表示 过大的整数。 分析手工方式下整数平方(乘法)的计算过程，以376为例： 376被乘数 X376乘数 ———- 2256第一个部分积=被乘数*乘数的倒数第一位 2632第二个部分积=被乘数*乘数的倒数第二位 1128第三个部分积=被乘数*乘数的倒数第三位 ———- 141376积 本问题所关心的是积的最后三位。分析产生积的后三位的过程，可以看出，在每一次的部分积中， 并不是它的每一位都会对积的后三位产生影响。总结规律可以得到：在三位数乘法中，对积的后 三位产生影响的部分积分别为： 第一个部分积中：被乘数最后三位*乘数的倒数第一位 第二个部分积中：被乘数最后二位*乘数的倒数第二位 第三个部分积中：被乘数最后一位*乘数的倒数第三位 将以上的部分积的后三位求和后截取后三位就是三位数乘积的后三位。这样的规律可以推广到同 样问题的不同位数乘积。 按照手工计算的过程可以设计算法编写程序。 *程序说明与注释 #include intmain() { longmul,number,k,ll,kk; printf("Itexistsfollowingautomorphicnmberssmallthan200000: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",number); } } *运行结果 Itexstsfollowingautomorphicnumbnerssmallerthan200000: 2593769 28.回文数 打印所有不超过n(取n<256)的其平方具有对称性质的数(也称回文数)。 *问题分析与算法设计 对于要判断的数n，计算出其平方后(存于a)，将a的每一位进行分解，再按a的从低到高的顺 序将其恢复成一个数k(如n=13，则a=169且k=961)，若a等于k则可判定n为回亠数。 *程序说明与注释 原程序好像有错，而且比较费解，现基于原程序修改如下（如果读者还发现错误请提出）： #include intmain(void) { intm[16],n,i,t,count=0; longunsigneda,k; printf("it'ssquare(palindrome)n"); for(n=1;n<256;n++)/*穷举n的取值范围*/ { k=0;t=1;a=n*n;/*计算n的平方*/ for(i=0;a!=0;i++)/*从低到高分解数a的每一位存于数组m[0]~m[16]*/ { m[i]=a%10;//这个是取得a的个位，整个循环合起来就可以取得各个位 a/=10; } intj=0; for(i–;j if(m[j]!=m[i])break;//只要有一位不是对称，那就说明不是对称，就可以退出了 //所有的位都对称就说明是对称了，这样就可以打印出结果了 if(j>=i)printf("%2d%10d%10dn",++count,n,n*n); } return0; } *运行结果 it'ssquare(palindrome) 111 224 339 411121 522484 626676 710110201 811112321 912114641 1020240804 1121244944 //下面程序是原来的，有错，而且费解 #include intmain(void) { intm[16],n,i,t,count=0; longunsigneda,k; printf("it'ssquare(palindrome)n"); for(n=1;n<256;n++)/*穷举n的取值范围*/ { k=0;t=1;a=n*n;/*计算n的平方*/ for(i=1;a!=0;i++)/*从低到高分解数a的每一位存于数组m[1]~m[16]*/ { m[i]=a%10;//安安注：这个是取得a的个位，整个循环合起来就可以取得各个位,并存于数组 中，为了是下面判断是不是对称 a/=10; } for(;i>1;i–) { k+=m[i-1]*t; t*=10; } if(k==n*n) printf("%2d%10d%10dn",++count,n,n*n); } return0; } *运行结果 it'ssquare(palindrome) 111 224 339 411121 522484 626676 710110201 811112321 912114641 29.求具有abcd=(ab+cd)2性质的四位数 3025这个数具有一种独特的性质：将它平分为二段，即30和25，使之相加后求平方，即 (30+25)2，恰好等于3025本身。请求出具有这样性质的全部四位数。 *问题分析与算法设计 具有这种性质的四位数没有分布规律，可以采用穷举法，对所有四位数进行判断，从而筛选出符 合这种性质的四位数。具体算法实现，可任取一个四位数，将其截为两部分，前两位为a，后两 位为b，然后套用公式计算并判断。 *程序说明与注释 #include intmain() { intn,a,b; printf("Therearefollowingnumberwith4digitssatisfiedconditionn"); 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",n); } } *运行结果 Therearefollowingnumberswith4digitssatisfiedcondition: 2 30.求素数 求素数表中1~1000之间的所有素数 *问题分析与算法设计 素数就是仅能衩1和它自身整除的整数。判定一个整数n是否为素数就是要判定整数n能否被 除1和它自身之外的任意整数整除，若都不能整除，则n为素数。 程序设计时i可以从2开始，到该整数n的1/2为止，用i依次去除需要判定的整数，只要存 在可以整除该数的情况，即可确定要判断的整数不是素数，否则是素数。 *程序说明与注释 #include intmain() { intn1,nm,i,j,flag,count=0; do{ printf("InputSTARTandEND=?"); scanf("%d%d",&n1,&nm);/*输入求素数的范围*/ }while(!(n1>0&&n1 printf("………..PRIMETABLE(%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 /*判定能否被从3到整数的一半中的某一数所整除*/ if(!(i%j))flag=0;/*若能整除则不是素数*/ if(flag)printf(++count%15?"%4d":"%4dn",i); } } *思考题 请找出十个最小的连续自然数，它们个个都是合数(非素数) C/C++语言经典、实用、趣味程序设计编程百例精解（4） 31.歌德巴赫猜想 验证：2000以内的正偶数都能够分解为两个素数之和(即验证歌德巴赫猜想对2000以内的正 偶数成立)。 *问题分析与算法设计 为了验证歌德巴赫猜想对2000以内的正偶数都是成立的，要将整数分解为两部分，然后判断 出分解出的两个整数是否均为素数。若是，则满足题意；否则重新进行分解和判断。 程序中对判断是否为素数的算法进行了改进，对整数判断“用从2开始到该整数的一半”改为“2 开始到该整数的平方根”。原因何在请自行分析。 *程序说明与注释 #include #include intfflag(intn); intmain() { inti,n; for(i=4;i<=2000;i+=2) { for(n=2;n if(fflag(n))/*分别判断两个整数是否均为素数*/ if(fflag(i-n)) { printf("%14d=%d+%dn",i,n,i-n);/*若均是素数则输出*/ break; } if(n==i)printf("error%dn",i); } } intfflag(inti)/*判断是否为素数*/ { intj; if(i<=1)return0; if(i==2)return1; if(!(i%2))return0;/*ifno,return0*/ for(j=3;j<=(int)(sqrt((double)i)+1);j+=2) if(!(i%j))return0; return1;/*ifyes,return1*/ } 32.可逆素数 求四位的可逆素数。可逆素数指：一个素数将其各位数字的顺序倒过来构成的反序数也是素数。 *问题分析与算法设计 本题的重点不是判断素数的方法，而是求一个整数的反序数。求反序数的方法是从整数的末 尾依次截取最后一位数字，每截取一次后整数缩小10倍，将截取的数字作为新的整数的最后一 位（新的整数扩大10倍后加上被截取的数字）。这样原来的整数的数字从低到高被不断地截取， 依次作为新的整数从高到低的各位数字。 *程序说明与注释 #include #include intnum(intnumber); intok(intnumber); intmain() { inti,count; printf("Thereareinvertableprimeswith4digits:n"); for(count=0,i=1001;i<9999;i+=2)//穷举全部的奇数 { if(num(i))//若是可逆素数，则输出 printf(count%9?"%3d:%d":"%3d:%dn",++count,i); } return0; } intnum(intnumber) { inti,j; if(!ok(number))return0;//判断是否为素数 for(i=number,j=0;i>0;i/=10)//按位将整数倒过来，产生反序数 { j=j*10+i%10; } if(number { if(!ok(i))//判断对应的反序数是否为可逆素数 { return0; } else { return1;//若是可逆数素数，则返回1 } } else { return0; } getchar(); return0; } intok(intnumber) { inti,j; if(number%2==0)//判断是否为素数 return0; j=sqrt((double)number)+1;//取整数的平方根为判断的上限 for(i=3;i { if(number%i==0)//若为素数则返回1，否则返回0 return0; } return1; } *思考题 求1000以内的孪生素数。孪生素数是指：若a为素数，且a+2也是素数，则素数a和a+2 称为孪生素数。 33.回文素数 求不超过1000的回文素数。 *问题分析与算法设计 所谓回文素数是指，对一个整数n从左向右和从由向左读其结果值相同且是素数，即称n 为回文素数。所以本题的重点不是判断素数的方法，而是求回文整数。构造回文数的方法很多， 这里仅介绍一种最简单的算法。实现思路是先求出一个整数的回文数，再判断是否为素数。 不超过1000的回文数包括二位和三位的回文数，我们采用穷举法来构造一个整数并求与 其对应的反序数，若整数与其反序数相等，则该整数是回文数。 *程序说明与注释 #include inta(intn) intmain() { inti,j,t,k,s; printf("Followingarepalindromeprimesnotgreaterthan1000:n"); for(i=0;i<=9;++i)//穷举第一位 for(j=0;j<=9;++j)//穷举第二位 for(k=0;k<=9;++k)//穷举第三位 { s=i*100+j*10+k;//计算组成的整数 t=ik*100+j*10+i;//计算对应的反序数 if(i==0&&j==0)//处理整数的前两位为0的情况 { t/100; } elseif(i==0)//处理整数的第一位为0的情况 { t/10; } if(s.10&&s==t&&a(s))//若大于10且为回文素数，则输出 { printf("%dt",s); } } return0; } //判断参数n是否为素数 inta(intn) { inti; for(i=2;i<(n-1)/2;+=i) { if(n%i==0) return0; } return1; } *运行结果 Followingarepalindromeprimesnotgreaterthan1000: 373383727787797919929 *思考题 优化生成回文数的算法。 34.要发就发 “1898–要发就发”。请将不超过1993的所有素数从小到大排成第一行，第二行上的每个素数 都等于它右肩上的素数之差。编程求出：第二行数中是否存在这样的若干个连续的整数，它们的 和恰好是1898？假好存在的话，又有几种这样的情况？ 第一行：2357111317……3 第二行：122424……86 *问题分析与算法设计 首先从数学上分析该问题： 假设第一行中的素数为n[1]、n[2]、n[3]….n[i]、…第二行中的差值为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 #include #defineNUM320 intnumber[NUM];/*存放不超过1993的全部奇数*/ intfflag(inti); intmain() { inti,j,count=0; printf("therearefollwingprimessequencesinfirstrow: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[i]>1898;i++);/*循环查找满足条件的素数*/ if(number[j]-number[i]==1898)/*若两个素数的差为1898，则输出*/ printf("(%d).%3d,…..,%dn",++count,number[i],number[j]); } } intfflag(inti) { intj; if(i<=1)return0;/*判断是否为素数*/ if(i==2)return1; if(!(i%2))return0;/*ifno,return0*/ for(j=3;j<=(int)(sqrt((double)i)+1);j+=2) if(!(i%j))return0; return1; } *运行结果 Therearefollwingprimessequencesinfirstrow: (1).89,……,1987 (2).53,……,1951 (3).3,……,1901 *思考题 将1,2，3，。。。,20这20个连续的自然数排成一圈，使任意两个相邻的自然数之和均为素 数。 35.素数幻方 求四阶的素数幻方。即在一个4X4的矩阵中，每一个格填入一个数字，使每一行、每一列和 两条对角线上的4个数字所组成的四位数，均为可逆素数。 *问题分析与算法设计 有了前面的基础，本题应当说是不困难的。 最简单的算法是：采用穷举法，设定4X4矩阵中每一个元素的值后，判断每一行、每一列和两 条对角线上的4个数字组成的四位数是否都是可逆素数，若是则求出了满足题意的一个解。 这种算法在原理是对的，也一定可以求出满足题意的全部解。但是，按照这一思路编出的程序效 率很低，在微机上几个小时也不会运行结束。这一算法致命的缺陷是：要穷举和判断的情况过多。 充分利用题目中的“每一个四位数都是可逆素数”这一条件，可以放弃对矩阵中每个元素进行的穷 举的算法，先求出全部的四位可逆素数(204个)，以矩阵的行为单位，在四位可逆素数的范围 内进行穷举，然后将穷举的四位整数分解为数字后，再进行列和对角线方向的条件判断，改进的 算法与最初的算法相比，大大地减少了穷举的次数。 考虑矩阵的第一行和最后一行数字，它们分别是列方向四位数的第一个数字和最后一个数字，由 于这些四位数也必须是可逆素数，所以矩阵的每一行和最后一行中的各个数字都不能为偶数或 5。这样穷举矩阵的第一行和最后一行时，它们的取值范围是：所有位的数字均不是偶数或5的 四位可逆数。由于符合这一条件的四位可逆素数很少，所以这一范围限制又一次减少了穷举的次 数。 对算法的进一步研究会发现：当设定了第一和第二行的值后，就已经可以判断出当前的这种组合 是否一定是错误的(尚不能肯定该组合一定是正确的)。若按列方向上的四个两位数与四位可逆数 的前两位矛盾(不是其中的一种组合)，则第一、二行的取值一定是错误的。同理在设定了前三行 数据后，可以立刻判断出当前的这种组合是否一定是错误的，若判断出矛盾情况，则可以立刻设 置新的一组数据。这样就可以避免将四个数据全部设定好以后再进行判断所造成的低效。 根据以上分析，可以用伪语言描述以上改进的算法： 开始 找出全部四位的可逆素数； 确定全部出现在第一和最后一行的四位可逆素数； 在指定范围内穷举第一行 在指定范围内穷举第二行 若第一、第二、三行已出现矛盾，则继续穷举下一个数； 在指定范围内穷举第四行 判断列和对角方向是否符合题意 若符合题意，则输出矩阵； 否则继续穷举下一个数； 结束 在实际编程中，采用了很多程序设计技巧，假如设置若干辅助数组，其目的就是要最大限度的提 高程序的执行效率，缩短运行时间。下面的程序运行效率是比较高的。 *程序说明与注释 #include #include intnumber[210][5];/*存放可逆素数及素数分解后的各位数字*/ intselect[110];/*可以放在矩阵第一行和最后一行的素数的下标*/ intarray[4][5];/*4X4的矩阵，每行0号元素存可逆素数对应的数组下标*/ intcount;/*可逆素数的数目*/ intselecount;/*可以放在矩阵第一行和最后一行的可逆素数的数目*/ intlarray[2][200];/*存放素数前二、三位数的临时数组所对应的数量计数器*/ intlcount[2]; intnum(intnumber); intok(intnumber); voidprocess(inti); voidcopy_num(inti); intcomp_num(intn); intfind1(inti); intfind2(void); intfind0(intnum); voidp_array(void); intmain() { inti,k,flag,cc=0,i1,i4; printf("therearemagicsquareswithinvertableprimesasfollw:n"); for(i=1001;i<9999;i+=2)/*求满足条件的可逆素数*/ { k=i/1000; if(k%2!=0&&k!=5&&num(i))/*若可逆素数的第一位不是偶数或5*/ { 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 { if(larray[0][lcount[0]-1]!=number[i][0]/100) larray[0][lcount[0]++]=number[i][0]/100; if(larray[1][lcount[1]-1]!=number[i][0]/10) larray[1][lcount[1]++]=number[i][0]/10; } for(i1=0;i1 { array[0][0]=select[i1];/*取对应的素数下标*/ copy_num(0);/*复制分解的素数*/ for(array[1][0]=0;array[1][0] { copy_num(1);/*复制分解的数字*/ if(!comp_num(2)) continue;/*若每列的前两位的组成与素数相矛盾，则试探下一个数*/ for(array[2][0]=0;array[2][0] { copy_num(2);/*复制分解的数字*/ if(!comp_num(3)) continue;/*若每列的前三位的组成与素数相矛盾，则试探下一个数*/ for(i4=0;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.%dn",++cc);p_array();}/*输出幻方矩阵*/ } } } } } intnum(intnumber)/*判断是否可逆素数*/ { intj; if(!ok(number))return0; for(j=0;number>0;number/=10)/*将素数变为反序数*/ j=j*10+number%10; if(!ok(j))return0;/*判断反序数是否为素数*/ return1; } intok(intnumber)/*判断是否为素数*/ { inti,j; if(number%2==0)return0; j=sqrt((double)number)+1; for(i=3;i<=j;i+=2) if(number%i==0)return0; return1; } voidprocess(inti)/*将第i个整数分解为数字并存入数组*/ { intj,num; num=number[i][0]; for(j=4;j>=1;j–,num/=10) number[i][j]=num%10; } voidcopy_num(inti)/*将array[i][0]指向的素数的各位数字复制到array[i]中*/ { intj; for(j=1;j<=4;j++) array[i][j]=number[array[i][0>[j]; } intcomp_num(intn)/*判断array中每列的前n位是否与可逆素数允许的前n位矛盾*/ { staticintii;/*用内部静态变量保存前一次查找到的元素下标*/ staticintjj;/*ii:前一次查找前二位的下标，jj:前一次查找前三位的下标*/ inti,num,k,*p;/*p:指向对应的要使用的前一次下标ii或jj*/ int*pcount;/*pcount:指向要使用的临时数组数量的计数器*/ switch(n){/*根据n的值选择对应的一组控制变量*/ case2:pcount=&lcount[0];p=ⅈbreak; case3:pcount=&lcount[1];p=&jj;break; default:return0; } for(i=1;i<=4;i++)/*对四列分别进行处理*/ { for(num=0,k=0;k num=num*10+array[k][i]; if(num<=larray[n-2][*p])/*与前一次最后查找到的元素进行比较*/ for(;*p>=0&&num else for(;plarray[n-2][*p];(*p)++);/*否则向后找*/ if(*p=*pcount) { *p=0;return0; } if(num!=larray[n-2][*p]) return0;/*前n位不是可逆素数允许的值则返回0*/ } return1; } intfind1(inti)/*判断列方向是否是可逆素数*/ { intnum,j; for(num=0,j=0;j<4;j++) num=num*10+array[j][i]; returnfind0(num); } intfind2(void)/*判断对角线方向是否是可逆素数*/ { intnum1,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][i]; if(find0(num1))return(find0(num2)); elsereturn0; } intfind0(intnum)/*查找是否为满足要求的可逆素数*/ { staticintj; if(num=0&&num elsefor(;jnumber[j][0];j++); if(j=count){j=0;return0;} if(num==number[j][0])return1; elsereturn0; } voidp_array(void)/*输出矩阵*/ { inti,j; for(i=0;i<4;i++) { for(j=1;j<=4;j++)printf("%d",array[i][j]); printf("n"); } } *问题的进一步讨论 程序中大量技巧是用于尽早发现矛盾，减少循环次数，缩短运行时间。从实际效果看是相当不错 的。但目前的程序仍然可以进一步优化。 当第四行设定了前三行后，尚未设定的行就没必要再使用穷举的方法，因为列方向设定好的三位 数字已经限制了最后一个数字可能的取值，在可逆数中找出前三位数字与设定好的三位数字相同 的素数。这些素数就是在这一列前面已设定好的三位数字的限制条件下可能的取值。此时每一列 上只有不超过四个可能的取值。找出全部各列可能的取值(可能的四位可逆素数)，求出它们的交 集。若交集为空，即没有共同的可能取值，则列间数据相互矛盾否满足则将交集中的数据填入 矩阵中就是题目的一个解。 算法可再进一步优化。先穷举一、二和四列的数据，然后用上面的算法来确定第三行的值，这样 可进一步缩小穷举的范围，提高运行效率。 分析输出的结果。可以看出本题的基本解只有17种，每个解可通过旋转与反射获得同构的其它 7个解，可以进一步改进程序，只输出17个基本解。 *思考题 用1到16构成一个四阶幻方，要求任意相邻两个方格中的数字之和均为素数。 36.百钱百鸡问题 中国古代数学家张丘建在他的《算经》中提出了著名的“百钱买百鸡问题”：鸡翁一，值钱五，鸡 母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？ *问题分析与算法设计 设鸡翁、鸡母、鸡雏的个数分别为x,y,z，题意给定共100钱要买百鸡，若全买公鸡最多买20 只，显然x的值在0~20之间；同理，y的取值范围在0~33之间，可得到下面的不定方程： 5x+3y+z/3=100 x+y+z=100 所以此问题可归结为求这个不定方程的整数解。 由程序设计实现不定方程的求解与手工计算不同。在分析确定方程中未知数变化范围的前提下， 可通过对未知数可变范围的穷举，验证方程在什么情况下成立，从而得到相应的解。 *程序说明与注释 #include intmain() { intx,y,z,j=0; printf("Folleingarepossibleplanstobuy100fowlswith100Yuan.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=%2dhen=%2dchicken=%2dn",++j,x,y,z); } } *运行结果 Follwingarepossibleplanstobuy100fowlswith100Yuan. 1:cock=0hen=25chicken=75 2:cock=4hen=18chicken=78 3:cock=8hen=11chicken=81 4:cock=12hen=4chicken=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 intmain() { inti=1;/*i为所设的阶梯数*/ while(!((i%2==1)&&(i%3==2)&&(i%5==4)&&(i%6==5)&&(i%7==0))) ++i;/*满足一组同余式的判别*/ printf("Staris_number=%dn",i); } *运行结果 Staris_number=119 *问题的进一步讨论 此题算法还可考虑求1、2、4、5的最小公倍数n，然后判t(t为n-1)≡0(mod7)是否成立， 若不成立则t=t+n,再进行判别，直至选出满足条件的t值。请自行编写程序实现 38.换分币 用一元人民币兑换成1分、2分和5分硬币，共有多少种不同的兑换方法。 *问题分析与算法设计 根据题意设i,j,k分别为兑换的1分、2分、5分硬币所具有的钱数(分)，则i,j,k的值应满足： i+j+k=100 *程序说明与注释 #include intmain() { inti,j,k,count=1; printf("Therearefollwingsmallexchangeplansfor1Yuannote: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*%dt":"%d:1*%d+2*%d+5*%dn",count ++,i,j/2,k/5); } 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 intmain() { intn,a,i; printf("Theserieswithequaldifferenceare: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);/*输出前20项*/ } *运行结果 Theserieswithequaldifferenceare: 25844750535659 40.三色球问题 若一个口袋中放有12个球，其中有3个红的。3个白的和6个黒的，问从中任取8个共有多 少种不同的颜色搭配？ *问题分析与算法设计 设任取的红球个数为i，白球个数为j，则黒球个数为8-i-j，根据题意红球和白球个数的取值范 围是0~3，在红球和白球个数确定的条件下，黒球个数取值应为8-i-j<=6。 *程序说明与注释 #include intmain() { inti,j,count=0; printf("REDBALLWHITEBALLBLACKBALLn"); 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) printf("%2d:%d%d%dn",++count,i,j,8-i-j); } C/C++语言经典、实用、趣味程序设计编程百例精解（5） 41.马克思手稿中的数学题 马克思手稿中有一道趣味数学问题：有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 intmain() { intx,y,z,count=0; printf("MenWomenChildrenn"); 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%dn",++count,x,y,z); } } 42.最大公约数和最小公倍数 求任意两个正整数的最大公约数和(GCD)和最小公倍数(LCM) *问题分析与算法设计 手工方式求两个正整数的蝚大公约数的方法是用辗转相除法，在程序中可以模拟这种方式。 *程序说明与注释 #include intmain() { inta,b,num1,num2,temp; printf("Inputa&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("TheGCDof%dand%dis:%dn",num1,num2,a);/*输出最大公约数*/ printf("TheLCMofthemis:%dn",num1*num2/a);/*输出最小公倍数*/ } *运行结果 &b:2055 TheGCDof20and55is:5 TheLCMofthemis:220 &b:1771 TheGCDof17and71is:1 TheLCMofthemis:1207 &b:2488 TheGCDof24and88is:8 TheLCMofthemis:264 &b:3585 TheGCDof35and85is:5 TheLCMofthemis:595 *思考题 求一个最小的正整数，这个正整数被任意n(2<=n<=10)除都是除不尽的，而且余数总是(n-1)。 例如：被9除时的余数为8。要求设计一个算法，不允许枚举与除2、除3、….、除9、除10 有关的命令，求出这个正整数。 43.分数比较 比较两个分数的大小。 *问题分析与算法设计 人工方式下比较分数大小最常用的方法是：进行分数的通分后比较分子的大小。可以编程模拟手 式方式。 *程序说明与注释 #include intzxgb(inta,intb); intmain() { inti,j,k,l,m,n; printf("InputtwoFENSHU: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/%dn",i,j,k,l);/*比较分子的大小*/ elseif(m==n)printf("%d/%d=%d/%dn",i,j,k,l);/*输出比较的结果*/ elseprintf("%d/%d<%d/%dn",i,j,k,l); } intzxgb(inta,intb) { longintc; intd; if(a for(c=a*b;b!=0;) { d=b;b=a%b;a=d; } return(int)c/a; } *运行结果 输入：4/5，6/7输出：4/5<6/7 输入：8/4，16/32输出：8/4>16/32 输入：16/32，4/8输出：16/32=4/8 44.分数之和 求这样的四个自然数p,q,r,s(p<=q<=r<=s)，使得以下等式成立： 1/p+1/q+1/r+1/s=1 *问题分析与算法设计 若规定p<=q<=r<=s，将原式通分、化简并整理后得到： 2<=p<5p<=q<7q 采用最简单的穷举方法可以很方便的求解。 程序与程序注释: #include intmain() { intp,q,r,s,count=0; printf("The4fractionswhichsumisequal1are: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=1n",++count,p,q,r,s); /*输出结果*/ } } *运行结果 *思考题 将1、2、3、4、5、6、7、8、9九个数字分成以下三种分数形式之一，每个数字只能用一次，使 得该分数刚好等于一个整数。 求所有满足条件的表示形式。 (参考答案：某些自然数没有这种表示形式，如：1、2、3、4、15、18等。此外整数100有11 种满足条件的表示形式；89的表示形式最多，共有36种；三种形式中，最大可表示的整数为794。) 45.将真分数分解为埃及分数 分子为1的分数称为埃及分数，现输入一个真分数，请将该分数分解为埃及分数。 如：8/11=1/2+1/5+1/55+1/110。 *问题分析与算法设计 若真分数的分子a能整除分母b，则真分数经过化简就可以得到埃及分数，若真分数的分子不能 整除分母，则可以从原来的分数中分解出一个分母为b/a+1的埃及分数。用这种方法将剩余部分 反复分解，最后可得到结果。 *程序说明与注释 /*安安注：对源程序作稍许修改，主要是添加了一个外循环，可以直接计算多个真分数的埃及分 数，按Ctrl-C退出。具体的算法我没有认真看，有问题请提出，谢谢*/ #include intmain(void) { longinta,b,c; while(true) { printf("Pleaseenteraoptionalfraction(a/b):"); scanf("%ld/%ld",&a,&b);/*输入分子a和分母b*/ printf("Itcanbedecomposedto:"); while(true) { if(b%a)/*若分子不能整除分母*/ c=b/a+1;/*则分解出一个分母为b/a+1的埃及分数*/ else{c=b/a;a=1;}/*否则，输出化简后的真分数(埃及分数)*/ if(a==1) { printf("1/%ldn",c); break;/*a为1标志结束*/ } else printf("1/%ld+",c); a=a*c-b;/*求出余数的分子*/ b=b*c;/*求出余数的分母*/ if(a==3)/*若余数为3，输出最后两个埃及分数*/ {printf("1/%ld+1/%ldn",b/2,b);break;} } } return0; } *运行结果 Pleaseenteraoptionalfraction(a/b):1/6 Itcanbedecomposedto:1/6 Pleaseenteraoptionalfraction(a/b):20/33 Itcanbedecomposedto:1/2+1/10+1/165 Pleaseenteraoptionalfraction(a/b):10/89 Itcanbedecomposedto:1/9+1/801 Pleaseenteraoptionalfraction(a/b):19/99 Itcanbedecomposedto:1/6+1/40+1/3960 Pleaseenteraoptionalfraction(a/b):8/87 Itcanbedecomposedto:1/11+1/957 ……（按ctrl-c退出） 46.列出真分数序列 按递增顺序依次列出所有分母为40，分子小于40的最简分数。 *问题分析与算法设计 对分子采用穷举法，利用最大公约数的方法，判断分子与40是否构成真分数。 *程序说明与注释 #include intmain() { inti,num1,num2,temp; printf("Thefractionserialswithdemominator40is: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)/*若最大公约数为1，则为最简真分数*/ printf("%d/40",i); } } *运行结果 Thefractionserialswithdemominator40is: 1/403/407/409/4011/4013/4017/4019/40 21/4023/4027/4029/4031/4033/4037/4039/40 *思考题 按递增顺序依次列出所有分母小于等于40的最简真分数 47.计算分数的精确值 使用数组精确计算M/N(0 环节，同时要求输出循环节的起止位置(小数位的序号) *问题分析与算法设计 由于计算机字长的限制，常规的浮点运算都有精度限制，为了得到高精度的计算结果，就必须自 行设计实现方法。 为了实现高精度的计算，可将商存放在一维数组中，数组的每个元素存放一位十进制数，即商的 第一位存放在第一个元素中，商的第二位存放在第二个元素中….，依次类推。这样就可以使用 数组不表示一个高精度的计算结果。 进行除法运算时可以模拟人的手工操作，即每次求出商的第一位后，将余数乘以10，再计算商 的下一位，重复以上过程，当某次计算后的余数为0时，表示M/N为有限不循环小数某次计算 后的余数与前面的某个余数相同时，则M/N为无限循环小数，从该余数第一次出现之后所求得的 各位数就是小数的循环节。 程序具体实现时，采用了数组和其它一些技巧来保存除法运算所得到的余数和商的各位数。 *程序说明与注释 #include intremainder[101],quotient[101];/*remainder:存放除法的余数；quotient:依次存放商的 每一位*/ intmain() { intm,n,i,j; printf("Pleaseinputafraction(m/n)(<0 scanf("%d/%d",&m,&n);/*输入被除数和除数*/ printf("%d/%dit'saccuracyvalueis:0.",m,n); for(i=1;i<=100;i++)/*i:商的位数*/ { remainder[m]=i;/*m:除的余数remainder[m]:该余数对应的商的位数*/ m*=10;/*余数扩大10位*/ quotient[i]=m/n;/*商*/ m=m%n;/*求余数*/ if(m==0)/*余数为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("ntanditisainfinitecyclicfractionfrom%dn",remainder[m]); printf("tdigitto%ddigitafterdecimalpoint.n",i); /*输出循环节的位置*/ break;/*退出*/ } } } *思考题 使用数组实现计算MXN的精确值 48.新娘和新郞 三对情侣参加婚礼，三个新郞为A、B、C，三个新娘为X、Y、Z。有人不知道谁和谁结婚，于是 询问了六位新人中的三位，但听到的回答是这样的：A说他将和X结婚；X说她的未婚夫是C；C 说他将和Z结婚。这人听后知道他们在开玩笑，全是假话。请编程找出谁将和谁结婚。 *问题分析与算法设计 将A、B、C三人用1,2，3表示，将X和A结婚表示为“X=1”，将Y不与A结婚表示为“Y!=1”。 按照题目中的叙述可以写出表达式： x!=1A不与X结婚 x!=3X的未婚夫不是C z!=3C不与Z结婚 题意还隐含着X、Y、Z三个新娘不能结为配偶，则有： x!=y且x!=z且y!=z 穷举以上所有可能的情况，代入上述表达式中进行推理运算，若假设的情况使上述表达式的结果 均为真，则假设情况就是正确的结果。 *程序说明与注释 #include intmain() { intx,y,z; for(x=1;x<=3;x++)/*穷举x的全部可能配偶*/ for(y=1;y<=3;y++)/*穷举y的全部可能配偶*/ for(z=1;z<=3;z++)/*穷举z的全部可能配偶*/ if(x!=1&&x!=3&&z!=3&&x!=y&&x!=z&&y!=z)/*判断配偶是否满足题意*/ { printf("Xwillmarryto%c.n",'A'+x-1);/*打印判断结果*/ printf("Ywillmarryto%c.n",'A'+y-1); printf("Zwillmarryto%c.n",'A'+z-1); } } *运行结果 XwillmarrytoB.(X与B结婚) YwillmarrytoC.(Y与C结婚) ZwillmarrytoA.(Z与A结婚) 49.委派任务 某侦察队接到一项紧急任务，要求在A、B、C、D、E、F六个队员中尽可能多地挑若干人，但有 以下限制条件： 1)A和B两人中至少去一人； 2)A和D不能一起去； 3)A、E和F三人中要派两人去； 4)B和C都去或都不去； 5)C和D两人中去一个； 6)若D不去，则E也不去。 问应当让哪几个人去？ *问题分析与算法设计 用A、B、C、D、E、F六个变量表示六个人是否去执行任务的状态，变量的值为1，则表示该人 去；变量的值为0，则表示该人不参加执行任务，根据题意可写出表达式： a+b>1A和B两人中至少去一人； a+d!=2A和D不能一起去； a+e+f==2A、E、F三人中要派两人去； b+c==0或b+c==2B和C都去或都不去； c+d==1C和D两人中去一个； d+e==0或d==1若D不去，则E也不去(都不去；或D去E随便)。 上述各表达式之间的关系为“与”关系。穷举每个人去或不去的各种可能情况，代入上述表达式 中进行推理运算，使上述表达式均为“真”的情况就是正确的结果。 *程序说明与注释 #include intmain() { inta,b,c,d,e,f; for(a=1;a>=0;a–)/*穷举每个人是否去的所有情况*/ for(b=1;b>=0;b–)/*1:去0:不去*/ for(c=1;c>=0;c–) for(d=1;d>=0;d–) for(e=1;e>=0;e–) for(f=1;f>=0;f–) if(a+b>=1&&a+d!=2&&a+e+f==2 &&(b+c==0||b+c==2)&&c+d==1 &&(d+e==0||d==1)) { printf("Awill%sbeassigned.n",a?"":"not"); printf("Bwill%sbeassigned.n",b?"":"not"); printf("Cwill%sbeassigned.n",c?"":"not"); printf("Dwill%sbeassigned.n",d?"":"not"); printf("Ewill%sbeassigned.n",e?"":"not"); printf("Fwill%sbeassigned.n",f?"":"not"); } } *运行结果 Awillbeassigned.(去) Bwillbeassigned.(去) Cwillbeassigned.(去) Dwillnotbeassigned.(不去) Ewillnotbeassigned.(不去) Fwillbeassigned.(去) *思考题 某参观团按以下条件限制从A、B、C、D、E五个地方中选若干参观点： 1)如去A，则必须去B； 2)D、E两地只能去一地； 3)B、C两地只能去一地； 4)C、D两地都去或都不去； 5)若去E地，A、D也必去。 问该团最多能去哪几个地方？ 50.谁在说谎 张三说李四在说谎，李四说王五在说谎，王五说张三和李四都在说谎。现在问：这三人中到底谁 说的是真话，谁说的是假话？ *问题分析与算法设计 分析题目，每个人都有可能说的是真话，也有可能说的是假话，这样就需要对每个人所说的话进 行分别判断。假设三个人所说的话的真假用变量A、B、C表示，等于1表示该人说的是真话；表 示这个人说的是假话。由题目可以得到： *张三说李四在说谎张三说的是真话：a==1&&b==0 或张三说的是假话：a==0&&b==1 *李四说王五在说谎李四说的是真话：b==1&&c==0 或李四说的是假话：b==0&&c==1 *王五说张三和李四都在说谎王五说的是真话：c==1&&a+b==0 或王五说的是假话：c==0&&a+b!=0 上述三个条件之间是“与”的关系。将表达式进行整理就可得到C语言的表达式： (a&&!b||!a&&b)&&(b&&!c||!b&&c)&&(c&&a+b==0||!c&&a+b!=0) 穷举每个人说真话或说假话的各种可能情况，代入上述表达式中进行推理运算，使上述表达式均 为“真”的情况就是正确的结果。 *程序说明与注释 #include intmain() { inta,b,c; for(a=0;a<=1;a++) for(b=0;b<=1;b++) for(c=0;c<=1;c++) if((a&&!b||!a&&b)&&(b&&!c||!b&&c)&&(c&&a+b==0||!c&&a+b!=0)) { printf("Zhangsantolda%s.n",a?"truth":"lie"); printf("Lisitolda%s.n",b?"truch":"lie"); printf("Wangwutolda%s.n",c?"truch":"lie"); } } *运行结果 Zhangsantoldalie(张三说假话) Lisitoldatruch.(李四说真话) Wangwutoldalie.(王五说假话) C/C++语言经典、实用、趣味程序设计编程百例精解（6） 51.谁是窃贼 公安人员审问四名窃贼嫌疑犯。已知，这四人当中仅有一名是窃贼，还知道这四人中每人要么是 诚实的，要么总是说谎的。在回答公安人员的问题中： 甲说：“乙没有偷，是丁偷的。” 乙说：“我没有偷，是丙便的。” 丙说：“甲没有偷，是乙偷的。” 丁说：“我没有偷。” 请根据这四人的答话判断谁是盗窃者。 *问题分析与算法设计 假设A、B、C、D分别代表四个人，变量的值为1代表该人是窃贼。 由题目已知：四人中仅有一名是窃贼，且这四个人中的每个人要么说真话，要么说假话，而由于 甲、乙、丙三人都说了两句话：“X没偷，X偷了”，故不论该人是否说谎，他提到的两人中必有 一人是小偷。故在列条件表达式时，可以不关心谁说谎，谁说实话。这样，可以列出下列条件表 达式： 甲说：”乙没有偷，是丁偷的。”B+D=1 乙说：“我没有偷，是丙偷有。”B+C=1 丙说：“甲没有偷，是乙偷的。”A+B=1 丁说：“我没有偷。”A+B+C+D=1 其中丁只说了一句话，无法判定其真假，表达式反映了四人中仅有一名是窃贼的条件。 *程序说明与注释 #include intmain() { inti,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; elsea[j]=0; if(a[3]+a[1]==1&&a[1]+a[2]==1&&a[0]+a[1]==1)/*判断条件是否成立*/ { printf("Thethiefis");/*成立*/ for(j=0;j<=3;j++)/*输出计算结果*/ if(a[j])printf("%c.",j+'A'); printf("n"); } } } *运行结果 ThethiefisB.(乙为窃贼。) 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 intmain() { inta,b,c,d,e; for(a=0;a<=1;a++)/*黑色：0白色：1*/ 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("Aispastedapieceof%spaperonhisforehead.n", a?"white":"black"); printf("Bispastedapieceof%spaperonhisforehead.n", b?"white":"black"); printf("Cispastedapieceof%spaperonhisforehead.n", c?"white":"black"); printf("Dispastedapieceof%spaperonhisforehead.n", d?"white":"black"); printf("Eispastedapieceof%spaperonhisforehead.n", e?"white":"black"); } } *运行结果 Aispastedapaperofblackpaperonhisforehead.(黑) Bispastedapaperofblackpaperonhisforehead.(黑) Cispastedapaperofwhitepaperonhisforehead.(白) Dispastedapaperofblackpaperonhisforehead.(黑) Eispastedapaperofwhitepaperonhisforehead.(白) 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 intmain() { inta,b,c; 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("Aisa%s.n",a?"honest":"lier");/*输出判断结果*/ printf("Bisa%s.n",b?"honest":"lier"); printf("Cisa%s.n",c?"honest":"lier"); } } *运行结果 Aisalier(说谎族) Bisalier(说谎族) Cisalier(说谎族) *思考题 迷语博士遇到四个人，知道他们可能是来自诚实族和说谎族的。为了调查这四个人是什么族的， 博士照例进行询问：”你们是什么族的？“ 第一人说：”我们四人全都是说谎族的。“ 第二人说：”我们之中只有一人是说谎族的。“ 第三人说：”我们四人中有两个是说谎族的。“ 第四人说：”我是诚实族的。“ 问自称是“诚实族”的第四个人是否真是诚实族的？ (答案：第四个人是诚实族的。) 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 根据左边人的回答可以推出：若他们是诚实族，则中间的人也是诚实族；若他不是诚实族，则中 间的人也不是诚实族。以上条件可以表示为： c&&!b&&!bb||(!c&&!cc)&&(b||bb)||!c&&cc 将全部逻辑条件联合在一起，利用穷举的方法求解，凡是使上述条件同时成立的变量取值就是题 目的答案。 *程序说明与注释 #include intmain() { inta,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("Themanstandonleftisa%s.n", aa?"double–dealer":(a?"honest":"lier")); printf("Themanstandonleftisa%s.n", bb?"double–dealer":(b?"honest":"lier")); printf("Themanstandonleftisa%s.n", cc?"double–dealer":(c?"honest":"lier")); /*输出最终的推理结果*/ } } *运行结果 Themanstandonleftisadouble–dealer.(左边的人是两面族的) Themanstandoncenterisalier.(中间的人是说谎族的) Themanstandonrightisahonest.(右边的人是诚实族的) *思考题 迷语博士遇到三个人，便问第一个人：“你是什么族的？”，回答：“诚实族的。”问第二个人：“你 是什么族的？”，答：“说谎族的。”博士又问第二个人：“第一个人真的是诚实族的吗？”，答：“是 的。”问第三个人：“你是什么族的？”，答：“诚实族的。”博士又问第三个人：“第一个人是什么 族的？”，答：“两面族的。” 请判断这个人到底是哪个民族的？ (答案：第一个人是诚实族的，第二个人是两面族的，第三人是说谎族。) 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七位大 夫。 *程序说明与注释 #include #include inta[8]; char*day[]={"","MONDAY","TUESDAY","WEDNESDAY","THURSDAYT", "FRIDAY","SATUDAY","SUNDAY"};/*建立星期表*/ intmain() { inti,j,t; a[4]=6;/*星期四是F值班*/ for(i=1;i<=3;i++) { a[i]=2;/*假设B值班的日期*/ if(!a[i+3])a[i+3]=7;/*若三天后无人值班则安排G值班*/ else{a[i]=0;continue;}/*否则B值班的日期不断对*/ for(t=1;t<=3;t++)/*假设E值班的时间*/ { if(!a[t])a[t]=5;/*若当天无人值班则安排E值班*/ elsecontinue; 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值班*/ elsecontinue; if(!a[j+1])a[j+1]=1;/*C之后一天无人值班则应当是A值班*/ else{a[j]=0;continue;}/*否则A值班日期不对*/ for(i=1;i<=7;i++)/*安排完毕，输出结果*/ printf("Doctor%cisonduty%s.n",'A'+a[i]-1,day[i]); exit(0); } } } } *运行结果 DoctorEisondutyMONDAY.(星期一：E) DoctorBisondutyTUESDAY.(星期二：B) DoctorDisondutyWEDNESDAY.(星期三：D) DoctorFisondutyTHUESDAY.(星期四：F) DoctorGisondutyFRIDAY.(星期五：G) DoctorCisondutySATURDAY.(星期六：C) DoctorAisondutySUNDAY.(星期日：A) *思考题 在本题的求解过程中，我们只考虑了一星期之内的情况，没有考虑跨周的情况。对于“B大夫比 G大夫早三天值班的”条件只是简单的认为是在同一周内早三天。若考虑跨周的情况就可能出现： B大夫星期一值班，而G大夫是上周的星期五。同样，对“F大夫的值班日在B和C大夫的中间” 这个条件，也可以扩展为：“只要F大夫的值班日在B和C大夫的中间就可以”。 请考虑允许跨周的情况下，可能的时间安排表。 56.区分旅客国籍 在一个旅馆中住着六个不同国籍的人，他们分别来自美国、德国、英国、法国、俄罗斯和意大利。 他们的名字叫A、B、C、D、E和F。名字的顺序与上面的国籍不一定是相互对应的。现在已知： 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 .. C(技师) D...... E(教师)X..X.X F...X.. 根据此表使用消元法进行求解，可以方便地得到问题的答案。 将条件矩阵输入计算机，用程序实现消去算法是很容易的。 *程序说明与注释 #include char*m[7]={"","U.S","U.K","FRANCE","GER","ITALI","EUSSIAN"};/*国名*/ intmain() { inta[7][7],i,j,t,e,x,y; for(i=0;i<7;i++)/*初始化条件矩阵*/ for(j=0;j<7;j++)/*行为人，列为国家，元素的值表示某人是该国人*/ a[i][j]=j; for(i=1;i<7;i++)/*条件矩阵每一列的第0号元素作为该列数据处理的标记*/ a[0][i]=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][i])/*若该列尚未处理，则进行处理*/ { for(e=0,j=1;j<7;j++)/*j:行坐标e:该列中非0元素计数器*/ if(a[j][i]){x=j;y=i;e++;} if(e==1)/*若该列只有一个元素为非零，则进行消去操作*/ { for(t=1;t<7;t++) if(t!=i)a[x][t]=0;/*将非零元素所在的行的其它元素置0*/ a[0][y]=0;/*设置该列已处理完毕的标记*/ } } } for(i=1;i<7;i++)/*输出推理结果*/ { printf("%ciscomingfrom",'A'-1+i); for(j=1;j<7;j++) if(a[i][j]!=0) {printf("%s.n",m[a[i][j>);break;} } } *运行结果 AiscomingfromITALY.(意大利人) BiscomingfromEUSSIAN.(俄罗斯人) CiscomingfromU.K..(英国人) DiscomingfromGER.(德国人) EiscomingfromFRANCE.(法国人) FiscomingfromU.S..(美国人) *问题的进一步讨论 生成条件矩阵然后使用消去法进行推理判断是一种常用的方法。对于解决较为复杂的逻辑问题是 十分有效的。 *思考题 地理课上老师给出一张没有说明省份的中国地图，从中选出五个省从1到5编号，要大家写出 省份的名称。交卷后五位同学每人只答了二个省份的名称如下，且每人只答对了一个省，问正确 答案是什么？ A答：2号陕西，5号甘肃B答：2号湖北，4号山东 C答：1号山东，5号吉林D答：3号湖北，4号吉林 E答：2号甘肃，3号陕西 57.谁家孩子跑最慢 张王李三家各有三个小孩。一天，三家的九个孩子在一起比赛短跑，规定不分年龄大小，跑第一 得9分，跑第2得8分，依此类推。比赛结果各家的总分相同，且这些孩子没有同时到达终点 的，也没有一家的两个或三个孩子获得相连的名次。已知获第一名的是李家的孩子，获得第二的 是王家的孩子。问获得最后一名的是谁家的孩子？ *问题分析与算法设计 按题目的条件，共有1+2+3+…+9=45分，每家的孩子的得分应为15分。根据题意可知：获 第一名的是李家的孩子，获第二名的是王家的孩子，则可推出：获第三名的一定是张家的孩子。 由“这些孩子没有同时到达终点的”可知：名次不能并列，由“没有一家的两个或三个孩子获得相 连的名次”可知：第四名不能是张家的孩子。 程序中为了方便起见，直接用分数表示。 *程序说明与注释 #include intscore[4][4]; intmain() { inti,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")) for(j=1;j<=3;j++) { printf("%d",score[i][j]);/*输出各家孩子的得分情况*/ if(score[i][j]==1)who=i;/*记录最后一名的家庭序号*/ } if(who==1)/*输出最后判断的结果*/ printf("ThelastonearrivedtoendisachildfromfamilyZhang.n"); elseif(who==2) printf("ThelastonearrivedtoendisachildfromfamilyWang.n"); elseprintf("ThelastonearrivedtoendisachildfromfamilyLi.n"); } *运行结果 753 861 942 ThelastonearrivedtoendisachildfromfamilyWang. (获得最后一名的是王家的孩子。 58.拉丁方阵 构造NXN阶的拉丁方阵(2<=N<=9)，使方阵中的每一行和每一列中数字1到N只出现一次。 如N=4时： 1234 2341 3412 4123 *问题分析与算法设计 构造拉丁方阵的方法很多，这里给出最简单的一种方法。观察给出的例子，可以发现：若将每一 行中第一列的数字和最后一列的数字连起来构成一个环，则该环正好是由1到N顺序构成；对 于第i行，这个环的开始数字为i。按照此规律可以很容易的写出程序。下面给出构造6阶拉丁 方阵的程序。 *程序说明与注释 #include #defineN6/*确定N值*/ intmain() { inti,j,k,t; printf("ThepossbleLatinSquaresoforder%dare:n",N); for(j=0;j { for(i=0;i { t=(i+j)%N;/*确定该拉丁方阵第i行的第一个元素的值*/ for(k=0;k printf("%d",(k+t)%N+1); printf("n"); } printf("n"); } } *运行结果 ThepossbleLatinSquaresoforder6are: 1345612 2345623 3456234 4562345 5623456 6234561 4562345 5623456 6234561 1345612 2345623 3456234 59.填表格 将1、2、3、4、5和6填入下表中，要使得每一列右边的数字比左边的数字大，每一行下面 的数字比上面的数字大。按此要求，可有几种填写方法？ *问题分析与算法设计 按题目的要求进行分析，数字1一定是放在第一行第一列的格中，数字6一定是放在第二行第 三列的格中。在实现时可用一个一维数组表示，前三个元素表示第一行，后三个元素表示第二行。 先根据原题初始化数组，再根据题目中填写数字的要求进行试探。 *程序说明与注释 #include intjud1(ints[]); voidprint(intu[]); intcount;/*计数器*/ intmain() { staticinta[]={1,2,3,4,5,6};/*初始化数组*/ printf("Thepossbletablesatisfiedaboveconditionsare: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);/*如果满足题意，打印结果*/ } intjud1(ints[]) { inti,l; for(l=1;l<4;l++) for(i=l+1;i<5;++i) if(s[l]==s[i])return0;/*若数组中的数字有重复的，返回0*/ return1;/*若数组中的数字没有重复的，返回1*/ } voidprint(intu[]) { intk; printf("nNo.:%d",++count); for(k=0;k<6;k++) if(k%3==0)/*输出数组的前三个元素作为第一行*/ printf("n%d",u[k]); else/*输出数组的后三个元素作为第二行*/ printf("%d",u[k]); } *运行结果 Thepossbletablesatisfiedaboveconditionsare: No.1:No.2:No.3:No.4:No.5: 4135 456356346256246 60.1~9分成1：2：3的三个3位数 将1到9这九个数字分成三个3位数，分求第一个3位数，正好是第二个3位数的二倍，是第 三个3位数的三倍。问应当怎样分法。 *问题分析与算法设计 问题中的三个数之间是有数学关系的，实际上只要确定第一个三位数就可以解决问题。 试探第一个三位数之后，计算出另外两个数，将其分别分解成三位数字，进行判断后确定所试探 的数是否就是答案。 需要提醒的是：试探的初值可以是123，最大值是333。因为不可能超出该范围。 *程序与程序设计 #include intok(intt,int*z); inta[9]; intmain() { intm,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%dn",++count,m,2*m,3*m);/*输出结果*/ } intok(intt,int*z)/*分解t的值，将其存入z指向的三个数组元素，若满足要求返回1*/ { int*p1,*p2; for(p1=z;p1 { *p1=t%10;/*分解整数*/ t/=10; for(p2=a;p2 if(*p1==0||*p2==*p1)return0;/*若重复则返回*/ } return1;/*否则返回1*/ } *运行结果 No.1:192384576 No.2:219438657 No.3:273546819 No.4:327654981 *思考题 求出所有可能的以下形式的算式，每个算式中有九个数位，正好用尽1到9这九个数字。 1)○○○+○○○=○○○(共有168种可能的组合) 2)○×○○○○=○○○○(共有2种可能的组合) 3)○○×○○○=○○○○(共有7种可能的组合) 4)○×○○○=○○×○○○(共有13种可能的组合) 5)○×○○○=○×○○○○(共有28种可能的组合) 6)○○×○○=○×○○○○(共有7种可能的组合) 7)○○×○○=○○×○○○(共有11种可能的组合) C/C++语言经典、实用、趣味程序设计编程百例精解（7） 61.1~9组成三个3位的平方数 将1、2、3、4、5、6、7、8、9九个数字分成三组，每个数字只能用一次，即每组三个数不 允许有重复数字，也不许同其它组的三个数字重复，要求每组中的三位数都组成一个平方数。 *问题分析与算法设计 本问题的思路很多，这里介绍一种简单快速的算法。 首先求出三位数中不包含0且是某个整数平方的三位数，这样的三位数是不多的。然后将满足 条件的三位数进行组合，使得所选出的3个三位数的9个数字没有重复。 程序中可以将寻找足条件的三位数的过程和对该三位数进行数字分解的过程结合起来。 *程序说明与注释 #include intmain() { inta[20],num[20][3],b[10];/*a:存放满足条件的三位数*/ /*若不是10的倍数，则分解三位数*/ /*分解该三位数中的每一个数字*/ inti,j,k,m,n,t,flag; printf("The3squareswith3differentdigitseachare: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[i][0]; b[2]=num[i][1]; b[3]=num[i][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个数的三位数字*/ 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(b[m]==b[n])flag=1; if(!flag)/*若均不重复则打印结果*/ printf("%d,%d,%dn",a[i],a[t],a[k]); } } } } *运行结果 The3squareswith3differentdigitseachare: 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个。) 62.由8个整数形成奇特的立方体 任意给出8个整数，将这8个整数分别放在一个立方体的八个顶点上，要求每个面上的四个数 之和相等。 *问题分析与算法设计 简化问题：将8个顶点对应数组中的8个元素，将“每个面上的四个数之和皆相等”转换为数组 无素之间和的相等关系。这里的关键在于正确地将立方体的8个顶点与数组的8个元素对应。 可以利用简单的穷举方法建立8个数的全部排列。 *程序说明与注释 #include #include intmain() { inta[9],ii=0,i,a1,a2,a3,a4,b1,b2,b3,b4,flag; for(i=1;i<=8;i++)/*输入个数*/ { printf("Pleaseenter[%d]number:",i); scanf("%d",&a[i]); ii+=a[i]; } printf("******************************************n"); if(ii%2)/*和为奇数则输入的8个数不可用*/ { printf("Sorrytheycan'tbeconstructedrequiredcube!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++) 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;gotoout;/*满足条件则将flag置1后退出*/ } out: if(flag) { printf("Theycanbeconstructedrequiredcubeasfollow:n"); printf("/%2d…………/%2dn",a[a4],a[a3]); printf("%2d/…………%2d/|n",a[a1],a[a2]); printf("||||n"); printf("||||n"); printf("|%2d|||%2dn",a[b4],a[b3]); printf("/……………./n"); printf("%2d/………….%2d/n",a[b1],a[b2]); } elseprintf("Sorrytheycan'tbeconstructedrequiredcube!n"); } *运行结果 Pleaseenter[1]number:20 Pleaseenter[2]number:45 Pleaseenter[3]number:39 Pleaseenter[4]number:25 Pleaseenter[5]number:29 Pleaseenter[6]number:7 Pleaseenter[7]number:3 Pleaseenter[8]number:2 Sorrytheycan'tbeconstructedrequiredcube! *思考题 程序中建立全排列的方法效率太低，算法虽然简单但程序过于冗余。请读者自行设计新的算法完 成同样的工作。 63.减式还原 编写程序求解下式中各字母所代表的数字，不同的字母代表不同的数字。 PEAR -ARA ——– PEA *问题分析与算法设计 类似的问题从计算机算法的角度来说是比较简单的，可以采用最常见的穷举方法解决。程序中采 用循环穷举每个字母所可能代表的数字，然后将字母代表的数字转换为相应的整数，代入算式后 验证算式是否成立即可解决问题。 *程序说明与注释 #include intmain() { intp,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) { printf("PEAR%d%d%d%dn",p,e,a,r); printf("-ARA-%d%d%dn",a,r,a); printf("…………………….n"); printf("PEA%d%d%dn",p,e,a); } } *运行结果 PEAR1098 -ARA-989 ———-—— PEA109 *思考题 请复原下面的和式。不同的字母代表不同的数字。 SEVEN8252482526 THREE1972219722 +TWO答案：+106+104 ———-———–———– TWELVE1 64.乘式还原 A代表数字0到9中的前五个数字，Z代表后五个数字，请还原下列乘式。 AZA ×AAZ ———— AAAA AAZZ ZAA ———— ZAZAA *问题分析与算法设计 问题本身并不复杂，可以对乘式中的每一位使用穷举法，最终可以得到结果。本题的关键在于怎 样有效的判断每个部分积的每一位是否满足题意，这一问题处理不好，编写的程序会很长。程序 实现中采用了一个判断函数，通过传入函数的标志字符串对所有的数进行统一的判断处理。 *程序说明与注释 #include voidprint(longa,longb,longs1,longs2,longs3); intjud(longq,char*pflag); intmain() { longi,j,k,l,m,n,term,t1,t2,t3; intflag; 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) { 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); } } } } voidprint(longa,longb,longs1,longs2,longs3)/*打印结果*/ { printf("n%ldn",a); printf("*)%ldn",b); printf("………………….n"); printf("%ldn%ldn%ldn",s1,s2/10,s3/100); printf("………………….n"); printf("%ldn",a*b); } intjud(longq,char*pflag)/*判断一个数的每一位是否满足要求的判断函数*/ /*q:需要判断的数。pflag:标志字符串，A用1表示，Z用0表示。标志串排列顺序：个十百…*/ { while(q!=0&&*pflag!=NULL)/*循环判断对应位的取值范围是否正确*/ if(*pflag-'0'!=(q%10>=5?1:0))/*标志位与对应的位不符，返回0*/ return0; else { q/=10;++pflag;/*若相符则取下一位进行判断*/ } if(q==0&&*pflag==NULL)/*q的位数与标志字符串的长度相同时，返回1*/ return1; elsereturn0; } *运行结果 372 ×246 ———- 2232 1488 744 ———— 91512 *思考题 E代表数字0到9中的偶数数字，O代表奇数数字，请还原下列乘式。 EEO285 ×OO答案×39 ———–———– EOEO2565 EOO855 ———–———– OOOOO11115 65.乘式还原(2) 有乘法算式如下： ○○○ ×○○ ———— ○○○○ ○○○○ ———— ○○○○○ 18个○的位置上全部是素数(1、3、5或7)，请还原此算式。 *问题分析与算法设计 问题中虽然有18数位，但只要确定乘数和被乘数后经过计算就可确定其它的数位。 乘数和被乘数共有5个数位，要求每个数都是质数。完全可以采用穷举的方法对乘数和被乘数 进行穷举，经过判断后找出答案。但是这种方法给人的感觉是“太笨了”，因为组成的数字只是质 数(4个)，完全没有必要在那么大的范围内进行穷举，只需要试探每一位数字为质数时的情况即 可。 采用五重循环的方法实现对于5个数字的穷举，前面的许多例题中都已见过。循环实现简单易 行，但嵌套的层次太多，需要穷举的变量的数量直接影响到循环嵌套的层数，这种简单的实现方 法缺少技巧性。本例的程序中给出了另外一种同样功能的算法，该算法的实现思想请阅读程序。 程序中并没有直接对质数进行穷举，而是将每个质数与1到4顺序一一对应，在穷举时为处理 简单仅对1到4进行穷举处理，待要判断产生的乘积是否满足条件时再利用一个数组完成向对 应质数的转换。请体会程序中的处理方法。程序中使用的算法实际上是回朔法。 *程序说明与注释 #include #defineNUM5/*需要穷举的变量数目*/ #defineC_NUM4/*每个变量的值的变化范围*/ inta[NUM+1];/*为需要穷举的变量开辟的数组*/ /*a[1]:被乘数的百位，a[2]：十位,aa[3]:个位a[4]:被乘数的十位a[5]:个位*/ intb[]={0,2,3,5,7};/*存放质数数字的数组，不使用第0号元素*/ intf(longsum); intmain() { inti,not_finish=1; i=2;/*i:将要进行处理的元素的指针下标。设置初始值*/ a[1]=1;/*为第1号元素设置初始值*/ while(not_finish)/*not_finish:程序运行没结束标记*/ { while(not_finish&&i<=NUM) /*处理包括第i个元素在内的后续元素，找出当前条件下的一种各个变量的一种可能的取值方法 */ if(a[i]>=C_NUM)/*当要处理的元素取超过规定的C_NUM时*/ if(i==1&&a[1]==C_NUM) not_finish=0;/*若1号元素已经到C_NUM，则处理全部结束*/ elsea[i–]=0;/*将要处理的元素置0，下标-1(回退一个元素)*/ elsea[i++]++;/*当前元素值加1后下标指针加1*/ if(not_finish) { longintsum1,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=2222&&sum3<=7777&&f(s um3)) /*判断两部分积是否满足题目条件*/ if((sum4=sum2+sum3*10)>=22222&&sum4<=77777&&f(sum4)) /*判断乘式的积是否满足题目条件*/ { printf("%dn",sum1);/*若满足题意，则打印结果*/ printf("*%d%dn",b[a[4>,b[a[5>); printf("……………………n"); printf("%dn",sum2); printf("%dn",sum3); printf("……………………n"); printf("%dn",sum4); } i=NUM;/*为穷举下一个可能取值作准备*/ } } } intf(longsum)/*判断sum的每一位数字是否是质数，若不是返回0，若是返回1*/ { inti,k,flag;/*flag=1:数字是质数的标记*/ while(sum>0) { i=sum%10;/*取个位的数字*/ for(flag=0,k=1;!flag&&k<=C_NUM;k++) if(b[k]==i) { flag=1;break; } if(!flag)return0; elsesum=sum/10; } return1; } *运行结果 775 ×33 ———- 2325 2325 ———– 25575 *思考题 以下乘式中，A、B、C代表一确定的数字，○代表任意数字，请复原。 ABC286 ×BAC×826 ————-答案：———— ○○○○1716 ○○A572 ○○○B2288 ————-—————- ○○○○○○236236 66.除式还原(1) 给定下列除式，其中包含5个7，其它打×的是任意数字，请加以还原。 ×7×————–商 ————– 除数——××|×××××————-被除数 ×77 ————– ×7× ×7× ———- ×× ×× ———- ○ *问题分析与算法设计 首先分析题目，由除式本身尽可能多地推出已知条件。由除式本身书已知： 1、被除数的范围是10000到99999，除数的范围是10到99，且可以整除； 2、商为100到999之间，且十位数字为7； 3、商的第一位与除数的积为三位数，且后两位为77； 4、被除数的第三位一定为4； 5、7乘以除数的积为一个三位数，且第二位为7； 6、商的最后一位不能为0，且与除数的积为一个二位数。 由已知条件就可以采用穷举的方法找出结果。 *程序说明与注释 #include intmain() { longinti; intj,l; for(i=10000;i<=99999;i++)/*1.i:被除数*/ if(i%1000-i%100==400)/*4.被除数的第三位一定为4*/ for(j=10;j<=99;j++)/*1.j:余数*/ if(i%j==0&&(l=i/j)%100>=70&&l%100100&&l<=999) /*1.可以整除&&2.商l在100到999之间且十位数字为7&&6.商的个数不能为0*/ if((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=%dn",i,j,l); } *运行结果 51463/53=971。 可以看作为下列算式： 971 ————- 53|51463 477 ————- 376 371 ———– 53 53 ———– ○ *问题的进一步讨论 在推出的已知条件中，几所有的条件都是十分明显的，换句话说，推出的已知条件就是对题目的 平铺直叙。这种推已知条件的方法十分简单，并且行之有效。 *思考题 下列除式中仅给定了一个8，其它打×的位置上是任意数字，请还原。 ×8×—————-商 —————- 除数——-×××|××××××—————被除数 ×××× ————— ××× ××× ————— ×××× ×××× ————— ○ 67.除式还原(2) 下列除式中仅在商中给定了一个7，其它打×的位置全部是任意数字，请还原。 ×7×××————-商 —————— 除数——————-×××|××××××××————-被除数 ××××————-1) ————— ×××————-2) ×××————-3) ————— ××××————-4) ×××————-5) —————– ××××————-6) ××××————-7) —————– 0 *问题分析与算法设计 这道题是不可能用单纯的穷举法求解的，一则计算时间太长，二则难于求出除式中各部分的值。 对除式进行分析，改可能多地推出限制条件： 由3)可以看出，商的第二位7乘除数得一个三位数，所以除数<=142。 由除数乘商的第一位为一个四位数可知，商的第一位只能为8或9且除数>=112。同时商的第 五位也为8或9数的前四位一定=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]<=13770<=a[1]<=9 0<=a[2]<=90<=a[3]<=99 除数：112<=b<=142 商：8<=c[0]<=97<=c[1]<=88<=c[2]<=9 2)的前两位：10<=d[0]<=99 4)的前三位：100<=d[1] 6)的前两位：10<=d[2]<=99 1)式部分积：b*c[0]>1000 5)式部分积：100 *程序说明与注释 #include intmain() { inta[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] for(a[2]=0;a[2]<=9;a[2]++) for(c[1]=7;c[1]<=8;c[1]++) if(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%dn",c[0],7,c[1],0,c[2]); } } *运行结果： No1:12128316/124=97809 *思考题 下列除式中“×”所在的位置全部是任意数字，请还原。 ××××× ——————- ×××|×××××××× ×××× —————— ×××× ××× ————— ××× ××× ———– ×××× ×××× ———– 0 68.九位累进可除数 求九位累进可除数。所谓九位累进可除数就是这样一个数：这个数用到1到9这九个数字组成， 每个数字刚好只出现一次。这九个位数的前两位能被2整除，前三位能被3整除……前N位能 被N整除，整个九位数能被9整除。 *问题分析与算法设计 问题本身可以简化为一个穷举问题：只要穷举每位数字的各种可能取值，按照题目的要求对穷举 的结果进行判断就一定可以得到正确的结果。 问题中给出了“累进可除”这一条件，就使得我们可以在穷举法中加入条件判断。在穷举的过程中， 当确定部分位的值后，马上就判断产生的该部分是否符合“累进可除”条件，若符合，则继续穷举 下一位数字；否则刚刚产生的那一位数字就是错误的。这样将条件判断引入到穷举法之中，可以 尽可能早的发现矛盾，尽早地放弃不必要穷举的值，从而提高程序的执行效率。 为了达到早期发现矛盾的目的，不能采用多重循环的方法实行穷举，那样编出的程序质量较差。 程序中使用的算法不再是穷举法，而是回朔法。 *程序说明与注释 #include #defineNUM9 inta[NUM+1]; intmain() { inti,k,flag,not_finish=1; longsum; 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 if(a[k]==a[i])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[i]==a[i-1])/*若a[i]的值已经经过一圈追上a[i-1]*/ { i–;/*i值减1，退回处理前一个元素*/ if(i>1&&a[i]==NUM) a[i]=1;/*当第i位的值达到NUM时，第i位的值取1*/ elseif(i==1&&a[i]==NUM)/*当第1位的值达到NUM时结束*/ not_finish=0;/*置程序结束标记*/ elsea[i]++;/*第i位的值取下一个,加1*/ } elseif(a[i]==NUM)a[i]=1; elsea[i]++; } else/*第i位已经满足要求，处理第i+1位*/ if(++i<=NUM)/*i+1处理下一元素，当i没有处理完毕时*/ if(a[i-1]==NUM)a[i]=1;/*若i-1的值已为NUM，则a[i]的值为1*/ elsea[i]=a[i-1]+1;/*否则，a[i]的初值为a[i-1]值的"下一个"值*/ } if(not_finish) { printf("nTheprogressiredivisiablenumberis:"); for(k=1;k<=NUM;k++)/*输出计算结果*/ printf("%d",a[k]); if(a[NUM-1] elsea[NUM-1]=1; not_finish=0; printf("n"); } } } *运行结果 Theprogressiredivisiblenumberis:381654729 *思考题 求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 inta[14]; intmain() { inti,n,j=1;/*j:数组(盒子)下标，初始时为1号元素*/ printf("Theoriginalorderofcardsis:"); 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);/*控制空盒计数为i*/ } for(i=1;i<=13;i++)/*输出牌的排列顺序*/ printf("%d",a[i]); printf("n"); } *运行结果 Theoriginalorderofcardsis:18251 70.魔术师的猜牌术(2) 魔术师再次表演，他将红桃和黑桃全部迭在一起，牌面朝下放在手中，对观众说：最上面一张是 黑桃A，翻开后放在桌上。以后，从上至下每数两张全依次放在最底下，第三张给观众看，便是 黑桃2，放在桌上后再数两张依次放在最底下，第三张给观众看，是黑桃3。如此下去，观众看 到放在桌子上牌的顺序是： 黑桃A2345678910JQK 红桃A2345678910JQK 问魔术师手中牌的原始顺序是什么？ *问题分析与算法设计 本题可在上题的基础上进行编程，不同的在于计数的方法和牌的张数，这些并不影响我们求解题 目的思路，仍可按照倒推的方法，得到原来魔术师手中的牌的顺序。 *程序说明与注释 #include inta[27]; intmain() { inti,n,j=1; a[1]=1;/*初始化第一张牌*/ printf("Theoriginalorderofcardsis:(r:radb: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);/*控制空盒计数为3*/ } for(i=1;i<=26;i++)/*输出牌的排列顺序*/ { printf("%c",a[i]>13?'r':'b'); printf("%d",a[i]>13?a[i]-13:a[i]); if(i==13)printf("n"); } printf("n"); } *运行结果 Theoriginalorderofcardsis:(r:radb:black): b1r6b10b2r12r3b3b11r9b4r7b12b5 r4r13b6b13r11b7r5r1b8r8r10b9r2 C/C++语言经典、实用、趣味程序设计编程百例精解（8） 71.约瑟夫问题 这是17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15个 非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法： 30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进 行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。 *问题分析与算法设计 约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实现方法。 题目中30个人围成一圈，因而启发我们用一个循环的链来表示。可以使用结构数组来构成一个 循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否 被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9 时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为 止。 *程序说明与注释 #include structnode { intnextp;/*指向下一个人的指针(下一个人的数组下标)*/ intno_out;/*是否被扔下海的标记。1：没有被扔下海。0：已被扔下海*/ }link[31];/*30个人，0号元素没有使用*/ intmain() { inti,j,k; printf("Theoriginalcircleis(+:pagendom,@:christian):n"); for(i=1;i<=30;i++)/*初始化结构数组*/ { link[i].nextp=i+1;/*指针指向下一个人(数组元素下标)*/ link[i].no_out=1;/*标志置为1，表示人都在船上*/ } link[30].nextp=1;/*第30个人的指针指向第一个人以构成环*/ j=30;/*j:指向已经处理完毕的数组元素，从link[i]指向的人开始计数*/ for(i=0;i<15;i++)/*i:已扔下海的人数计数器*/ { for(k=0;;)/*k:决定哪个人被扔下海的计数器*/ if(k<15) { j=link[j].nextp;/*修改指针，取下一个人*/ k+=link[j].no_out;/*进行计数。因已扔下海的人计标记为0*/ } elsebreak;/*计数到15则停止计数*/ link[j].no_out=0;/*将标记置0，表示该人已被扔下海*/ } for(i=1;i<=30;i++)/*输出结果*/ printf("%c",link[i].no_out?'@':'+');/*+:被扔下海，@：在船上*/ printf("n"); } *运行结果 Theoriginalcircleis(+: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 inta[27]; intmain() { inti,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("%dkinds:",n);/*输出结果*/ for(k=0;a[k];k++) printf("%d",a[k]); printf("n"); } *运行结果 19kinds:5412172227 73.和数能表示1~23的5个正整数 已知五个互不相同的正整数之和为23，且从这五个数中挑选若干个加起来可以表示从1到23 之内的全部自然数。问这五个数是什么？ *问题分析与算法设计 从计算机程序设计的角度来说，可以用穷举法分解23，然后判断所分解的五个数是否可以表示 1到23之间的全部整数。 *程序说明与注释 #include intmain() { inta,b,c,d,e,i,j,k,l,m,x,count=0,f=0;/*f:分解的5个数可以表示出1~23的标记*/ printf("Therearefollowingpossbleresult: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++)/*判断5个数可否表示1~23*/ for(f=1,i=0;i<2&&f;i++)/*穷举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%dn",++count,a,b,c,d,e); } } *运行结果 Therearefollowingpossbleresult: [1]:123512 [2]:123611 [3]:123710 [4]:124511 [5]:124610 [6]:12479 74.可称1~40磅的4块砝码 法国数学家梅齐亚克在他著名的《数字组合游戏》(1962)中提出了一个问题：一位商人有一个 重40磅的砝码，一天不小心将砝码摔成了四块。后来商人称得每块的重量都是整磅数，而且发 现这四块碎片可以在天平上称1至40磅之间的任意重量。请问这四块碎片各重多少？ *问题分析与算法设计 本题是上一题的发展。题目中给出的条件是“在天平上”，这意味着：同一砝码既可以放在天平的 左侧，也可以放在天平的右侧。若规定重物只能放在天平的左侧，则当天平平衡时有： 重物重量+左侧砝码重量总和=右侧砝码重量总和 由此可得： 重物重量=右侧砝码重量总和-左侧砝码重量总和 编程时只要根据以上公式，使“右侧砝码重量总和-左侧砝码重量总和”可以表示1到40之间的 全部重量即可。编程中要注意的是：怎样采用一种简单的方法来表示一个砝码是在天平的左侧还 是在天平的右侧，或是根本没有使用。 以下程序采用1、-1和0分别表示上述三种情况，请注意理解。 *程序说明与注释 #include #include intmain() { intweight1,weight2,weight3,weight4,d1,d2,d3,d4,x,flag;/*flag:满足题意的标记*/ printf("Theweightisbrokeupasfollowing4pieces:"); 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%dn",weight1,weight2,weight3,weight4); flag=0; } } *运行结果 Theweightisbrokeupasfollowing4pieces:13927 75.10个小孩分糖果 十个小孩围成一圈分糖果，老师分给第一个小孩10块，第二个小孩2块，第三个小孩8块， 第四个小孩22块，第五个小孩16块，第六个小孩4块，第七个小孩10块，第八个小孩6块， 第九个小孩14块，第十个小孩20块。然后所有的小孩同时将手中的糖分一半给右边的小孩； 糖块数为奇数的人可向老师要一块。问经过这样几次后大家手中的糖的块数一样多？每人各有多 少块糖？ *问题分析与算法设计 题目描述的分糖过程是一个机械的重复过程，编程算法完全可以按照描述的过程进行模拟。 *程序说明与注释 #include voidprint(ints[]); intjudge(intc[]); intj=0; intmain() { staticintsweet[10]={10,2,8,22,16,4,10,6,14,20};/*初始化数组数据*/ inti,t[10],l; printf("childn"); printf("roundn"); printf("………………………..n"); print(sweet);/*输出每个人手中糖的块数*/ while(judge(sweet))/*若不满足要求则继续进行循环*/ { for(i=0;i<10;i++)/*将每个人手中的糖分成一半*/ if(sweet[i]%2==0)/*若为偶数则直接分出一半*/ t[i]=sweet[i]=sweet[i]/2; else/*若为奇数则加1后再分出一半*/ t[i]=sweet[i]=(sweet[i]+1)/2; for(l=0;l<9;l++)/*将分出的一半糖给右(后)边的孩子*/ sweet[l+1]=sweet[l+1]+t[l]; sweet[0]+=t[9]; print(sweet);/*输出当前每个孩子中手中的糖数*/ } } intjudge(intc[]) { inti; for(i=0;i<10;i++)/*判断每个孩子手中的糖是否相同*/ if(c[0]!=c[i])return1;/*不相同返回1*/ return0; } voidprint(ints[])/*输出数组中每个元素的值*/ { intk; printf("%2d",j++); for(k=0;k<10;k++)printf("%4d",s[k]); printf("n"); } 76.小明买书 小明假期同爸爸一起去书店，他选中了六本书，每本书的单价分别为：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 #include intmain() { intd[6],m,i,j; longb[63],flag; floatc[6],min,x; printf("Pleaseenterthepricesof6books:"); for(i=0;i<6;i++)scanf("%f",&c[i]);/*输入六个浮点数*/ 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的最小差值*/ 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;/*对第一次计算出的差min进行处理*/ b[i++]=flag;/*b[]:有相同的min的flag的数组i:b[]数组的下标*/ } elseif(min-x>1.e-6)/*对新的min的处理*/ { min=x;b[0]=flag;i=1; } elseif(fabs((double)x-min)<1.e-6) b[i++]=flag;/*对相等min的处理*/ } for(m=0;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]); elseprintf("%.2fn",c[j]); } } *运行结果 Pleaseenterthepricesof6books:3.11.72.05.30.97.2 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 *思考题 可以看出，程序中求六个数所能产生全部组合的算法并不好，使用六重循环进行处理使程序显得 不够简洁。可以设计出更通用、优化的算法产生全部组合。 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 xy 倒酒的规则如下： 1)按a->b->c->a的顺序； 2)b倒空后才能从a中取 3)c装满后才能向a中倒 按以上规则可以编写出程序如下： *程序说明与注释 #include voidgetti(inta,inty,intz); inti;/*最后需要分出的重量*/ intmain() { inta,y,z; printf("inputFulla,Emptyb,c,Geti:");/*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的步骤*/ } voidgetti(inta,inty,intz)/*a:满瓶的容量y:第一个空瓶的容量z:第二个空瓶的容量*/ { intb=0,c=0;/*b:第一瓶实际的重量c:第二瓶实际的重量*/ printf("a%db%dc%dn%4d%4d%4dn",a,y,z,a,b,c); while(a!=i||b!=i&&c!=i)/*当满瓶!=i或另两瓶都!=i*/ { if(!b) {a-=y;b=y;}/*如果第一瓶为空，则将满瓶倒入第一瓶中*/ elseif(c==z) {a+=z;c=0;}/*如果第二瓶满，则将第二瓶倒入满瓶中*/ elseif(b>z-c)/*如果第一瓶的重量>第二瓶的剩余空间*/ {b-=(z-c);c=z;}/*则将装满第二瓶，第一瓶中保留剩余部分*/ else{c+=b;b=0;}/*否则，将第一瓶全部倒入第二瓶中*/ printf("%4d%4d%4dn",a,b,c); } } *思考题 上面的程序中仅给出了两种分酒的方法，并没有找出全部的方法。请设计新的算法，找出全部的 分酒方法，并找出一种倒酒次数最少的方法。 78.求π的近似值 请利用“正多边形逼近”的方法求出π的近似值 *问题分析与算法设计 利用“正多边形逼近”的方法求出π值在很早以前就存在，我们的先人祖冲之就是用这种方法在 世界上第一个得到精确度达小数点后第6位的π值的。 利用圆内接正六边形边长等于半径的特点将边数翻番，作出正十二边形，求出边长，重复这一过 程，就可获得所需精度的π的近似值。 假设单位圆内接多边形的边长为2b，边数为i，则边数加倍后新的正多边形的边长为： x=√────── 2-2*√─── 1-b*b ────── 2 周长为： y=2*i*xi:为加倍前的正多边形的边数 *程序说明与注释 #include #include intmain() { doublee=0.1,b=0.5,c,d; longinti;/*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则停止计算*/ e=b;/*保存本次正多边形的边长作为下一次精度控制的依据*/ } printf("pai=%.15lfn",2*i*b);/*输出π值和正多边形的边数*/ printf("Thenumberofedgesofrequiredpolygon:%ldn",i); } *运行结果 pai=3.9794 Thenumberofedgesofrequiredpolygon:100663296 *思考题 请用外切正多边形逼近的方法求π的近似值。 79.求π的近似值(2) 利用随机数法求π的近似值 *问题分析与算法设计 随机数法求π的近似值的思路：在一个单位边长的正方形中，以边长为半径，以一个顶点为圆 心，在政权方形上作四分之一圆。随机的向正方形内扔点，若落入四分之一圆内则计数。重复向 正方形内扔足够多的点，将落入四分之一圆内的计数除以总的点数，其值就是π值四分之一的 近似值。 按此方法可直接进行编程，注意：本方法求出的π值只有统计次数足够多时才可能准确。 *程序说明与注释 #include #include #include #defineN30000 intmain() { floatx,y; intc=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=%fn",4.*d/N);/*输出求出的π值*/ } *运行结果 多次运行程序，可能得到多个不同的对口果，这是因为采用的是统计规律求出的近似值，只有当 统计的次数足够大时，才可能逼近π值。运行四次，可能的结果是： 3.122267 3.139733 3.133733 80.奇数平方的一个有趣性质 编程验证“大于1000的奇数其平方与1的差是8的倍数”。 *问题分析与算法设计 本题是一个很容易证明的数学定理，我们可以编写程序验证它。 题目中给出的处理过程很清楚，算法不需要特殊设计。可以按照题目的叙述直接进行验证(程序 中仅验证到3000)。 *程序说明与注释 #include intmain() { longinta; 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("+%ldn",(a*a-1)%8);/*输出被8除后的余数*/ } } C/C++语言经典、实用、趣味程序设计编程百例精解（9） 81.角谷猜想 日本一位中学生发现一个奇妙的“定理”，请角谷教授证明，而教授无能为力，于是产生角谷猜想。 猜想的内容是：任给一个自然数，若为偶数除以2，若为奇数则乘3加1，得到一个新的自然数 后按照上面的法则继续演算，若干次后得到的结果必然为1。请编程验证。 *问题分析与算法设计 本题是一个沿未获得一般证明的猜想，但屡试不爽，可以用程序验证。 题目中给出的处理过程很清楚，算法不需特殊设计，可按照题目的叙述直接进行证。 *程序说明与注释 #include intmain() { intn,count=0; printf("Pleaseenternumber:"); scanf("%d",&n);/*输入任一整数*/ do{ if(n%2) { n=n*3+1;/*若为奇数，n乘3加1*/ printf("[%d]:%d*3+1=%dn",++count,(n-1)/3,n); } else { n/=2;/*若为偶数n除以2*/ printf("[%d]:%d/2=%dn",++count,2*n,n); } }while(n!=1);/*n不等于1则继续以上过程*/ } 82.四方定理 数论中著名的“四方定理”讲的是：所有自然数至多只要用四个数的平方和就可以表示。 请编程证此定理。 *问题分析与算法设计 本题是一个定理，我们不去证明它而是编程序验证。 对四个变量采用试探的方法进行计算，满足要求时输出计算结果。 *程序说明与注释 #include #include intmain() { intnumber,i,j,k,l; printf("Pleaseenteranumber="); scanf("%d",&number);/*输入整数*/ for(i=1;i for(j=0;j<=i;j++) 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*%dn",number,i,i,j,j,k,k,l,l); exit(0); } } *运行结果 1)Pleaseenteranumber=110 110=7*7+6*6+4*4+3*3 2)Pleaseenteranumber=211 211=8*8+7*7+7*7+7*7 3)Pleaseenteranumber=99 99=7*7+5*5+4*4+3*3 83.卡布列克常数 验证卡布列克运算。任意一个四位数，只要它们各个位上的数字是不全相同的，就有这样的规律： 1)将组成该四位数的四个数字由大到小排列，形成由这四个数字构成的最大的四位数； 2)将组成该四位数的四个数字由小到大排列，形成由这四个数字构成的最小的四位数(如果四个 数中含有0，则得到的数不足四位)； 3)求两个数的差，得到一个新的四位数(高位零保留)。 重复以上过程，最后得到的结果是6174，这个数被称为卡布列克数。 *问题分析与算法设计 题目中给出的处理过程很清楚，算法不需要特殊设计，可按照题目的叙述直接进行验证。 *程序说明与注释 #include voidvr6174(int); voidparse_sort(intnum,int*each); voidmax_min(int*each,int*max,int*min); voidparse_sort(intnum,int*each); intcount=0; intmain() { intn; printf("Enteranumber:"); scanf("%d",&n);/*输入任意正整数*/ vr6174(n);/*调用函数进行验证*/ } voidvr6174(intnum) { inteach[4],max,min; if(num!=6174&&num)/*若不等于74且不等于0则进行卡布列克运算*/ { parse_sort(num,each);/*将整数分解，数字存入each数组中*/ max_min(each,&max,&min);/*求数字组成的最大值和最小值*/ num=max-min;/*求最大值和最小值的差*/ printf("[%d]:%d-%d=%dn",++count,max,min,num);/*输出该步计算过程*/ vr6174(num);/*递归调用自身继续进行卡布列克运算*/ } } voidparse_sort(intnum,int*each) { inti,*j,*k,temp; for(i=0;i<=4;i++)/*将NUM分解为数字*/ { j=each+3-i; *j=num%10; num/=10; } for(i=0;i<3;i++)/*对各保数字从小到大进行排序*/ for(j=each,k=each+1;j if(*j>*k){temp=*j;*j=*k;*k=temp;} return; } voidmax_min(int*each,int*max,int*min)/*将分解的数字还原为最大整数和最小整数 */ { int*i; *min=0; for(i=each;i *min=*min*10+*i; *max=0; for(i=each+3;i>=each;i–)/*还原为最大的整数*/ *max=*max*10+*i; return; } *运行结果 1)Enteranumber:4312 [1]:4312-1234=3078 [2]:8730-378=8352 [3]:8532-2358=6174 2)Enteranumber: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)Enteranumber:9643 [1]:9643-3469=6174 84.尼科彻斯定理 验证尼科彻斯定理，即：任何一个整数的立方都可以写成一串连续奇数的和。×× *问题分析与算法设计 本题是一个定理，我们先来证明它是成立的。 对于任一正整数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。编程的算法不 需要特殊设计，可按照定理的证明过直接进行验证。 *程序说明与注释 #include intmain() { inta,b,c,d; printf("Pleaseenteranumber:"); scanf("%d",&a);/*输入整数*/ b=a*a*a;/*求整数的三次方*/ printf("%d*%d*%d=%d=",a,a,a,b); for(d=0,c=0;c { d+=a*a-a+1+c*2;/*求数列的前a项的和*/ printf(c?"+%d":"%d",a*a-a+1+c*2); } if(d==b)printf("Yn");/*若条件满足则输出“Y”*/ elseprintf("Nn");/*否则输出“N”*/ } *运行结果 1)Pleaseenteranumber:13 13*13*13=2197=157+159+161+163+165+167+169+171+173+175+177+179 +181Y 2)Pleaseenteranumber:14 14*14*14=2744=183+185+187+189+191+193+195+197+199+201+203+205 +207+209Y *思考题 本题的求解方法是先证明，在证明的过程中找到编程的算法，然后实现编程。实际上我们也可以 不进行证明，直接使用编程中常用的试探方法来找出该数列，验证该定理。请读者自行设计算法。 当然这样得到的数列可能与用定理方法得到的数列不一样。 85.回文数的形成 任取一个十进制整数，将其倒过来后与原来的整数相加，得到一个新的整数后重复以上步聚，则 最终可得到一个回文数。请编程验证。 *问题分析与算法设计 回文数的这一形成规则目前还属于一个猜想，尚未得到数学上的证明。有些回文数要经历上百个 步聚才能获得。这里通过编程验证。 题目中给出的处理过程很清楚，算法不需要特殊设计。可按照题目的叙述直接进行验证。 *程序说明与注释 #include #defineMAX2147483647 longre(longint); intnonres(longints); intmain() { longintn,m; intcount=0; printf("Pleaseenetranumberoptionaly:"); scanf("%ld",&n); printf("Thegenerationprocessofpalindrome:n"); while(!nonres((m=re(n))+n))/*判断整数与其反序数相加后是否为回文数*/ { if(m+n>=MAX) { printf("inputerror,break.n"); break; } else { printf("[%d]:%ld+%ld=%ldn",++count,n,m,m+n); n+=m; } } printf("[%d]:%ld+%ld=%ldn",++count,n,m,m+n);/*输出最后得到的回文数*/ printf("Herewereachedtheaimatlast!n"); } longre(longinta)/*求输入整数的反序数*/ { longintt; for(t=0;a>0;a/=10)/*将整数反序*/ t=t*10+a%10; returnt; } intnonres(longints)/*判断给定的整数是否是回文数*/ { if(re(s)==s)return1;/*若是回文数则返回１*/ elsereturn0;/*否则返回０*/ } 86.自动发牌 一副扑克有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 #include intcomp(constvoid*j,constvoid*i); voidp(intb[],charn[]); intmain(void) { staticcharn[]={'2','3','4','5','6','7','8','9','T','J','Q','K','A'}; inta[53],b1[13],b2[13],b3[13],b4[13]; intb11=0,b22=0,b33=0,b44=0,t=1,m,flag,i; while(t<=52)/*控制发52张牌*/ { m=rand()%52;/*产生0到51之间的随机数*/ for(flag=1,i=1;i<=t&&flag;i++)/*查找新产生的随机数是否已经存在*/ if(m==a[i])flag=0;/*flag=1:产生的是新的随机数flag=0:新产生的随机数已经存在*/ if(flag) { a[t++]=m;/*如果产生了新的随机数，则存入数组*/ if(t%4==0)b1[b11++]=a[t-1];/*根据t的模值，判断当前*/ elseif(t%4==1)b2[b22++]=a[t-1];/*的牌应存入哪个数组中*/ elseif(t%4==2)b3[b33++]=a[t-1]; elseif(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); qsort(b4,13,sizeof(int),comp); p(b1,n);p(b2,n);p(b3,n);p(b4,n);/*分别打印每个人的牌*/ return0; } voidp(intb[],charn[]) { inti; printf("n006");/*打印黑桃标记*/ for(i=0;i<13;i++)/*将数组中的值转换为相应的花色*/ if(b[i]/13==0)printf("%c",n[b[i]%13]);/*该花色对应的牌*/ printf("n003");/*打印红桃标记*/ for(i=0;i<13;i++) if((b[i]/13)==1)printf("%c",n[b[i]%13]); printf("n004");/*打印方块标记*/ for(i=0;i<13;i++) if(b[i]/13==2)printf("%c",n[b[i]%13]); printf("n005");/*打印梅花标记*/ for(i=0;i<13;i++) if(b[i]/13==3||b[i]/13==4)printf("%c",n[b[i]%13]); printf("n"); } intcomp(constvoid*j,constvoid*i)/*qsort调用的排序函数*/ { return(*(int*)i-*(int*)j); } 87.黑白子交换 有三个白子和三个黑子如下图布置： ○○○.●●● 游戏的目的是用最少的步数将上图中白子和黑子的位置进行交换： ●●●.○○○ 游戏的规则是：(1)一次只能移动一个棋子；(2)棋子可以向空格中移动，也可以跳过一个对方 的棋子进入空格，但不能向后跳，也不能跳过两个子。请用计算机实现上述游戏。 *问题分析与算法设计 计算机解决胜这类问题的关键是要找出问题的规律，或者说是要制定一套计算机行动的规则。分 析本题，先用人来解决问题，可总结出以下规则： (1)黑子向左跳过白子落入空格，转(5) (2)白子向右跳过黑子落入空格，转(5) (3)黑子向左移动一格落入空格(但不应产生棋子阻塞现象)，转(5) (4)白子向右移动一格落入空格(但不应产生棋子阻塞现萌)，转(5) (5)判断游戏是否结束，若没有结束，则转(1)继续。 所谓的“阻塞”现象就是：在移动棋子的过程中，两个尚未到位的同色棋子连接在一起，使棋盘中 的其它棋子无法继续移动。例如按下列方法移动棋子： 0 ○○○.●●● 1○○.○●●● 2△○○●○.●● 3 ○○●.○●● 4两个●连在一起产生阻塞 ○○●●○.● 或4两个白连在一起产生阻塞 ○.●○○●● 产生阻塞的现象的原因是在第2步(△状态)时，棋子○不能向右移动，只能将●向左移动。 总结产生阻塞的原因，当棋盘出现“黑、白、空、黑”或“白、空、黑、白”状态时，不能向左或向 右移动中间的棋子，只移动两边的棋子。 按照上述规则，可以保证在移动棋子的过程中，不会出现棋子无法移动的现象，且可以用最少的 步数完成白子和黑子的位置交换。 *程序说明与注释 #include intnumber; voidprint(inta[]); voidchange(int*n,int*m); intmain() { intt[7]={1,1,1,0,2,2,2};/*初始化数组1：白子2：黑子0：空格*/ inti,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[i]==1&&t[i+1]==2&&t[i+2]==0) {change(&t[i],&t[i+2]);print(t);flag=0;} for(i=0;flag&&i<5;i++)/*若黑子可以向左跳过白子，则黑子向左跳*/ if(t[i]==0&&t[i+1]==1&&t[i+2]==2) {change(&t[i],&t[i+2]);print(t);flag=0;} for(i=0;flag&&i<6;i++)/*若向右移动白子不会产生阻塞,则白子向右移动*/ if(t[i]==1&&t[i+1]==0&&(i==0||t[i-1]!=t[i+2])) {change(&t[i],&t[i+1]);print(t);flag=0;} for(i=0;flag&&i<6;i++)/*若向左移动黑子不会产生阻塞，则黑子向左移动*/ if(t[i]==0&&t[i+1]==2&&(i==5||t[i-1]!=t[i+2])) {change(&t[i],&t[i+1]);print(t);flag=0;} } } voidprint(inta[]) { inti; printf("No.%2d:………………………..n",number++); printf(""); for(i=0;i<=6;i++) printf("|%c",a[i]==1?'*':(a[i]==2?'@':'')); printf("|n………………………..nn"); } voidchange(int*n,int*m) { intterm; term=*n;*n=*m;*m=term; } *问题的进一步讨论 本题中的规则不仅适用于三个棋子的情况，而且可以推而广之，适用于任意N个棋子的情况。 读者可以编程验证，按照本规则得到的棋子移动步数是最少的。 事实上，制定规则是解决这类问题的关键。一个游戏程序“思考水平的高低，完全取决于使用规 则的好坏。” *思考题 有两个白子和两个黑子如下左图布置： ○.○ ... ●.● 棋盘中的棋子按”马步“规则行走，要求用最少的步数将图中白子和黑子的位置进行交换，最终结 果如下一幅图所示。 ●.● ... ○.○ 88.常胜将军 现有21根火柴，两人轮流取，每人每次可以取走1至4根，不可多取，也不能不取，谁取最 后一楰火柴谁输。请编写一个程序进行人机对弈，要求人先取，计算机后取；计算机一方为“常 胜将军”。 *问题分析与算法设计 在计算机后走的情况下，要想使计算机成为“常胜将军”，必须找出取关键。根据本题的要求枷 以总结出，后走一方取子的数量与对方刚才一步取子的数量之和等于，就可以保证最后一个子是 留给先取子的那个人的。 据此分析进行算法设计就是很简单的工作，编程实现也十分容易。 *程序说明与注释 #include intmain() { inta=21,i; printf("Gamebegin:n"); while(a>0) { do{ printf("Howmanystickdoyouwishtotake(1~%d)?",a>4?4:a); scanf("%d",&i); }while(i>4||ia);/*接收正在确的输入*/ if(a-i>0)printf("%dstickleftinthepile.n",a-i); if((a-i)<=0) {