C-C++

C/c++趣味程序百例(献给C/C++初学者)(三)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*程序说明与注释#includestdio.hintmain(){intx,y,z,count=0;printf(MenWomenChildren\n);printf(........................................\n);for(x=0;x=10;x++){y=20-2*x;/*x定值据(3)式求y*/z=30-x-y;/*由(1)式求z*/if(3*x+2*y+z==50)/*当前得到的一组解是否满足式(2)*/printf(%2d:%d%d%d\n,++count,x,y,z);}}42.最大公约数和最小公倍数求任意两个正整数的最大公约数和(GCD)和最小公倍数(LCM)*问题分析与算法设计手工方式求两个正整数的蝚大公约数的方法是用辗转相除法，在程序中可以模拟这种方式。*程序说明与注释#includestdio.hintmain(){inta,b,num1,num2,temp;printf(Inputa&b:);scanf(%d%d,&num1,&num2);if(num1num2)/*找出两个数中的较大值*/{temp=num1;num1=num2;num2=temp;/*交换两个整数*/}a=num1;b=num2;while(b!=0)/*采用辗转相除法求最大公约数*/{temp=a%b;a=b;b=temp;}printf(TheGCDof%dand%dis:%d\n,num1,num2,a);/*输出最大公约数*/printf(TheLCMofthemis:%d\n,num1*num2/a);/*输出最小公倍数*/}*运行结果1.Inputa&b:2055TheGCDof20and55is:5TheLCMofthemis:2202.Inputa&b:1771TheGCDof17and71is:1TheLCMofthemis:12073.Inputa&b:2488TheGCDof24and88is:8TheLCMofthemis:2644.Inputa&b:3585TheGCDof35and85is:5TheLCMofthemis:595*思考题求一个最小的正整数，这个正整数被任意n(2=n=10)除都是除不尽的，而且余数总是(n-1)。例如：被9除时的余数为8。要求设计一个算法，不允许枚举与除2、除3、....、除9、除10有关的命令，求出这个正整数。43.分数比较比较两个分数的大小。*问题分析与算法设计人工方式下比较分数大小最常用的方法是：进行分数的通分后比较分子的大小。可以编程模拟手式方式。*程序说明与注释#includestdio.hintzxgb(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(mn)printf(%d/%d%d/%d\n,i,j,k,l);/*比较分子的大小*/elseif(m==n)printf(%d/%d=%d/%d\n,i,j,k,l);/*输出比较的结果*/elseprintf(%d/%d%d/%d\n,i,j,k,l);}intzxgb(inta,intb){longintc;intd;if(ab)c=a,a=b,b=c;/*若ab,则交换两变量的值*/for(c=a*b;b!=0;){d=b;b=a%b;a=d;}return(int)c/a;}*运行结果输入：4/5，6/7输出：4/56/7输入：8/4，16/32输出：8/416/32输入：16/32，4/8输出：16/32=4/844.分数之和求这样的四个自然数p,q,r,s(p=q=r=s)，使得以下等式成立：1/p+1/q+1/r+1/s=1*问题分析与算法设计若规定p=q=r=s，将原式通分、化简并整理后得到：2=p5p=q7qr13采用最简单的穷举方法可以很方便的求解。程序与程序注释:#includestdio.hintmain(){intp,q,r,s,count=0;printf(The4fractionswhichsumisequal1are:\n);for(p=2;p5;p++)/*穷举分母*/for(q=p;q7;q++)for(r=q;r13;r++)if(p*q*r-q*r-p*r-p*q!=0){s=(p*q*r)/(p*q*r-q*r-p*r-p*q);/*求出s的值*/if(!((p*q*r)%(p*q*r-q*r-p*r-p*q))&&s=r)printf([%2d]1/%d+1/%d+1/%d+1/%d=1\n,++count,p,q,r,s);/*输出结果*/}}*运行结果*思考题将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退出。具体的算法我没有认真看，有问题请提出，谢谢*/#includestdio.hintmain(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/%ld\n,c);break;/*a为1标志结束*/}elseprintf(1/%ld+,c);a=a*c-b;/*求出余数的分子*/b=b*c;/*求出余数的分母*/if(a==3)/*若余数为3，输出最后两个埃及分数*/{printf(1/%ld+1/%ld\n,b/2,b);break;}}}return0;}*运行结果Pleaseenteraoptionalfraction(a/b):1/6Itcanbedecomposedto:1/6Pleaseenteraoptionalfraction(a/b):20/33Itcanbedecomposedto:1/2+1/10+1/165Pleaseenteraoptionalfraction(a/b):10/89Itcanbedecomposedto:1/9+1/801Pleaseenteraoptionalfraction(a/b):19/99Itcanbedecomposedto:1/6+1/40+1/3960Pleaseenteraoptionalfraction(a/b):8/87Itcanbedecomposedto:1/11+1/957……（按ctrl-c退出）46.列出真分数序列按递增顺序依次列出所有分母为40，分子小于40的最简分数。*问题分析与算法设计对分子采用穷举法，利用最大公约数的方法，判断分子与40是否构成真分数。*程序说明与注释#includestdio.hintmain(){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/4021/4023/4027/4029/4031/4033/4037/4039/40*思考题按递增顺序依次列出所有分母小于等于40的最简真分数47.计算分数的精确值使用数组精确计算M/N(0MN=100)的值。如果M/N是无限循环小数，则计算并输出它的第一循环节，同时要求输出循环节的起止位置(小数位的序号)*问题分析与算法设计由于计算机字长的限制，常规的浮点运算都有精度限制，为了得到高精度的计算结果，就必须自行设计实现方法。为了实现高精度的计算，可将商存放在一维数组中，数组的每个元素存放一位十进制数，即商的第一位存放在第一个元素中，商的第二位存放在第二个元素中....，依次类推。这样就可以使用数组不表示一个高精度的计算结果。进行除法运算时可以模拟人的手工操作，即每次求出商的第一位后，将余数乘以10，再计算商的下一位，重复以上过程，当某次计算后的余数为0时，表示M/N为有限不循环小数某次计算后的余数与前面的某个余数相同时，则M/N为无限循环小数，从该余数第一次出现之后所求得的各位数就是小数的循环节。程序具体实现时，采用了数组和其它一些技巧来保存除法运算所得到的余数和商的各位数。*程序说明与注释#includestdio.hintremainder[101],quotient[101];/*remainder:存放除法的余数；quotient:依次存放商的每一位*/intmain(){intm,n,i,j;printf(Pleaseinputafraction(m/n)(0mn=100):);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=m/n;/*商*/m=m%n;/*求余数*/if(m==0)/*余数为0则表示是有限小数*/{for(j=1;j=1;j++)printf(%d,quotient[j]);/*输出商*/break;/*退出循环*/}if(remainder[m]!=0)/*若该余数对应的位在