[算法]Josephus相关问题。

Iambitious

传说是这样地:
在Jewish-Roman战争时期，著名的历史学家Josephus与一些犹太叛乱者被罗马的军队围困在一个山洞里，这些叛乱者宁为玉碎不为瓦全，决定以自杀作为最后的抗争手段，但是Josephus不想死阿，所以非常有数学天赋的他就提出了一个方案让自杀变得有"趣"些：让我们围成一个圆圈，然后从第一个人开始计数，每次杀掉第2个人，直到剩下最后一个，他再自杀。毫无察觉的众人轻率的答应了，而万万没有想到阴险的Josephus早就计算好了自己所要站在的位置，使得最后剩下的人就是他自己，当然至于后来Josephus去投降来保全自己的生命已经是另外的一个故事了，那么问题就是，对于n个人，最后剩下的是谁呢？
对于5个人的情况是这样地：
1,2,3,4,5
依此杀掉2,4,1,5
最后剩下的是3

soloforce

一直以为Josephus游戏是小孩子玩的，原来背后是个阴谋啊

Iambitious

传统的Josephus问题已经说完了，那么开始介绍几个相关的变形问题。
相关问题一般都与两个参数有关，一个是总人数n,一个是杀人步长m,所谓的杀人步长就是
从1开始计数，每次杀掉第m个人，然后从被杀掉的人的下一个人开始从1计数，再杀掉第m个人，依此直到剩下最后一个。
下面有3个相关的变形问题：
1.总共有n个人，杀人的步长为m,问编号为k的人，第几个被杀掉？
2.总共有n个人，杀人的步长为m,问第k个杀掉的人，编号是多少？
3.总共有n个人，问最小的使得前n/2次杀掉的都是[n/2] ..n中的人的杀人步长是多少？

Iambitious

Post by Lolita
一直以为Josephus游戏是小孩子玩的，原来背后是个阴谋啊

对阿， 所以这个问题一般的称谓是：臭名昭著的约瑟夫问题----the  notorious Josephus problem

Iambitious

第一问：存在O(n)的算法
第二问：存在O(n)的算法
第三问: 第三问存在....汗，一般只能解决n < 14的问题。(O(n^2 * n!)
具体题目参见:
1.topcoder SRM 315 div 2 hard problem
2.百度A*程序大赛，复赛第1题（稍微有些变化）
3.Poj1012

soloforce

偶然再看到这个帖子，又偶然看到第3题，恰好是上个月无意逛POJ看到的。当时想了大约1小时吧，提交上去就AC了， 我可不是ACM选手，纯粹是为了好玩。
贴个我求杀人步长的解法，不是很好，恰好满足 k<=14 的POJ要求。

POJ那题描述和Iambitious兄的略微不同，简单来说就是一共有2k个人，要求杀k次，且每次都杀死排在最后的k个坏人之一，求杀人步长m

2. /*
3. The Joseph's problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, . . ., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved.
5. Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy.
6. */
8. #include <stdio.h>
10. #define BOOL int
11. #define TRUE 1
12. #define FALSE 0
14. #define M_MAX 15000000
15. #define K_MAX 15
17. BOOL pick(int k, int m)
18. {
19.     int i;
20.     int currpos=0;
21.     int nextpos;
22.    
23.     for(i=0;i<k;i++)
24.     {
25.         nextpos=(currpos+(m-1)%(2*k-i)) % (2*k-i);
26.         if(nextpos<k) return FALSE;
27.         currpos=nextpos;
28.     }
29.    
30.     return TRUE;
31. }
34. int main()
35. {
36.     int k;
37.     int m;
38.    
39.     for(k=1;k<=K_MAX;k++)
40.     {
41.         for(m=k+1;m<M_MAX;m++)
42.         {
43.             if(pick(k,m)==TRUE) break;
44.         }
45.         
46.         if(m<M_MAX)
47.         {
48.             printf("k=%d m=%d\n",k,m);
49.         }
50.         else
51.         {
52.             printf("m not found while k=%d, with limitation m<=%d\n",k, M_MAX);
53.         }
54.     }
56. }

复制代码

soloforce

此外， Iambitious 兄说的第3题时间复杂度为 O(n^2 * n!)，不知道如何算出来的？我上面的算法时间复杂度最坏为 M_MAX*O(k)