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