职业IT人-IT人生活圈

 找回密码
 成为会员
搜索
查看: 827|回复: 2

约瑟夫环问题

[复制链接]
烈火奥拓仔 发表于 2009-8-18 11:16 | 显示全部楼层 |阅读模式
计算机三级上机试题的约瑟夫环问题的答案是
void Josegh(void)
{int i,j;
int 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-1;j++)
p[j-1]=p[j];
p[i-1]=w;
}
}
请问
其中的s1=(s1+m-1)为什么要减一呢?
若n=100
s=1
m=10
则按照程序执行第一个循环时
i=100
s1=(1+10-1)%100=10
按上面说的就是编号为10的是下一次开始报数的人
但是从编号为1的开始报数时
1是1
2报2
3报3
到10就报10
该编号为10的人出圈
下一次开始报数的应该是编号为11的人啊
为什么表达式要减1呢?
dgyys 发表于 2009-8-18 11:16 | 显示全部楼层

约瑟夫环问题

约瑟夫环有好多种解法
但是大体的可以分为两类:
1. 将符合出圈要求的人进行标注
但是不出圈
只是下次再轮到此人时
直接跳过
不参加报数
2. 将符合出圈要求的人直接出圈(从环中删除)
剩下的人继续报数

这里列的是第二种方法
出圈的处理在这里: p[i-1]=i;
由于已经有人出圈
所以编号也就得-1了:(s1+m-1)%i
虎儿 发表于 2009-8-18 11:16 | 显示全部楼层

约瑟夫环问题

for(j=s1;j<=i-1;j++)
p[j-1]=p[j];
看到了么,这段代码已经把原来的第11号人移到现在的10号位置了
您需要登录后才可以回帖 登录 | 成为会员

本版积分规则

QQ|手机版|小黑屋|网站帮助|职业IT人-IT人生活圈 ( 粤ICP备12053935号-1 )|网站地图
本站文章版权归原发布者及原出处所有。内容为作者个人观点,并不代表本站赞同其观点和对其真实性负责,本站只提供参考并不构成任何投资及应用建议。本站是信息平台,网站上部分文章为转载,并不用于任何商业目的,我们已经尽可能的对作者和来源进行了通告,但是能力有限或疏忽造成漏登,请及时联系我们,我们将根据著作权人的要求立即更正或者删除有关内容。

GMT+8, 2024-4-19 21:35 , Processed in 0.149530 second(s), 20 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表