需找新的美猴王——约瑟夫环 猴王问题

猴王问题:
某森林中有n只猴子在商量猴王选举问题,所有的猴子都想当猴王,
因此大家商量了一个选举办法如下:
所有的猴子围成一圈,先从第一个猴子开始报数,报数到13的猴子就出列。
紧接着的下一个猴子,又从1开始进行新的一轮报数,报数到12的猴子再出列;
依此重复下去,每一轮报数都比上一轮的报数少1,直到报数减为1之后,又从13开始报数。
直到原列中只剩下一个猴子为止,这个猴子就是猴王。

 

试设计一个程序求出猴王。

约瑟夫环……
很自然地能想到,用链表——环形链表 比较合适。
创建一个环形的链表,每次报数报到的猴子的节点被删除,C程序实现如下:

 

示例结果:
imageimage
约瑟夫环是一个很经典的问题,最初为——
已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。

 

而变形很多,又比如如下“狐狸抓兔子”问题:

围绕着山顶有10个洞。一只兔子和一只狐狸各住一个洞。 狐狸要吃兔子。
兔子对狐狸说:“你想吃掉我可以,但必须找到我。我就藏身于这十个洞中,
你从10号洞出发,先到1号洞找我,第二次隔一个洞找我,第三次隔两个洞找我,……,
以后依次类推,若能找到我,可饱餐一顿。”。
狐狸答应了,但是狐狸从早到晚进进出出了1000次,仍没找到兔子。
请编程求兔子究竟躲在哪个洞里。 

这个问题可以在泛化一点,使山洞的个数和进进出出的次数可变, 同样用环形链表求解,这次不必删除节点,只需在每个节点(山洞)中加一个标志变量,标志其是否被进出过,则C代码实现:

示例结果:
image

 

 

有关约瑟夫环,具体见 http://baike.baidu.com/view/717633.htm

 

 

 

Leave a Reply

Your email address will not be published.