UC知道约瑟夫环(约瑟夫问题)
来源：百度知道 编辑：UC知道 时间：2024/05/10 07:29:40
问题如下
有N只猴子选大王，选举的办法是：排成一排，从头到尾报数，报到3的倍数（3、6、9、……）的退出去，直到全部报完，然后从尾到头开始逆向报数，同样报 3的倍数的退出。第三遍又是从头到尾进行，第四遍又从尾到头，直到最后余下两只，以排在后面（按报数的顺序）的那只为猴王。请编程序找出猴王的位置。（N 从键盘输入）
var a,b:array[0..100000] of longint;
c:array[0..100000] of boolean;
i,j,k,l,o,p,n,m:longint;
begin
read(n);m:=n;
for i:=1 to n-1 do a[i]:=i+1;a[n]:=0;
for i:=2 to n do b[i]:=i-1;b[1]:=0;
fillchar(c,sizeof(c),true);
i:=1;k:=1;
while n>2 do
begin
if i mod 2=1 then
begin
for j:=1 to m do if c[j] then break;
while j>0 do
begin
if k=2 then begin c[a[j]]:=false;a[j]:=a[a[j]];b[a[j]]:=j;dec(n);end;
if k<>2 then j:=a[j];inc(k);k:=k mod 3;
if a[j]=0 then break;
end;
end
else
begin
for j:=m downto 1 do if c[j] then break;
while j>0 do
begin
if k=2 then begin c[b[j]]:=false;b[j]:=b[b[j]];a[b[j]]:=j;dec(n);end;
if k<>2 then j:=b[j];inc(k);k:=k mod 3;
if b[j]=0 then break;
end;
end;
inc(