Josephus problem

N人围成一圈，每轮报到k倍数的离开，从下一个人开始重新从1开始报数. 求解最后一个剩下的人最初是第几个。

• wiki
• MathWorld

问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。

我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2
并且从k开始报0。

现在我们把他们的编号做一下转换：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1

变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x‘=(x+k)%n

如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：

令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]

递推公式
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)

有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1

由于是逐级递推，不需要保存每个f[i]，程序也是异常简单：

DP solution: O(N)

d[1] = 0
d[i] = ( d[i-1] + k ) % i 

不光最后一个剩下的符合这个规律，倒数第j个离开的也是这样

d[i，j] = ( d[i-1, j] + k ) % i 

 K = 3, $->  second-last; * -> last
---------------------------------
0 1 2
$ *

0 1 2 3
*     $

0 1 2 3 4
 $   *

0 1 2 3 4 5
*       $

 

int d[151];

// standard joseph problem solution
// person id is 0-based
int joseph(int n, int m) {
  d[1] = 0;
  for(int i = 2; i <= n; ++i)
    d[i] = (d[i-1] + m)% i;
  return d[n];
}

// another joseph problem extension
// always kill the 1st guy, then every m-th guy
// idea: after the 1st guy is killed,
//       the problem (n,m) is changed to a (n-1, m)
//       standard joseph problem
//       the solution's id + 1 is the old problem's id
int joseph1(int n, int m) {
  int last = joseph(n-1, m);
  return last + 1;
}

// the solve subrutine is used to find the exact m
// to make the 2nd person the last guy to kill
// in extension joseph1
int solve(int n) {
  int m = 2;
  while(true) {
    // 0-based index
    int last = joseph1(n, m);
    if (last == 1)
      break;
    ++ m;
  }
  return m;
}

Problem:

• UVa 130 Roman Roulette
  
  
• UVa 133 The Dole Queue
  
  
  
  
  
  • just simulate the process
    
    
  • using array to keep the status (i tried to use bit vector, but it seems no good for this problem)

            int live = n;  // live person #
           int p1 = 1, p2 = n; // current position
           while(live > 0) {
               int cnt = 0;
               while(true) { //skip k persons
                   if(a[p1]) ++cnt;
                   if(cnt == k) break;
                   reg(--p2,n)
               }
               cnt = 0;
               while(true) { // skip m persons
                   if(a[p2]) ++cnt;
                   if(cnt == m) break;
                   reg(--p2,n)
               }
    
               if(p1 == p2) {
                   printf("%3d", a[p1]);
                   a[p1] = 0; live--;
               } else {
                   printf("%3d%3d", a[p1],a[p2]);
                   a[p1]=a[p2]=0;
                   live -= 2;
               }
               reg(++p1,n);
               reg(--p2,n);
    
               if(live) printf(",");
           }

  
  
  
• UVa 305 Joseph
  
  
  
  
  
  • We have to check :
    
    
  • a1 = (m-1) % n > k
    
    
  • a2 = (a1 + m-1) % (n-1) > k
    
    
  • a3 = (a2 + m-1) % (n-2) > k
    
    
  • ...
    
    
  • ak = (a(k-1) + m-1) % (n-k+1) > k

    int gen_data(int k) {
       int n = k << 1; // total number n = 2k
       int m = k+1;    // starting to check at k+1
       bool found = false;
       while(!found){
           int ap = 0; // previous (a_i-1)
       int an;     // current  (a_i)
           for(int i = 0; i < k; ++i) {
               an = (ap+m-1) % (n-i);
               ap = an;
               if(an < k)
                   break;
               if(i == k-1 && an >= k)
                   found = true;
           }
           if(!found) ++m;
       }
       return m;
    }

  
  
  
• UVa 402 M*A*S*H