2021-06-03 · 2분

BOJ 1158 — 约瑟夫问题

algorithmboj

这篇文章发布已超过两年，内容可能已过时。

BOJ #1158 题目：https://www.acmicpc.net/problem/1158

我们将活用在 [算法] - 队列（queue）学到的队列来解决问题！

问题解决

在计算机科学或数学中，约瑟夫问题（Josephus problem）或约瑟夫排列（Josephus permutation）定义如下。

设 n 和 k 为自然数，且 k < n。当 n 人围成一圈时，从任意一人开始依次计数，把第 k 个人从队伍中剔除。从剩下的 n-1 人中，再从下一个人开始依次计数，剔除第 k 个人。如此反复直到无人剩下。此时被从队伍中剔除的人的顺序称为 (n, k) 约瑟夫排列，求最后被剔除者的问题称为约瑟夫问题。

解题过程

使用了 C++ STL 提供的 queue。

当 (7, 3) 时

(1, 2, 3, 4, 5, 6, 7) ( )
(1, 2, 4, 5, 6, 7) ( 3 )
(1, 2, 4, 5, 7) ( 3 , 6 )
(1, 4, 5, 7) ( 3 , 6, 2 )
(1, 4, 5 ) ( 3, 6, 2, 7 )
(1, 4 ) ( 3, 6, 2, 7, 5 )
( 4 ) ( 3, 6, 2, 7, 5, 1 )
( ) ( 3, 6, 2, 7, 5, 1, 4 )

push 后 pop 直到 N-1 次，

到第 N 个时反复 front 后 pop 应该就能解决。

代码

#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

int main() {
    int N, K;
    queue<int> Queue;

    scanf("%d%d", &N, &K);
    fgetc(stdin);

    for (int i = 1; i <= N; i++)
    {
        Queue.push(i);
    }
    printf("<");
    for (int i = 0; i < N - 1; i++)
    {
        for (int j = 0; j < K - 1; j++)
        {
            Queue.push(Queue.front());
            Queue.pop();
        }

        printf("%d", Queue.front()); printf(", ");
        Queue.pop();
    }
    printf("%d", Queue.front());
    printf(">\n");
    return 0;
}