约瑟夫环（代码+公式推导）

题目描述个人的编号是 1 ~ 如果他们依编号按顺时针排成一个圆圈从编号是 1 的人开始顺时针报数。报数是从 1 报起当报到 的时候这个人就退出游戏圈。下一个人重新从 1 开始报数。求最后剩下的人的编号。传统的暴力写法时间复杂度On²数据超过5×10⁵就很难通过#includebits/stdc.h using namespace std; int main() { int n, k; cin n k; vectorint s; for(int i 1; i n; i) s.push_back(i); int idx 0; // 从第0个位置开始 while(s.size() ! 1) { // 计算要删除的位置(当前位置 k - 1) % 当前大小 idx (idx k - 1) % s.size(); s.erase(s.begin() idx); // 删除后idx 自动指向下一位置因为后面的元素前移了 } cout s[0] endl; return 0;因此将使用时间复杂度为O(n)的公式法来解决超时问题公式法代码先给代码#includebits/stdc.h using namespace std; int main() { int n,k; cin nk; int ans0; for(int i2;in;i) { ans(ansk)%i; } cout ans1; return 0; }公式法举例验证法推理假设n5k3编号调整为1~n以下出现的名词解释虚拟位置 每轮重新编排的临时座位号本轮虚拟编号0, 1, 2, ...每轮重新编排原始编号实际剩余的编号上轮虚拟位置该原始编号在上轮中的虚拟位置初始情况虚拟编号 0 1 2 3 4原始编号 1 2 3 4 5经过第一轮筛选编号3 OUT~从编号4继续重新开始数本轮虚拟编号 0 1 2 3原始编号 4 5 1 2上轮虚拟位置 3 4 0 1经过第二轮筛选编号1 OUT~从编号2继续重新开始数本轮虚拟编号 0 1 2原始编号 2 4 5上轮虚拟位置 3 0 1经过第三轮筛选编号5 OUT~从编号2继续重新开始数本轮虚拟编号 0 1原始编号 2 4上轮虚拟位置 0 1经过第四轮筛选编号2 OUT~本轮虚拟编号 0原始编号 4上轮虚拟位置 1结果幸存者原始编号:4由此例引至数学归纳法以便得到递推公式公式法数学归纳法推理命题设 f(n) 为 n 个人时幸存者的虚拟位置则 f(n)(f(n−1)k) mod n基础情况当n1时只有1人虚拟位置为0f(1)0 归纳假设假设对于 n−1 个人公式成立即已知 f(n−1) 。归纳步骤n人圈第一轮虚拟位置 0 1 2 ... k-1 k ... n-1原始编号 1 2 3 ... k k1 ... n↑淘汰淘汰位置0k-1 mod n k-1剩余n-1人重新安排虚拟位置从淘汰位置的下一个即位置k1开始作为新虚拟0新虚拟位置对应旧虚拟位置映射关系0k(k0) mod n1k1(k1) mod n.........x(kx) mod n(kx) mod n应用归纳假设n-1人时幸存者在新虚拟位置 f(n−1)映射回n人圈新虚拟位置 f(n−1)对应旧虚拟位置 旧位置 (kf(n−1)) mod nn人圈的幸存者位置 f(n) (f(n−1)k) mod n公式的应用int ans0;初始化答案f(1) 0表示1个人时幸存者在虚拟位置0for(int i2;in;i)循环变量i当前计算的人数从2人到n人{ans(ansk)%i;ans由于只需要用到前一个数据f(i-1)便无需用数组存储ans即公式中的f函数表示法fi的虚拟位置}cout ans1;输出幸存者的最终编号1~nf函数表示虚拟位置虚拟位置范围0~n-1比实际位置少1故1