可用分押宝游戏火热进行中...	专题改版：Java Web 专题

关于出圈问题的疑惑，里面有许多方面不明白，希望高人指点迷津

楼主mafachang（）2004-09-04 04:03:22 在 C/C++ / C语言提问

题目如下：
34题设有n个人围坐一圈并按顺时针方向从1到n编号，从第s个人开始进行1到m的报数，报数到第个m人，此人出圈，再从他的下一个人重新开始1到m的报数，如此进行下去直到所有的人都出圈为止。现要求按出圈次序，每10人一组，给出这n个人的顺序表。请考生编制函数Josegh()实现此功能并调用函数WriteDat()把结果p输出到文件OUT.DAT中。
设n=100,c=1,m=10.
(1)将1到n个人的序号存入一维数组p中；
(2)若第i个人报数后出圈，则将p[i]置于数组的倒数第i个位置上，而原来第i+1个至倒数第i个元素依次向前移动一个位置；
(3)重复第(2)步直至圈中只剩下p[1]为止。
部分源程序已给出。
请勿改动主函数main()和输出数据函数writeDat()的内容。 #include <stdio.h>
#define N 100
#define S 1
#define M 10

int p[100],n,s,m;
void WriteDat(void);

void Josegh(void)
{
　
}

void main()
{
m=M;
n=N;
s=S;
Josegh();
WriteDat();
}

void WriteDat(void)
{
int i;
FILE *fp;

fp=fopen(\ out.dat\ ,\ w\ );
for(i=N-1;i>=0;i--){
printf(\ %4d\ ,p[i]);
fprintf(fp,\ %4d\ ,p[i]);
if(i % 10==0){
printf(\ \\n\ );
fprintf(fp,\ \\n\ );
}
}
fclose(fp);
}

给出的答案：
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;
}
}

不明白的地方是：
s1=(s1+m-1)%i;
书上给的解释是：
其中对i求余的作用是使报
数按圈进行（即报到尾后又从头报），该算法在很多题目中都用到。由于求余的作用当
报数正好到最后一个时s1为0，故而要进行if(s1==0)的判断。
是在想不明白，这种算法到底什么意思问题点数：10、回复次数：10Top

1 楼ntxs（别人加薪我加班，数钱数到心发酸T_T）回复于 2004-09-04 04:21:50 得分 1

看不懂懒得想了

去搜索约瑟夫问题

这样的题目用循环链表最直观了Top

2 楼liacw1017（梁上君子）回复于 2004-09-04 07:50:05 得分 2

s1=(s1+m-1)%i;,意思就是從sl開始報數,報數為m的號碼賦值給sl,,隨著i的增加,圈就越來越小了,然後就懂了,我看明白了,不過我從來沒有這樣想過,(以前遇到過出圈的問題).
Top

3 楼liushuaiboy（标准菜鸟）回复于 2004-09-04 10:31:21 得分 2

楼主画一个圈试试就知道了，在数到最后一个的时候要跳到第一个接着数啊，就是这个意思Top

4 楼comebaby（游民）回复于 2004-09-04 12:55:40 得分 1

s1=(s1+m-1)%i;
i是指圈的大小，s1=(s1+m-1)%i就是取下一个出圈人的标号Top

5 楼xczjl（偶的DD比我长）回复于 2004-09-04 13:05:20 得分 0

是啊!去网上搜索一下吧!Top

6 楼hshua424（东北菜鸟）回复于 2004-09-04 19:45:22 得分 1

就是数完一圈在回来，这个算法叫求模运算Top

7 楼fanbest（座天使长）回复于 2004-09-04 20:24:45 得分 1

来晚了。Top

8 楼jk01dingxian（蓝光书虫~痛并快乐着~）回复于 2004-09-04 20:30:20 得分 1

我在钱能的<C++程序设计>里看过.里头有好几次出现过.不用类的，用类的,用了继承,多态的.呵呵.他用这个程序来讲C++.Top

9 楼jk01dingxian（蓝光书虫~痛并快乐着~）回复于 2004-09-04 20:32:43 得分 1

我前天刚删除了他的电子版的书.你搜搜看吧,在网上,你看了后一定会明白的.我这几天很忙.Top

10 楼lwjhehe（）回复于 2005-04-11 22:38:51 得分 0

我也想了好久想不通。
我自己用从第n个开始就从第n个开始排，然后把n前面的接到后面去。
行是行的通，但还是有小bug。头好痛。
搞不明白啊Top