用递归的算法解决约瑟夫问题，请进来聊聊.............看者也有分

Question

用递归的算法解决一个猴子选大王的问题
 有N只猴子，按顺时针数：1，2........一直数到M，为M号的猴子就退出，接着又数直到留下最后一只时就是大王
   请大家谈谈算法的思路，留下一些代码最好
   对高手是简单的，小弟不太懂递归，愚啊~！

Answer 1

这么麻烦，先看最普通的：
program aa(input,output);
var i,j,sum,x,m,n,k:integer;
    a:array[1..100] of integer;
begin
write('Input m,n,k:');
readln(m,n,k);
for i:=1 to 100 do a[i]:=0;
for i:=1 to m do a[i]:=i;
sum:=0;x:=n-1;
while sum<>m do
begin
  j:=0;
  repeat
    x:=x+1;
    while (a[x]=-1) or (a[x]=0) do
      if a[x]=0 then x:=1
        else x:=x+1;
    j:=j+1;
  until j=k;
  write(a[x],' ');
  a[x]:=-1;sum:=sum+1;
end;
writeln;
end.
再看用指针的program aa(input,output);
type point=^rec;
     rec=record
       num:integer;
       next:point;
       end;
var p,q,r:point;
    i,k,m,n:integer;
begin
readln(m,n,k);
new(q);p:=q;
for i:=1 to m-1 do
  begin
  q^.num:=i;
  new(q^.next);
  q:=q^.next;
  end;
q^.num:=n;
q^.next:=p;
for i:=1 to n-1 do p:=p^.next;
repeat
  for i:=1 to k-1 do
    begin
    r:=p;
    p:=p^.next;
    end;
  write(p^.num:4);
  q:=p^.next;
  dispose(p);
  p:=q;
  r^.next:=p;
until p=p^.next;
writeln(p^.num:4);
writeln;
end.程序是turbo pascal的

Answer 2

const
  N = 100;
  M = 10;
type
  TMonkey = record
    Prev, Next: Integer; // 分别表示前一猴子及后一猴子编号
  end;
  TMonkeys: array[0..N - 1] of TMonkey;
// 不喜欢用链表，所以用数组来模拟
procedure FindCandidate(var SomeMonkeys: TMonkeys);
var I: Integer;
begin
  // 初始化圈子
  for I := 0 to N - 1 do with SomeMonkeys[I] do
  begin
    Prev := I - 1;
    Next := I + 1;
  end;
  SomeMonkeys[0].Prev := N - 1;
  SomeMonkeys[N - 1].Next := 0;
  // 选举
  ShowMessage('The King is: ' + IntToStr(Sift(SomeMonkeys, 0)));
end;function Sift(var SomeMonkeys: TMonkeys; Who: Integer): Integer;
var I: Integer;
begin
  if SomeMonkeys[Who].Next = Who then
    Result := Who
  else
  begin
    // 从1数到M
    for I := 1 to M - 1 do Who:= SomeMonkeys[Who].Next; 
    // 接下来将M( Who )踢出圈中       
    SomeMonkeys[SomeMonkeys[Who].Prev].Next := SomeMonkeys[Who].Next;
    SomeMonkeys[SomeMonkeys[Who].Next].Prev := SomeMonkeys[Who].Prev;
    // 从M + 1开始继续点数
    Result := Sift(SomeMonkeys, SomeMonkeys[Who].Next);
  end;
end;

Answer 3

你看一那个点数的方法，不是直接从数组中找下一个猴子，而是从当前猴子的Next索引到下一猴子，因此被剔除的猴子决不会被数到。

Answer 4

举个例子：
  第一次数到12时（即编号为1)时停下来，
  此时修改SomeMonkeys[0].Next为2, 
  SomeMonkeys[2].Prev为0, 以后再数的话，1将不再参与计数，
  因为SomeMonkeys[SomeMonkeys[0].Next] = SomeMonkeys[2]。

Answer 5

十分感谢了 
 westfly(西翔) 
一下就给分

Answer 6

提一个建议，可以用集合更方便。
IF　A　IN　B　THEN......