基本约瑟夫环问题详解

本人水平有限,题解不到为处,请多多谅解

本蒟蒻谢谢大家观看

推荐博客传送门

首先让我们来看一下这一段:

n-2 ---> (k1+n-2)%n1(n1为当前序列的总人数,因为是循环的序列,k1+n-1可能大于总人数)

至关重要,比如:我们已经知道当前的最后一个出列的位置为f ,设下一次最后一个出列的位置为ans

ans=(f+m)%n;

相当于是在f后往后再报m个数即可。

递推公式:

这样的话,我们就得到了递推公式,由于编号是从0开始的,那么我们可以令

f[1] = 0;          //当一个人的时候,出队人员编号为0

f[n] = (f[n-1] + m)%n     //m表示每次数到该数的人出列,n表示当前序列的总人数

 

原文地址:https://www.cnblogs.com/nlyzl/p/11798488.html