已经不止一次在面试中遇到过这种问题了。

n个人(编号为1~n)组成一个环,从第一个人以1开始报数,报的数为k的整数倍的那个人将从环中移除。问最后一个被移除人的编号。

比如,n=5, k = 3时,最后一个被移除人的编号为4.


最简单的实现方式:用链表进行模拟操作。这种方式复杂度太高。

以下介绍的是数学方式:O(n).

将报的数为k的整数倍的人移除,等价于,将某个人移除之后,后面的人再重新以1开始报,报到k的人移除,以此循环下去。

为了方便,设这n个人的编号以0开始。取f(n)表示,由n个人组成的约瑟夫环问题,最后一个被移除人的编号。

在第一轮操作中,将编号为(k-1)的人移除,之后的所有人再做一个编号映射,即:

  0      1    ...  k-2    k-1     k    k+1   ...    n
  |      |          |      |      |     |           |
n-k+1  n-k+2  ...  n-1  deleted   0     1    ...   n-k

这样的话,考虑是否能将f(n)的问题,转换为f(n-1)的问题?

f(n)和f(n-1)最后移除的人在上图中对应的是同一个位置,只是两者对应的编号不一样。

假设f(n-1)=x,那么根据上述映射关系,则f(n)=(x+k)%n.

考虑只有一个人时,最后一个被移除的人显然是环中唯一的这个人,即f(1)=0.

那么,转换关系为:

(1) f(1) = 0;

(2) f(i) = [f(i-1) + k] % i.

代码:

int main(){
    int n =  5, k = 3;
    int rst = 0;    // f(1) = 0
    for(int i = 2; i <= n; i++){
        rst = (rst + k) % i;
    }
    cout << rst << endl;
}

若编号从1开始,则返回rst+1.