C/C++語言經典、實用、趣味程序設計編程百例精解（8）

71.約瑟夫問題

這是17世紀的法國數學家加斯帕在《數目的游戲問題》中講的一個故事：15個教徒和15 個非教徒在深海上遇險，必須將一半的人投入海中，其余的人才能幸免于難，于是想了一個辦法：30個人圍成一圓圈，從第一個人開始依次報數，每數到第九個人就將他扔入大海，如此循環進行直到僅余15個人為止。問怎樣排法，才能使每次投入大海的都是非教徒。

*問題分析與算法設計
約瑟夫問題并不難，但求解的方法很多；題目的變化形式也很多。這里給出一種實現方法。
題目中30個人圍成一圈，因而啟發我們用一個循環的鏈來表示。可以使用結構數組來構成一個循環鏈。結構中有兩個成員，其一為指向下一個人的指針，以構成環形的鏈；其二為該人是否被扔下海的標記，為1表示還在船上。從第一個人開始對還未扔下海的人進行計數，每數到9時，將結構中的標記改為0，表示該人已被扔下海了。這樣循環計數直到有15個人被扔下海為止。

*程序說明與注釋
#include<stdio.h>
struct node
{
int nextp; /*指向下一個人的指針(下一個人的數組下標)*/
int no_out; /*是否被扔下海的標記。1：沒有被扔下海。0：已被扔下海*/
}link[31]; /*30個人，0號元素沒有使用*/
int main()
{
int i,j,k;
printf("The original circle is(+: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*/
}
else break; /*計數到15則停止計數*/
link[j].no_out=0; /*將標記置 0，表示該人已被扔下海*/
}
for(i=1;i<=30;i++) /*輸出結果*/
printf("%c",link[i].no_out? '@':'+'); /*+:被扔下海， @：在船上*/
printf("\n");
}

*運行結果
The original circle is(+: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<stdio.h>
int a[27];
int main()
{
int i,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("%d kinds:",n); /*輸出結果*/
for(k=0;a[k];k++)
printf("%d ",a[k]);
printf("\n");
}

*運行結果
19 kinds: 5 10 15 3 8 13 18 6 11 16 21 9 14 19 24 12 17 22 27

 73.和數能表示1~23的5個正整數

已知五個互不相同的正整數之和為23，且從這五個數中挑選若干個加起來可以表示從1到23之內的全部自然數。問這五個數是什么？

*問題分析與算法設計
從計算機程序設計的角度來說，可以用窮舉法分解23，然后判斷所分解的五個數是否可以表示1到23 之間的全部整數。

*程序說明與注釋
#include<stdio.h>
int main()
{
int a,b,c,d,e,i,j,k,l,m,x,count=0,f=0; /*f:分解的5個數可以表示出1~23的標記*/
printf("There are following possble result:\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 %d\n",++count,a,b,c,d,e);
}
}

*運行結果
There are following possble result:
[1]: 1 2 3 5 12
[2]: 1 2 3 6 11
[3]: 1 2 3 7 10
[4]: 1 2 4 5 11
[5]: 1 2 4 6 10
[6]: 1 2 4 7 9

74.可稱1~40磅的4塊砝碼

法國數學家梅齊亞克在他著名的《數字組合游戲》(1962)中提出了一個問題：一位商人有一個重40磅的砝碼，一天不小心將砝碼摔成了四塊。后來商人稱得每塊的重量都是整磅數，而且發現這四塊碎片可以在天平上稱1至40磅之間的任意重量。請問這四塊碎片各重多少？

*問題分析與算法設計
本題是上一題的發展。題目中給出的條件是“在天平上”，這意味著：同一砝碼既可以放在天平的左側，也可以放在天平的右側。若規定重物只能放在天平的左側，則當天平平衡時有：
重物重量+左側砝碼重量總和=右側砝碼重量總和
由此可得：
重物重量=右側砝碼重量總和-左側砝碼重量總和
編程時只要根據以上公式，使“右側砝碼重量總和-左側砝碼重量總和”可以表示1到40之間的全部重量即可。編程中要注意的是：怎樣采用一種簡單的方法來表示一個砝碼是在天平的左側還是在天平的右側，或是根本沒有使用。
以下程序采用1、 -1和0分別表示上述三種情況，請注意理解。

*程序說明與注釋
#include<stdio.h>
#include<math.h>
int main()
{
int weight1,weight2,weight3,weight4,d1,d2,d3,d4,x,flag; /*flag:滿足題意的標記*/
printf("The weight is broke up as following 4 pieces:");
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 %d\n",weight1,weight2,weight3,weight4);
flag=0;
}
}

*運行結果
The weight is broke up as following 4 pieces: 1 3 9 27

75.10個小孩分糖果

十個小孩圍成一圈分糖果，老師分給第一個小孩10塊，第二個小孩2塊，第三個小孩8塊，第四個小孩22塊，第五個小孩16塊，第六個小孩4塊，第七個小孩10塊，第八個小孩6塊，第九個小孩14塊，第十個小孩20塊。然后所有的小孩同時將手中的糖分一半給右邊的小孩；糖塊數為奇數的人可向老師要一塊。問經過這樣幾次后大家手中的糖的塊數一樣多？每人各有多少塊糖？

*問題分析與算法設計
題目描述的分糖過程是一個機械的重復過程，編程算法完全可以按照描述的過程進行模擬。

*程序說明與注釋
#include<stdio.h>
void print(int s[]);
int judge(int c[]);
int j=0;
int main()
{
static int sweet[10]={10,2,8,22,16,4,10,6,14,20}; /*初始化數組數據*/
int i,t[10],l;
printf(" child\n");
printf(" round 1 2 3 4 5 6 7 8 9 10\n");
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); /*輸出當前每個孩子中手中的糖數*/
}
}
int judge(int c[])
{
int i;
for(i=0;i<10;i++) /*判斷每個孩子手中的糖是否相同*/
if(c[0]!=c[i]) return 1; /*不相同返回 1*/
return 0;
}
void print(int s[]) /*輸出數組中每個元素的值*/
{
int k;
printf(" %2d ",j++);
for(k=0;k<10;k++) printf("%4d",s[k]);
printf("\n");
}