约瑟夫环问题

思路

约瑟夫环问题是：n个人围成一个环，编号从1到n(或者从0到n-1)，从1开始数(从几开始数不重要，重要的是数到第几个出队)，第k个人出队，然后从下一个人开始重新数，直到剩最后一个为赢家。

我们先把环展开，n个人时，队列为1 2 3 … n-1 n(n个人，队列1)，淘汰一个人后，下一轮应该从k+1开始报数，也就是k+1 k+1 … k-1(n-1个人，队列2)，对于这两个队列，胜者的编号应该是一样的，但在两个队列中的位置发生了变化，而对于下面这个队列1 2 3 … n-2 n-1(n-1个人，队列3)，因为和队列2都是n-1个人，所以显然胜者的位置是一样的，而我们的递归函数f(n,k)其实算的就是队列1(n个人)和队列3(n-1个人)，而当我们计算了队列3，需要转化为队列2之后，再返回给上层函数，这两者的关系就是(x+k)%n，n是当前人数，在迭代做法中应该是i。

注意最后一步，当队列编号从0开始时，可以直接(x+k)%n，当队伍编号从1开始时，应该是(x+k-1)%n+1。

代码

递归

int josephus(int n,int k){
    // 递归边界，注意编号是0或者1
    if(n==1){
        return 0;
    }
    // 注意如果编号从1开始，则是(josephus(n-1,k)+k-1)%n+1
    return (josephus(n-1,k)+k)%n;
}

非递归

int josephus2(int n,int k){
    int x=0;
    for(int i=2;i<=n;i++){
        x=(x+k)%i;
    }
    return x;
}