08.txt

CC++语言程序百例精解 非常经典的C

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");
}