王　胜

（犍为外国语实验学校，四川　犍为　614400）



模拟淘汰程序的设计方法研究
——以“猴子选大王”程序为例

王胜

（犍为外国语实验学校，四川犍为614400）

摘要：猴子选大王是一道经典的程序设计题，文章指出，可以通过不同的设计方法来实现：（1）模拟数组法。（2）模拟链表法。（3）stl l ist实现。（4）数学推导法。

关键词：猴子选大王；模拟；链表；stl l ist；数学推导

问题：n只猴子围成一个圈。从第一只猴子开始，从1开始依次报数，报到m的猴子离开。从这只离开猴子的下一只开始再从1开始报数，报到m的再离开。以此类推，直到最后剩下一只猴子为止。这只剩下的猴子就是大王。现在编写程序，输入n和m，输出大王的号码。

1　模拟静态数组法

学习了静态数组后，可以直接用静态数组来模拟淘汰的过程。

原理：设置n+1数组，初值为0，表示n只猴子都在圈子里，淘汰的猴子赋值为1。从数组1开始扫描，查看对应的值是否为0并计数，扫描到m个0后，把对应数组的值修改为1，表示淘汰。继续执行下一步的操作，直到里面只剩下一只猴子结束。最后从1开始扫描数组，找到一个为0的结束，该下标对应的猴子为大王。关键：0，1表示猴子是否在圈中，扫描的时候忽略不在的猴子，设置结束标记，能正常结束。

优点：理解容易，代码较易实现。

缺点：效率差，每次都要扫描全部的数据，还要判断该位置上是否有猴子。对于大一些的数据运行时间长。

2　模拟链表法

数组法在淘汰过程中要不断判断对应的值是否为0，即猴子是否在圈内，扫描判断效率低。学习链表后，我们可以用环形链表实现，每个节点代表一个猴子，扫描淘汰过程中直接删除该结点，避免了判断及重复扫描浪费时间。……