约瑟夫环问题
作者:
若雨
,
2023-11-22 17:17:11
,
所有人可见
,
阅读 113
/*
循环队列模拟,复杂度O(N*K):
hh与tt最大边界值分别为总的元素出队与入队次数;通过 hh%N 与 (tt-1)%N 获取队列首尾元素在队列中的下标;
判空条件 tt == hh,判满条件 tt - hh == N;其中N为循环队列容量;
*/
#include <cstdio>
const int N = 1000010;
int q[N], hh = 0, tt = 0;
inline void enQueue(int val) { if (tt - hh != N) q[tt % N] = val, tt ++; }
// 快读模板;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return f * x;
}
int main() {
int n, m, t = 0; n = read(), m = read();
for (int i = 1; i <= n; i ++) enQueue(i);
while (tt - hh != 1) {
t ++;
if (t == m) { hh ++; t = 0; }
else { enQueue(q[hh % N]); hh ++; }
}
printf("%d", q[hh]);
return 0;
}
约瑟夫环问题如何快速获取最后剩余人的编号[1, N];
考虑一般的情况:状态为N个人,此时删除报道M的人的编号,删掉之后,此时被删人的下一个人的编号从1开始,
编号循环递增直到被删者的上一个编号,类似于每个人的编号向前移动M,若从终止情况递推来看的话,每次状态
转移编号向后移动M,但为了不越界,对N取余,最后由于编号从1开始,而取余时是考虑0下标开始的情况,因此最后加一;
终止情况:最后只剩下一个人,此时下标为0;
因此递推公式为:
F(1) = 0;
F(n) = (F(n−1) + m) mod n;
其中F(k)表示剩下k个人 m次一出 最终胜利者在当前状态下的下标;
代码:
int p = 0;
for (int i = 2; i <= n; i ++)
p = (p + m) % i;
return p + 1;