c-c++语言趣味程序设计编程百例精解(8)

《c-c++语言趣味程序设计编程百例精解(8)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、C-C++语言趣味程序设计编程百例精解(8)71.约瑟夫问题这是17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。*问题分析与算法设计约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实现方法。题目中30个人围成一圈，因而启发我们用一个循环的链来

2、表示。可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。*程序说明与注释#includestructnode{intnextp;/*指向下一个人的指针(下一个人的数组下标)*/intno_out;/*是否被扔下海的标记。1：没有被扔下海。0：已被扔下海*/}link[31];/*30个

3、人，0号元素没有使用*/intmain(){inti,j,k;printf("Theoriginalcircleis(+:pagendom,@:christian):");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]指向的人开

4、始计数*/for(i=0;i<15;i++)/*i:已扔下海的人数计数器*/{for(k=0;;)/*k:决定哪个人被扔下海的计数器*/if(k<15){j=link[j].nextp;/*修改指针，取下一个人*/k+=link[j].no_out;/*进行计数。因已扔下海的人计标记为0*/}elsebreak;/*计数到15则停止计数*/link[j].no_out=0;/*将标记置0，表示该人已被扔下海*/}for(i=1;i<=30;i++)/*输出结果*/printf("%c",link[i].no_out?'@':'

5、+');/*+:被扔下海，@：在船上*/printf("");}*运行结果Theoriginalcircleis(+:pagandom,@:christian):+++@@+@+@@@+@+++@@+@@@+++@+@@+(+"表示被扔下海海的非教徒@：留在船上活命的教徒)*思考题有N个小孩围成一圈并依次编号，教师指定从第M个小孩开始报数，报到第S个小孩即令其出列。然后从下一个孩子继续报数，数到第S个小孩又令其出列，如此直到所有的孩子都出列。求小孩出列的先后顺序。72.邮票组合某人有四张3分的邮票和三张5分的邮票，用这些邮

6、票中的一张或若干张可以得到多少种不同的邮资？*问题分析与算法设计将问题进行数学分析，不同张数和面值的邮票组成的邮资可用下列公式计算：S=3*i+5*j其中i为3分邮柰的张数，j为5分的张数按题目的要求，3分的邮票可以取0、1、2、3、4张，5分的邮票可以取0、1、2、3张。采用穷举方法进行组合，可以求出这些不同面值不同张数的邮标组合后的邮资。*程序说明与注释#includeinta[27];intmain(){inti,j,k,s,n=0;for(i=0;i<=4;i++)/*i:取三分邮票的张数*/for(

7、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("%dkinds:",n);/*输出结果*/for(k=0;a[k];k++)printf("%d",a[k]);printf("");}*运行结果19kinds:5101538131861116219141924121

8、7222773.和数能表示1~23的5个正整数已知五个互不相同的正整数之和为23，且从这五个数中挑选若干个加起来可以表示从1到23之内的全部自然数。问这五个数是什么？*问题分析与算法设计从计算机程序设计的角度来说，可以用穷举法分解23，然后判断所分解的五个数是否可以表示1到2