简介：今天小编分享一个猴子争大王的机试题，这题考察了对链表的理解和设计算法的能力。 猴子选大王问题是一个十分经典的算法问题，这个问题是这样的：一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺 ...
| 
今天小编分享一个猴子争大王的机试题，这题考察了对链表的理解和设计算法的能力。 猴子选大王问题是一个十分经典的算法问题，这个问题是这样的：一堆猴子都有编号，编号是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。
看完本文有收获？请转发分享给更多人!!!如果你有更好的答案，欢迎大家点赞，留言讨论，喜欢这篇文章可以分享给更多人，关注我每天更新分享有关程序员、科技、编程之类的文章！！！爱你们，，么么哒，，让我们一起愉快的玩耍把！！！ 本文仅代表作者个人观点，不代表巅云官方发声，对观点有疑义请先联系作者本人进行修改，若内容非法请联系平台管理员，邮箱2522407257@qq.com。更多相关资讯，请到巅云www.rzxsoft.cn学习互联网营销技术请到巅云建站www.rzxsoft.cn。 |
