趣味程序设计编程百例精解(5)

爱因斯坦出了一道这样的数学题：有一条长阶梯，若每步跨2阶，则最最后剩一阶，若每步跨3 阶，则最后剩2阶，若每步跨5阶，则最后剩4阶，若每步跨6阶则最后剩5阶。只有每次跨7阶，最后才正好一阶不剩。请问这条阶梯共有多少阶？ *问题分析与算法设计

根据题意，阶梯数满足下面一组同余式： x≡1 (mod2) x≡2 (mod3) x≡4 (mod5) x≡5 (mod6) x≡0 (mod7) *程序说明与注释 for(k=0;k<=100-i-2*j;k+=5) /*k为5分硬币钱数*/ if(i+j+k==100)

printf(count%4?\d+2*%d+5*%d\\n\}

39.年龄几何

张三、李四、王五、刘六的年龄成一等差数列，他们四人的年龄相加是26，相乘是880，求以他们的年龄为前4项的等差数列的前20项。 *问题分析与算法设计

#include int main() {

int i=1; /*i为所设的阶梯数*/

while(!((i%2==1)&&(i%3==2)&&(i%5==4)&&(i%6==5)&&(i%7==0)))

++i; /*满足一组同余式的判别*/ printf(\}

*运行结果

Staris_number=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 int main() {

int i,j,k,count=1;

printf(\Yuan note:\\n\

for(i=0;i<=100;i++) /*i为1分硬币钱数，可取值0,1，2…,100*/

for(j=0;j<=100-i;j+=2) /*j为2分硬币钱数，可取0值，2，4，…，100*/

设数列的首项为a，则前4项之和为\前4 项之积为\。同时

\。可采用穷举法求出此数列。 *程序说明与注释 #include int main() { int n,a,i;

printf(\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(\输出前20项*/ }

*运行结果

The series with equal difference are: 2 5 8 11 14 17 20 23 26 29 32 35 38 41 44 47 50 53 56

59

40.三色球问题

若一个口袋中放有12个球，其中有3个红的。3个白的和6个黒的，问从中任取8个共有多少种不同的颜色搭配？ *问题分析与算法设计

设任取的红球个数为i，白球个数为j，则黒球个数为8-i-j，根据题意红球和白球个数的取值范围是0~3，在红球和白球个数确定的条件下，黒球个数取值应为8-i-j<=6。 *程序说明与注释 #include int main() {

int i,j,count=0;

printf(\

- 21 -

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(\}

C/C++语言经典、实用、趣味程序设计编程百例精解（5） 41.马克思手稿中的数学题

马克思手稿中有一道趣味数学问题：有30个人，其中有男人、女人和小孩，在一家饭馆吃饭花了50先令；每个男人花3先令，每*程序说明与注释 #include int main() {

int a,b,num1,num2,temp; printf(\scanf(\

if(num1>num2) /*找出两个数中的较大值*/ {

temp=num1; num1=num2; num2=temp; /*交换两个整数*/ }

a=num1; b=num2;

while(b!=0) /*采用辗转相除法求最大公约数*/ 个女人花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 int main() {

int x,y,z,count=0;

printf(\

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(\} }

42.最大公约数和最小公倍数

求任意两个正整数的最大公约数和(GCD)和最小公倍数(LCM) *问题分析与算法设计

手工方式求两个正整数的蝚大公约数的方法是用辗转相除法，在程序中可以模拟这种方式。

{

temp=a%b; a=b; b=temp; }

printf(\输出最大公约数*/

printf(\输出最小公倍数*/ }

*运行结果

1.Input a & b: 20 55 The GCD of 20 and 55 is: 5 The LCM of them is: 220 2.Input a & b: 17 71 The GCD of 17 and 71 is: 1 The LCM of them is: 1207 3.Input a & b: 24 88 The GCD of 24 and 88 is: 8 The LCM of them is: 264 4.Input a & b: 35 85 The GCD of 35 and 85 is: 5 The LCM of them is: 595 *思考题

求一个最小的正整数，这个正整数被任意n(2<=n<=10)除都是除不尽的，而且余数总是(n-1)。例如：被9除时的余数为8。要求设计一个算法，不允许枚举与除2、除3、?.、除9、除10有关的命令，求出这个正整数。 43.分数比较

比较两个分数的大小。

- 22 -

*问题分析与算法设计

人工方式下比较分数大小最常用的方法是：进行分数的通分后比较分子的大小。可以编程模拟手式方式。 *程序说明与注释 #include int zxgb(int a,int b); int main() {

int i,j,k,l,m,n;

printf(\

scanf(\输入两个分数*/ m=zxgb(j,l)/j*i; /*求出第一个分数通分后的分子*/ n=zxgb(j,l)/l*k; /*求出第二个分数通分后的分子*/

printf(\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(\

if(m>n) printf(\/*比较分子的大小*/

else if(m==n) printf(\输出比较的结果*/

else printf(\}

int zxgb(int a,int b) {

long int c; int d;

if(a

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<5 p<=q<7 q

采用最简单的穷举方法可以很方便的求解。 程序与程序注释: #include int main() {

int p,q,r,s,count=0;

*思考题

将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 int main(void) {

long int a,b,c; while(true) {

printf(\scanf(\输入分子a和分母b*/ printf(\while(true) {

if(b%a) /*若分子不能整除分母*/

c=b/a+1; /*则分解出一个分母为b/a+1的埃及分数*/

- 23 -

else{ c=b/a; a=1;} /*否则，输出化简后的真分数(埃及分数)*/ if(a==1) {

printf(\break; /*a为1标志结束*/ } else

printf(\a=a*c-b; /*求出余数的分子*/ b=b*c; /*求出余数的分母*/

if(a==3) /*若余数为3，输出最后两个埃及分数*/ { printf(\} while(num2!=0) /*采用辗转相除法求出最大公约数*/ {

temp=num1%num2; num1=num2; num2=temp; }

if(num1==1) /*若最大公约数为1，则为最简真分数*/ printf(\} }

*运行结果

The fraction serials with demominator 40 is: }

return 0; }

*运行结果

Please enter a optional fraction (a/b): 1/6 It can be decomposed to: 1/6

Please enter a optional fraction (a/b): 20/33 It can be decomposed to: 1/2+1/10+1/165 Please enter a optional fraction (a/b): 10/89 It can be decomposed to: 1/9+1/801

Please enter a optional fraction (a/b): 19/99 It can be decomposed to: 1/6+1/40+1/3960 Please enter a optional fraction (a/b): 8/87 It can be decomposed to: 1/11+1/957 ??（按ctrl-c退出） 46.列出真分数序列

按递增顺序依次列出所有分母为40，分子小于40的最简分数。 *问题分析与算法设计

对分子采用穷举法，利用最大公约数的方法，判断分子与40是否构成真分数。 *程序说明与注释 #include int main() {

int i,num1,num2,temp;

printf(\for(i=1;i<=40;i++) /*穷举40以内的全部分子*/ { num1=40; num2=i;

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的最简真分数 47.计算分数的精确值

使用数组精确计算M/N(0

由于计算机字长的限制，常规的浮点运算都有精度限制，为了得到高精度的计算结果，就必须自行设计实现方法。

为了实现高精度的计算，可将商存放在一维数组中，数组的每个元素存放一位十进制数，即商的第一位存放在第一个元素中，商的第二位存放在第二个元素中?.，依次类推。这样就可以使用数组不表示一个高精度的计算结果。

进行除法运算时可以模拟人的手工操作，即每次求出商的第一位后，将余数乘以10，再计算商的下一位，重复以上过程，当某次计算后的余数为0 时，表示M/N为有限不循环小数某次计算后的余数与前面的某个余数相同时，则M/N为无限循环小数，从该余数第一次出现之后所求得的各位数就是小数的循环节。 程序具体实现时，采用了数组和其它一些技巧来保存除法运算所得到的余数和商的各位数。 *程序说明与注释 #include

int remainder[101],quotient[101]; /*remainder:存放除法的余数； quotient:依次存放商的每一位*/ int main() {

int m,n,i,j;

printf(\scanf(\输入被除数和除数*/ printf(\for(i=1;i<=100;i++) /*i: 商的位数*/ {

- 24 -

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(\输出商*/ break; /*退出循环*/ }

if(remainder[m]!=0) /*若该余数对应的位在前面已经出现过*/ {

for(j=1;j<=i;j++) printf(\则输出循环{

int x,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(\printf(\} }

printf(\打印判断结果*/

小数*/

printf(\from %d\\n\

printf(\/*输出循环节的位置*/ 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!=1 A不与X结婚 x!=3 X的未婚夫不是C z!=3 C不与Z结婚

题意还隐含着X、Y、Z三个新娘不能结为配偶，则有： x!=y且x!=z且y!=z

穷举以上所有可能的情况，代入上述表达式中进行推理运算，若假设的情况使上述表达式的结果均为真，则假设情况就是正确的结果。

*程序说明与注释 #include int main()

*运行结果

X will marry to B. (X与B结婚) Y will marry to C. (Y与C结婚) Z will marry to A. (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>1 A和B两人中至少去一人； a+d!=2 A和D不能一起去；

a+e+f==2 A、E、F三人中要派两人去； b+c==0或b+c==2 B和C都去或都不去； c+d==1 C和D两人中去一个；

d+e==0或d==1 若D不去，则E也不去(都不去；或D去E随便)。上述各表达式之间的关系为“与”关系。穷举每个人去或不去的各种可能情况，代入上述表达式中进行推理运算，使上述表达式均为“真”的情况就是正确的结果。 *程序说明与注释 #include int main() {

int a,b,c,d,e,f;

- 25 -