约瑟夫问题的两种解法

Question

要用c语言的方法解决，一种数组，一种循环链表

Answer 1

【约瑟夫问题】
编号为1，2，......，n的n个人按照顺时针方向围坐一圈。从第一个人开始顺时针方向自1开始报数，报到m时停止报数。报m 的人出列，从他在顺时针方向的下一个人开始重新报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。其中n,m由键盘输入。
【思路1】
利用数组存放n个人，数组下标等于他的编号，然后模拟报数过程，报到m时输出该位置的人编号，然后该位置的值清0，继续报数并判断是否为0，是0则跳过。直到n个人全部出列为止。
【参考程序】
Program yueshefu;
Var
a:array[1..100] of integer;
n,m,i,j,p:integer;
Begin
write('Input n,m:');
readln(n,m);
for i:=1 to n do
a[i]:=i;
p:=1; {p用于记录报数的位置}
for i:=1 to n do
begin
j:=0; {j用于记录报到的人数}
while j<m do
begin
if a[p]<>0 then j:=j+1;
if p=n then p:=1 else p:=p+1; {处理边界情况}
end;
if p<>1
then begin write(a[p-1],' ');a[p-1]:=0;end {处理边界情况}
else begin write(a[n],' ');a[n]:=0;end;
end;
end.

--------------------------------------------------------------------------------

【思路2】
建立一个循环数组，数组元素的每一个值保存的是它的下一个元素的编号，如果报到m后只要修改m前面的元素的编号为m后面的元素的编号，这样就跳过了第m个元素，如此下去直到n个人全部出列。
【参考程序】
Program yuesefu;
Var
a:array[1..100] of integer;
n,m,p,i,j:integer;
Begin
readln(n,m);
for i:=1 to n-1 do
a[i]:=i+1;
a[n]:=1;
p:=n;
for i:=1 to n do
begin
for j:=1 to m-1 do
p:=a[p];
write(a[p],' ');
a[p]:=a[a[p]];
end;
End.

参考资料：http://www.zjtg.cn/itjs/pascaljx/4_4.asp