c++作业题 求解析!!

实验题3.1 M个人围成一圈,从第一个人开始依次从1循环报数,每当报数为N时此人从圈中出来,下一个人又从1开始报数,直到圈中只剩下一个人为止。请按退出次序输出出圈人员来的编号以及留在圈中的最后一个人原来的编号。
提示:方法一
(1)、声明两个数组,A数组存放人是否在圈中的标记,在为0,已出列为-1;B数组存放编号,是顺序记录出圈人的顺序,最后一个即为留在圈中的人。组成圈的人数为M,报号为N。
(2)、 A数组因为是表示一个圈,所以最后一个接着第一个,当编号大于最后一个编号时,接到前面开始部分。当下标号为M时,让其再变为0,下标号为M以后相当于0开始的又一圈开始。
方法二:用链表实现
初学者,自己尝试了很久,总是错误,想求教各位大虾~~
十分感谢!

首先理解题意
设有n个人围坐一圈并按顺时针方向从1到n编号。
从第s个人开始进行1到m的报数, 报数到第m个人, 此人出圈, 再从他的下一个人重新开始1到m的报数,如此进行下去直到所有的人都出圈为止。
现要求按出圈次序,给出这n个人的顺序表p。

木易版答案:
void Josegh(void)
{ int i,j,s1,w;
s1=s;
for(i=1; i<=n; i++)
p[i-1]=i;
for(i=n; i>=2; i--)
{ s1=(s1+m-1)%i;
if(s1==0) s1=i;
w=p[s1-1];
for(j=s1; j<i; j++)
p[j-1]=p[j];
p[i-1]=w;
}
}
这里提出几个广泛流传的错误:
本人在学习此题过程中发现,不管是网上还是书店的一些参考书中,对此题的讲解都有一些错误!本人在这里提出几个广泛流传的错误,希望大家指正!
① 南开上机题或无忧上机题的题干错误!
原题干:
若第i个人报数后出圈,则将p[i]置于数组的倒数第i个位置上,而原来第i+1个至倒数第i个元素依次向前移动一个位置。
举个例子:
套用原题干:
若第10个人报数后出圈,则将p[10]置于数组的倒数第10个位置上,而原来第11个至倒数第10个元素依次向前移动一个位置。
上面这句话显然不对!
而实际上是:
原列队第10个人报数后出圈(即编号为10的人报数出圈),则将p[9]置于数组的倒数第1个位置上,而原来第11个至倒数第1个元素依次向前移动一个位置。
或这么表述:
第1个报数后出圈的人(因为编号为10的人是第1个报数出圈的),将p[9]置于数组的倒数第1个位置上,而原来第11个至倒数第1个元素依次向前移动一个位置。
错误分析:
编题的人没有搞清其实“出圈次序”“出圈人编号”“出圈人所对应的数组下标”是三个不同的概念!
如:第一个出圈的人,出圈次序是1,下标是p[9],编号是10。
而编题人简单地都用i表示了!显然不对!
这里我认为本句话应该改为:
第i个人报数出圈的人,将“此人的编号”置于数组的倒数第i个位置上。
②市面上卖的谭浩强主编的《三级C语言上机指导》一书中(清华大学出版社2005年7月第1版封皮是红色的价格是22.00元)对此题的解释也有错误:
讲解中说:s1=(s1+m-1)%i的作用是找出报数后出圈人的下标。
本人认为编者也犯了类似的错误:
应该改为:
s1=(s1+m-1)%i的作用是找出报数后出圈人的“编号”。
因为变量s1表示的不是出圈人的所对应的数组下标,而是其“编号”。
清楚变量:
变量i:表示没有出圈的人数。
变量s1:表示出圈人所对应的编号。编号s1=p[s1-1]。
变量w:暂存变量,用于暂时存放刚刚出圈人的编号。
数组p[]:存放出圈人编号的数组。程序结束后,该数组按出圈次序倒序存放出圈人的编号。

思路步骤:
①建立数组,应注意:p[下标]=编号 ;下标=编号-1;编号s1=p[s1-1]。
对应代码是:for(i=1; i<=n; i++) p[i-1]=i;
②倒序循环for(i=n; i>=2; i--),找出出圈人的“编号”s1。
对应的算法是通过求余得到的!s1=(s1+m-1)%i;
③将刚出圈人的编号先寄存在暂存变量中。
④将刚出圈的人之后至原队列最后一个未出圈的人依次在数组中前移一位。对应的代码是:for(j=s1; j<i; j++) p[j-1]=p[j];
⑤将刚出圈人的编号放置在最后一个未出圈的人的后面,即p[i-1]的位置上。

注意事项:
①此题有两种变形,差别在于出圈人编号的存放顺序。考生应注意考题中是哪种变形!
形式一:
若第i个人报数后出圈,则将此人编号置于数组的倒数第i个位置上,而原来第i+1个至倒数第i个元素依次向前移动一个位置;即第1个出圈的编号存放在p[n-1]中,第2个出圈的编号存放在p[n-2]中,直至第n个出圈的编号存放在p[0]中。
对应的void WriteDat(void) 函数中的循环语句是for(i=N-1; i>=0; i--)
形式二:
第1个出圈的编号存放在p[0]中,第2个出圈的编号存放在p[1]中,直至第n个出圈的编号存放在p[n-1]中。
对应的void WriteDat(void) 函数中的循环语句是for(i = 0 ; i <= N - 1 ; i++)
上面答案是形式一的答案。
若遇到形式二,考生须在原有答案的基础上再增加两个循环以使循序颠倒过来!
for(i=0,j=n-1;i<n,j>=0;i++,j--) /*也可改为for(i=0,j=n-1;i<n;i++,j--) */
q[j]=p[i];
for(i=0;i<n;i++)
p[i]=q[i];
②由于求余的作用,当报数人正好到最后一个人时s1为0,故要有if(s1==0) s1=i;
③根据题意,开始时莫忘设置s1=s;

参考资料:http://bbs.ncre.cn/viewthread.php?tid=86618

温馨提示:答案为网友推荐,仅供参考
第1个回答  2011-03-14
典型的约瑟夫循环啊。。百度一下约瑟夫循环吧。。我就不去复制了。
相似回答