约瑟夫环问题的解决

来源：百度知道 编辑：UC知道 时间：2024/06/17 15:31:00
14．约瑟夫环问题的求解
约瑟夫环（Joseph）问题的一种描述是：编号为1，2，…，n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。试通过类的设计求解约瑟夫环问题的出列顺序。具体的要求和说明如下：
（1）利用单向循环链表存储结构模拟此过程，按照出列的顺序输出个人的编号。
（2）m的初值为20；n＝7，7个人的密码依次为：3，1，7，2，4，8，4，首先m的值为6（正确的出列顺序应为：6，1，4，7，2，3，5）。
（3）程序运行后，首先要求用户指定初始报数的上限值，然后读取个人的密码。可设n<=30，此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。
（4）将上述功能改为在顺序结构上实现

只做过没有密码的，你修改一下吧...
public class josephusArray {
public static void main(String[] args) {
int n=8;
int m=3;
int[] a=new int[n];
for(int i=0;i<n;i++)
a[i]=i+1;
for(int i=0;i<n;i++)
System.out.print(a[i]+" ");
System.out.println(" ");

int k=1;
int i=-1;

while(true)
{
for(int j=0;j<m;)
{i=(i+1)%n;
if(a[i]!=0)
j++;
}

if(k==n) break;
System.out.println("No. "+a[i]+" out ");
a[i]=0;
k++;
}

System.out.print("No. "+a[i]+" boy won. ");
}

}

pascal 语言编的
刚编过
program yuesefu;
const
maxn=99;
var
code,pre,next:array[1..maxn]of word;
n,m,i,p,j:byte;
begin
repeat
read(n,m);
for i:=1 to n do begin
read(code[i]);
if i=1 then pre[i]:=n else pre[i]:=i-1;
if i=n t