---
title: 约瑟夫问题
date: 2019-02-10
updated: 2019-02-11
---
# 约瑟夫问题
[约瑟夫问题](https://en.wikipedia.org/wiki/Josephus_problem) 描述的是n 个士兵围一个环,从一个人开始计数,每次计数到k 杀掉一个人,再从新计数,问最后剩下士兵的编号(编号从0开始)

# 解法
有两种解法:
1. 使用队列模拟循环的环:O(k*n)
2. 使用数学推导

## 1.线性推导
1. 假如计数不是从1 开始,而是从k 开始,则第一个人最先被杀,最后剩余`n-1`个人, 最后被杀的是`1+f(n-1,k)`
2. 从k-1 开始,最后被杀的是`2+f(n-1,k) mod n`
3. 从1 开始,最后被杀的是`f(n,k) = k+f(n-1,k) mod n`

## 2.线性推导改良
我们想到,每一轮循环剩余`n'=n-n/k` 人,有余数`a=n mod k` 
1. 余数0,计数从1开始,最后被杀的是`f(n',k)`
1. 余数1,计数从2开始,最后被杀的是`[f(n',k)-1] mod n'`
1. 余数a,计数从a+1开始,最后被杀的是`[f(n',k)-a] mod n'`

另外,每次被杀的是k,2k,3k 新的士兵编号`x` 对应老的士兵编号为(从0开始): `old(x) = x + x/(k-1) = k/(k-1)*x`

        k = 7
        0,1,2,3,4,5,[]  6,7,8,..,11,  12...17
                         +6/6     +12/6

最终的推导式:

    f(n,k) = 
        old([f(n', k) -  (n mod k)] mod n')  //n' = n-n/k  if k<=n
        k+f(n-1,k) mod n                    // if k>n

## k=2 时的结果
维基百科通过归纳法证明了:
如果 `n=2^m+L` 且 `0 <= L<2^m` 则 `f(n)=2l+1`, 相当于n 的最高位补到最低位
  1. 笔记