约瑟夫问题描述：

n个人围成一个圈，编号为0,1,2,..,n-1，设定一个常数k，然后从0号开始从1依次报数，报到k的那个人退出圈，后面一个人继续从1开始报数，依次类推，求最后剩下的人的编号

方法1：

模拟游戏过程的方法，将n个人串成一个循环链表，不停地去遍历链表，直到最后剩下一个结点。
优点：方法直观，写起来很容易
缺点：模拟了全部游戏过程，非常耗时，并且在n较大时占用较大的内存空间

方法2：

数学递推的方式。
假设当前k<=n，记n个人的时候最后剩下的人的编号是f(n) 。因为整个游戏过程存在大量重复的行为，我们自然可以想到将f(n)化成前面求出来的量。
当前圈是0,1,2,…,k-2,k-1,k,…,n-2,n-1
我们将第一个数到k的人去除，那么圈就变成
0,1,2,…,k-2,k,…n-2,n-1(其中k-1被去除)
因为此时整个圈的人数变成了n-1,我们就可以往f(n-1)上靠拢。
由于接下来开始报数的人是编号k的人。而f(n-1)表示的开始报数的是其编号0的人，那么我们这里就作一个映射
k,k+1,…….,n-2, n-1, 0, 1,……….,k-2 (将去掉一个人后的圈尾放到圈头)
0,1,……….,n-2-k,n-1-k,n-k,n-k+1,…..,n-2 (这是正常的得到f(n-1)的圈子)
观察上面一个映射我们可以发现f(n) = (f(n-1) + k) % n。意思就是说f(n-1)中的编号在加上k后就能转换成f(n)中的编号，并且如果>=n的话还要取模n使其在范围[0, n-1]之间。

由于递推或递归时都会遇到f(n)的n比k小的情况，所以我们要继续分析当n<k时上述递推式能不能继续满足。
假设当前k>n，那么第一次踢人时可能走完一圈，也有可能走完好几圈，所以第一个被踢的人编号是k mod n - 1。记：
p = k mod n (注意为了与前面一致，这里先不减1)
此时圈变成
0, 1, 2, …, p-2, p, …, n-2, n-1 (其中p-1被去除)
和前面一样，将圈尾调到圈头：
p, p+1, ……, n-2, n-1, 0, 1, …….., p-2 (这是f(n)的圈子去掉一个人后调整得到的)
0, 1, ………, n-2-p, n-1-p, n-p, n-p+1, …., n-2 (这是正常的得到f(n-1)的圈子)
观察可得到递推式f(n) = (f(n-1) + p) % n。即
f(n) = (f(n-1) + k%n) % n
因为最后都有个模n的操作，所以两个表达式是一样的，所以k和n不用比较大小关系，两个递推式都可以用。

方法2的优化1：

首先考虑对两个递推式的优化
f(n) = (f(n-1) + k) % n
f(n) = (f(n-1) + k%n) % n
为减少计算量，我们自然是要选用第一个表达式。
进一步考察模n这一操作的来源，发现在f(n-1)+k和f(n-1)+k%n后由于部分数据出现超过[0, n-1]这个闭区间，所以才需要模n使其保持在区间内。
我们分开来考虑，对f(n-1)+k，由于f(n-1)是在[0, n-2]这个区间内的，所以在+k后只需简单地判断其是否>=n即可，如果>=n就减上n，否则不需要进行操作。这样就避免了模n这个耗时的操作。
对k>n的情况，即表达式为f(n-1) + k%n时。虽然f(n-1)的确在区间内，但k比较大，导致相加后超过范围，由于不能确定k到底大到什么程度，所以这里不可避免地要对k取n的模，那么取n的模后加上f(n-1)还会超过n吗？会的。所以和上面一样进行一个判断，需要的话减n即可。
综合起来，就是

if k > n:
    k %= n
f(n) = f(n-1) + k
if f(n) >= n:
    f(n) -= n

由于递推的过程中始终是前项推后项，所以出于节省空间的考虑可以不用建立dp数组，直接保存上次得到的值不断循环更新即可。

方法2的优化2：

前述优化已经能较快的解决大部分问题了，但是当n非常非常大的时候还是会比较耗时。为了进一步加快速度，我们重新分析最开始考虑递推的过程。
我们将n个的圈按游戏规则踢掉一个后转化成了n-1的圈，从而得到递推表达式。那么我能在第一圈未结束时尽可能踢掉更多的人吗？
当k < n时，圈子一次性能踢掉n / k个人，此时圈子变成：
0, 1, 2, …, k-2, k, …, 2k-2, 2k, …, 3k-2, 3k, …, [n/k]k-2, [n/k]k, …, n-2, n-1 (其中k-1,2k-1,3k-1,…,[n/k]k-1都被踢掉了)
因为踢掉了n / k个人，所以f(n)应该由f(n - n / k)递推得到。那么此时如何去找他们之间的映射关系呢？
踢掉n/k个人后，接下来开始报数的是[n/k]k，并且从[n/k]k到n-1的人数是肯定小于k的。此时按前述的方法调整圈子：
[n/k]k, [n/k]k+1, …, n-2, n-1, 0,1, …, k-2, k, …, 2k-2, 2k, …, [n/k]k-2 (注意其中被踢掉的人)
0, 1, ….., n-2-[n/k]k, n-1-[n/k]k, n-[n/k]k…. (后面先不写，先分析前面的映射关系)
根据前面写出的一部分，我们可以得到递推关系 f(n) = (f(n-n/k) + [n/k]k) % n
需要注意两点：
1.递推是f(n)与f(n-n/k)之间
2.偏移量是[n/k]k
这里的偏移量很好理解，前面每踢一个人，后面偏移时都要多一个k,因为踢了[n/k]个人，所以要偏移[n/k]k。还有越过n-1时要模n控制区间。
继续往后分析，在调整后的圈子里0,1,2…并不是一直连续的，到了k-2,k时可以发现因为k-1被踢了，所以此时递推式中要补偿1，变成了f(n) = (f(n-n/k) + [n/k]k + 1) % n。再到了2k时则变成了f(n) = (f(n-n/k) + [n/k]k + 2) % n。依次类推可以得出f(n-n/k)的值即n-n/k个人时剩余的那个人的编号是非常影响f(n)的递推的，而且是分段性影响。
我们继续往后写一段映射关系，以期确定分段的端点。
0, 1, …, k-2, k, … (原n个人圈子踢人后调整后后面一段)
n-[n/k]k, n-[n/k]k+1, …, n-[n/k]k+k-2, n-[n/k]+k, … (n-n/k个人的圈子去掉前面一段)
由于原圈子在过0之后我们可以得到一个很明显的规律，即每过k个补偿就加1，所以
当f(n-n/k) >= n-[n/k]k时,
f(n)=(f(n-n/k) + [n/k]k + p) % n
其中p表示补偿量，p = (f(n-n/k) - (n - [n/k]k)) / k。先减去(n-[n/k]k)是为了将其编号映射到原圈子中,再通过除以k确定后面踢了几个人来得到补偿量
那么没有越过0呢，即映射到原圈子后编号在0的左边(不是指负数)，此时因为没有额外的踢人，所以补偿量一直为0，但是不能代上面的公式，因为此时p算出来为负数。即
当f(n-n/k) < n-[n/k]k 时
f(n)=f(n-n/k) + [n/k]k
并且此时因为映射后的编号没有过0，所以不需要模n

当k >= n时，因为遍历一次圈子无法踢人，要遍历两次或几次才能踢一个人，不满足优化2中提到的遍历一圈就踢几个人，所以此时按优化1处理即可。

综上可得如下伪代码：

if k > n:
    k %= n
    f(n) = f(n-1) + k
    if f(n) >= n:
        f(n) -= n
else if f(n-n/k) >= n-[n/k]k:
p = (f(n-n/k) - (n - [n/k]k)) / k
f(n)=(f(n-n/k) + [n/k]k + p) % n
else:
f(n)=f(n-n/k) + [n/k]k

以上是一次循环内的内容，循环的终点即是递推出n为止。由于这里与前面递推有所不同，并不是相邻项f(n)和f(n-1)之间的递推，而是相差了一个n/k。问题在于这个n/k会不断的变化，所以还是要设置dp数组保存前面的各项值，以供随时调用。

优先2中由于一次踢掉了尽可能多的人，所以n衰减的速度非常快，尤其是n较大且k较小的时候，运算次数远小于优化1.

模板(未优化)

单向

#include <bits/stdc++.h>
using namespace std;

int Next[1005];

int main(){
  int n,num,cnt=0,now=1;
  cin>>n>>num;
  for (int i=1;i<=n;++i)
    Next[i]=i+1;
  Next[n]=1;
  while (cnt<n){
    int co=1;
    while (co<num-1){
      co++;
      now=Next[now];
    }
    printf("%d ",Next[now]);
    Next[now]=Next[Next[now]];
    now=Next[now];
    cnt++;
  }
  return 0;
}

双向

#include <bits/stdc++.h>
using namespace std;

int Data[20005],Next[20005];

int main(){
  int num,cnt,n,m,now,pre,tmp;
  cin>>n>>m>>num;
  for (int i=1;i<=n;++i){
    Data[i]=i;
    Next[i]=i+1;
  }
  Next[n]=1;
  now=n;
  cnt=0;
  for (int i=1;i<=m;++i){
    cnt=0;
    while (cnt<num){
      cnt++;
      pre=now;
      now=Next[now];
    }
    printf("%d\n",Data[now]);
    tmp=now;
    Next[pre]=Next[now];
    while (cnt<2*num){
      cnt++;
      pre=now;
      now=Next[now];
    }
    Next[tmp]=Next[now];
    Next[now]=tmp;
    now=Next[now];
  }
  return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/30/