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<stdio.h>
int main()
{
int x,y,z,count=0;
printf(" Men Women Children\n");
printf("………………………………….\n");
for(x=0;x<=10;x++)
{
y=20-2*x; /*x定值據(3)式求y*/
z=30-x-y; /*由(1)式求z*/
if(3*x+2*y+z==50) /*當前得到的一組解是否滿足式(2)*/
printf(" %2d: %d %d %d\n",++count,x,y,z);
}
}

 

 42.最大公約數和最小公倍數

求任意兩個正整數的最大公約數和(GCD)和最小公倍數(LCM)

*問題分析與算法設計
手工方式求兩個正整數的蝚大公約數的方法是用輾轉相除法，在程序中可以模擬這種方式。

*程序說明與注釋
#include<stdio.h>
int main()
{
int a,b,num1,num2,temp;
printf("Input a & b:");
scanf("%d%d",&num1,&num2);
if(num1>num2) /*找出兩個數中的較大值*/
{
temp=num1; num1=num2; num2=temp; /*交換兩個整數*/
}
a=num1; b=num2;
while(b!=0) /*采用輾轉相除法求最大公約數*/
{
temp=a%b;
a=b;
b=temp;
}
printf("The GCD of %d and %d is: %d\n",num1,num2,a); /*輸出最大公約數*/
printf("The LCM of them is: %d\n",num1*num2/a); /*輸出最小公倍數*/
}

*運行結果
1.Input a & b: 20 55
The GCD of 20 and 55 is: 5
The LCM of them is: 220

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.分數比較

比較兩個分數的大小。

*問題分析與算法設計
人工方式下比較分數大小最常用的方法是：進行分數的通分后比較分子的大小。可以編程模擬手式方式。

*程序說明與注釋
#include<stdio.h>
int zxgb(int a,int b);
int main()
{
int i,j,k,l,m,n;
printf("Input two FENSHU:\n");
scanf("%d/%d,%d/%d",&i,&j,&k,&l); /*輸入兩個分數*/
m=zxgb(j,l)/j*i; /*求出第一個分數通分后的分子*/
n=zxgb(j,l)/l*k; /*求出第二個分數通分后的分子*/
if(m>n) printf("%d/%d>%d/%d\n",i,j,k,l); /*比較分子的大小*/
else if(m==n) printf("%d/%d=%d/%d\n",i,j,k,l); /*輸出比較的結果*/
else printf("%d/%d<%d/%d\n",i,j,k,l);
}

int zxgb(int a,int b)
{
long int c;
int d;
if(a<b) c=a,a=b,b=c; /*若a<b,則交換兩變量的值*/
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<5 p<=q<7 q<r<13
采用最簡單的窮舉方法可以很方便的求解。
程序與程序注釋:
#include<stdio.h>
int main()
{
int p,q,r,s,count=0;
printf("The 4 fractions which sum is equal 1 are:\n");
for(p=2;p<5;p++) /*窮舉分母*/
for(q=p;q<7;q++)
for(r=q;r<13;r++)
if(p*q*r-q*r-p*r-p*q!=0)
{
s=(p*q*r)/(p*q*r-q*r-p*r-p*q); /*求出s的值*/
if(!((p*q*r)%(p*q*r-q*r-p*r-p*q))&&s>=r)
printf("[%2d] 1/%d+1/%d+1/%d+1/%d=1\n",++count,p,q,r,s);
/*輸出結果*/
}
}

*運行結果

*思考題
將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<stdio.h>
int main(void)
{
long int a,b,c;
while(true)
{
printf("Please enter a optional fraction(a/b):");
scanf("%ld/%ld",&a,&b); /*輸入分子a和分母b*/
printf("It can be decomposed to:");
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標志結束*/
}
else
printf("1/%ld + ",c);
a=a*c-b; /*求出余數的分子*/
b=b*c; /*求出余數的分母*/
if(a==3) /*若余數為3，輸出最后兩個埃及分數*/
{ printf("1/%ld + 1/%ld\n",b/2,b); break;}
}
}

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<stdio.h>
int main()
{
int i,num1,num2,temp;
printf("The fraction serials with demominator 40 is:\n");
for(i=1;i<=40;i++) /*窮舉40以內的全部分子*/
{
num1=40;
num2=i;
while(num2!=0) /*采用輾轉相除法求出最大公約數*/
{
temp=num1%num2;
num1=num2;
num2=temp;
}
if(num1==1) /*若最大公約數為1，則為最簡真分數*/
printf("%d/40 ",i);

}
}

*運行結果
The fraction serials with demominator 40 is:
1/40 3/40 7/40 9/40 11/40 13/40 17/40 19/40
21/40 23/40 27/40 29/40 31/40 33/40 37/40 39/40

*思考題
按遞增順序依次列出所有分母小于等于40的最簡真分數

47.計算分數的精確值

使用數組精確計算M/N(0<M<N<=100)的值。如果M/N是無限循環小數，則計算并輸出它的第一循環節，同時要求輸出 循環節的起止位置(小數位的序號)

*問題分析與算法設計
由于計算機字長的限制，常規的浮點運算都有精度限制，為了得到高精度的計算結果，就必須自行設計實現方法。
為了實現高精度的計算，可將商存放在一維數組中，數組的每個元素存放一位十進制數，即商的第一位存放在第一個元素中，商的第二位存放在第二個元素中….，依次類推。這樣就可以使用數組不表示一個高精度的計算結果。
進行除法運算時可以模擬人的手工操作，即每次求出商的第一位后，將余數乘以10，再計算商的下一位，重復以上過程，當某次計算后的余數為0 時，表示M/N為有限不循環小數某次計算后的余數與前面的某個余數相同時，則M/N為無限循環小數，從該余數第一次出現之后所求得的各位數就是小數的循環節。
程序具體實現時，采用了數組和其它一些技巧來保存除法運算所得到的余數和商的各位數。

*程序說明與注釋
#include<stdio.h>
int remainder[101],quotient[101]; /*remainder:存放除法的余數； quotient:依次存放商的每一位*/
int main()
{
int m,n,i,j;
printf("Please input a fraction(m/n)(<0<m<n<=100):");
scanf("%d/%d",&m,&n); /*輸入被除數和除數*/
printf("%d/%d it's accuracy value is:0.",m,n);
for(i=1;i<=100;i++) /*i: 商的位數*/
{
remainder[m]=i; /*m:除的余數 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("\n\tand it is a infinite cyclic fraction from %d\n",remainder[m]);
printf("\tdigit to %d digit after decimal point.\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!=1 A不與X結婚
x!=3 X的未婚夫不是C
z!=3 C不與Z結婚
題意還隱含著X、Y、Z三個新娘不能結為配偶，則有：
x!=y且x!=z且y!=z
窮舉以上所有可能的情況，代入上述表達式中進行推理運算，若假設的情況使上述表達式的結果均為真，則假設情況就是正確的結果。

*程序說明與注釋
#include<stdio.h>
int main()
{
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("X will marry to %c.\n",'A'+x-1); /*打印判斷結果*/
printf("Y will marry to %c.\n",'A'+y-1);
printf("Z will marry to %c.\n",'A'+z-1);
}
}

*運行結果
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<stdio.h>
int main()
{
int a,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("A will%s be assigned. \n",a?"":"not");
printf("B will%s be assigned. \n",b?"":"not");
printf("C will%s be assigned. \n",c?"":"not");
printf("D will%s be assigned. \n",d?"":"not");
printf("E will%s be assigned. \n",e?"":"not");
printf("F will%s be assigned. \n",f?"":"not");
}
}

*運行結果
A will be assigned. (去)
B will be assigned. (去)
C will be assigned. (去)
D will not be assigned. (不去)
E will not be assigned. (不去)
F will be assigned. (去)

*思考題
某參觀團按以下條件限制從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<stdio.h>
int main()
{
int a,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("Zhangsan told a %s.\n",a?"truth":"lie");
printf("Lisi told a %s.\n",b?"truch":"lie");
printf("Wangwu told a %s.\n",c?"truch":"lie");
}
}

*運行結果
Zhangsan told a lie (張三說假話)
Lisi told a truch. (李四說真話)
Wangwu told a lie. (王五說假話)