海天科学工作室

        引子：

        很小的时候有一本书，叫趣味数学故事，猴子选大王就是其中的一个，没事的时候我会经常翻看那本书，一直到上大学。这些有趣的故事一直让我在思考，尽管如此，我还是不知道其中的答案是怎么回事。不过，这已经不重要了，重要的是它让我学会了思考。

       故事：

       10只猴子选大王，选举办法如下：从头到尾1,2,3报数，凡报3的退出，当报数到n时，继续从尾到头报数，凡报3的退出．．．如此类推，最后一个留在队中的为大王。有只聪明的小猴子站在一个很特殊的位置上，最后它当上了猴王。聪明的你，如果你是那只小猴子，你想想，应该站在什么位置上呢？ 
       编程：

       很多年没有用PASCAL来编写程序了，印象最深刻的是那年借调到一中去代李超兄的课，当时跟那些参加信息学竞赛的学生在一起，又刚好函授的时候学过数据结构，还想着考研、当黑客，所以对编程的兴趣很浓。当时诸如哈夫曼编码的之类的程序也都能编写出来，很有成就感。后面回到六中后，也没有带学生学编程，考研和当黑客都暂时没想了，这些东西也就全部荒废了，花了好多心血去学习数据结构，想想挺可惜的，都没用上。

      程序：（以下程序都用free pascal调试通过。）

program josephus01;  
var i,n,m,p,t,s:integer;
    a:array[1..150] of integer;   //总人数初设150,n不能超过150.
begin
    writeln('input n,m:');
    readln(n,m);
    for i:=1 to 150 do a[i]:=1;   //所有的人数先设为1,表示出圈.
    for i:=1 to n do a[i]:=0;     //1..n的人数,归0,初使化.
    t:=0; p:=0; s:=0;
    repeat
      while (t<m)  do    //t为计数器,当达到m的时候结束,打印出圈的号码.
        begin
          p:=p+1;       //p为数组元素指针,加1表示指针向后移动1次.
          if a[p]=0 then t:=t+1;  //如果a[p]=0,表示有在圈内,可计数.
          if p>n then p:=0;       //如果p>n,表示超过人数,重新开始数.
        end;
      write(p,'  ');   //打印出圈的号码
      a[p]:=1;         //将号码做标计,置1.
      s:=s+1;          //计算总人数,加1.
      t:=0;            //计数器置0,重新开始.
  until s=n;
readln;
end.

program josephus02;
var a:array[1..150] of integer;
    n,m,i,d,k,p:integer;
begin
  writeln('input n,m:');
  for i:=1 to 150 do a[i]:=1; //初使化数组元素为1,表示在圈内.
  readln(n,m);
  d:=0;k:=0;
  while true do
  begin
    for i:=1 to n do
    begin
      k:=k+a[i];
      if k<>m then continue;  //k不等于m时,继续跳到循环开始进行计数.
      write(i:4);
      p:=p+1;
      if p>9 then begin p:=0; writeln; end; //p变量是表示如果打印出10个就换行.
      a[i]:=0;             //a[i]为0表示出圈.
      k:=0;                //k表示重新计数.
      d:=d+1;
      if d=n then exit;
    end;
  end;
readln;
end.

program josephus03;    //链表实现,输入结点后,把该结点删除.
var a:array[1..150]of integer;
    i,j,n,m,p,s,t:integer;
begin
    writeln('input n,m:');
    readln(n,m);
    for i:=1 to n-1 do a[i]:=i+1;
    a[n]:=1;
    i:=0;j:=0; p:=0; t:=1; s:=0;
    repeat
      while p<m do
      begin
        j:=i;
        i:=t;
        t:=a[t];
        p:=p+1;
      end;
      write(i,'  ');
      a[j]:=a[i];
      p:=0;
      s:=s+1
    until s=n;
end.

program josephus04; //链表实现,同例3一样,少一个变量t.
var a:array[1..150]of integer;
    i,j,n,m,p,s:integer;
begin
    writeln('input n,m:');
    readln(n,m);
    for i:=1 to n-1 do a[i]:=i+1;
    a[n]:=1;
    i:=1;j:=0; p:=1; s:=0;
    repeat
      while p<m do
      begin
        j:=i;
        i:=a[i];
        p:=p+1;
      end;
      write(a[j],'  ');
      a[j]:=a[i];
      p:=0;
      s:=s+1
    until s=n;
    writeln('the king is:',i);
end.