今天小编分享一个猴子争大王的机试题，这题考察了对链表的理解和设计算法的能力。
猴子选大王问题是一个十分经典的算法问题，这个问题是这样的：一堆猴子都有编号，编号是1，2，3 …m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
这个问题要解决起来并不难，但求解的方法很多；题目的变化形式也很多，而我们统称这类问题为约瑟夫问题。这类题目基本的描述为：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。下面我们先来分析一下解决这类问题的几个步骤。
（1）由于对于每个人只有死和活两种状态，因此可以用布朗型数组标记每个人的状态，可用true表示死，false表示活。
（2）开始时每个人都是活的，所以数组初值全部赋为false。
（3）模拟杀人过程，直到所有人都被杀死为止。
题目中N个人围成一圈，因而启发我们用一个循环的链来表示，可以使用数组结构来构成一个循环链表。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被杀死的标记，为1表示还存活。从第一个人开始对还存活的人进行计数，每数到M时，将结构中的标记改为0，表示该人已被杀死。这样循环计数直到有15个人被杀死为止。
但是，无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm），当n，m非常大（例如上百万，上千万）的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。
为了讨论方便，先把问题稍微改变一下，并不影响原意：
问题描述：n个人（编号0~(n-1）），从0开始报数，报到（m-1）的退出，剩下的人继续从0开始报数。求胜利者的编号。
核心代码：
public int King(int M, int N)
{
//总人数 M ，数到第 N 个排除。
int k=0;
for (int i = 2; i <= M; i++)
k = (k + N) % i;
return ++k;
}
分析：
在n（0、1、2、3、……、n-1）只猴子中,假定报数m的猴子被删除，
则第一只被删除的猴子编号为（m-1）%n,记为k，那么删除k之后剩下的n-1只猴子为0、1、……、k-1、k+1、……、n-1,并且下一次是从k+1开始计数。
相当于在剩下的序列种，k+1排在最前面，从而形成k+1、……、n-1、0、1、……、k-1。
接下来将剩下的这n-1个数字的序列k+1、……、n-1、0、1、……、k-1映射形成一个从0到n-2的序列0、1、2、……、n-2。
把映射定义为p，则p(x)=(x-k-1)%n。
逆过来0、1、2、……、n-2映射为k+1、……、n-1、0、1、……、k-1，时则p’(x)=(x+k+1)%n，而k=(m-1)%n,故p’(x)=(x+m)%n。
最后一只猴子的编号为0，故x=0,n=1。例如当m=3时，p’(0)=(0+3)%1=3,表示最后一只猴大王在倒数第二轮（编号也是从0开始）中编号为3。
看完本文有收获？请转发分享给更多人!!!如果你有更好的答案，欢迎大家点赞，留言讨论，喜欢这篇文章可以分享给更多人，关注我每天更新分享有关程序员、科技、编程之类的文章！！！爱你们，，么么哒，，让我们一起愉快的玩耍把！！！
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/5107.html
