约瑟夫 (josephus) 问题c++

约瑟夫问题是一个经典的问题，描述如下：已知 n 个人（以编号 1，2，3…n 分别表示）围坐在一张圆桌周围。从编号为 k 的人开始报数，数到 m 的那个人出列；他的下一个人又从 1 开始报数，数到 m 的那个人又出列；依此规律重复下去，直到圆桌周围的人只剩下一个。现在要求你编写一个程序，输出最后剩下的人的编号。

以下是使用 C++ 语言实现的代码：

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

int josephus(int n, int k, int m) {
    int s = 0;
    for (int i = 2; i <= n; i++) {
        s = (s + m) % i;
    }
    return (s + k) % n + 1;
}

int main() {
    int n, k, m;
    cin >> n >> k >> m;
    cout << josephus(n, k, m) << endl;
    return 0;
}

在上面的代码中，josephus 函数接受三个参数，分别是人数 n，起始编号 k 和报数上限 m，返回最后剩下的人的编号。具体实现是使用了一个循环，每次将 s 增加 m，然后对 i 取模，最后返回 (s + k) % n + 1 即可。

以上是一个简单的解法，时间复杂度为 O(n)。如果需要更高效的解法，可以使用数学公式进行计算，时间复杂度可以降为 O(1)。

相关问题

约瑟夫环绕问题c++

约瑟夫环绕问题是一个经典的数学问题，也被称为约瑟夫问题或约瑟夫斯置换。问题的描述如下：
有n个人围成一圈排队，从第一个人开始报数，数到 m 的人出列，然后从出列的下一个人开始重新报数，直到所有人都出列。要求找出出列的顺序。

解决这个问题的一种常见方法是使用递归。首先，定义一个递归函数，命名为josephus(n,m)，表示n个人中按照m进行报数的出列顺序。递归函数的返回是一个列表，表示出列的顺序。

递归函数的基本情况是，当只有一个人时，该人是最后出列的，直接返回一个只包含该人的列表。

当有多个人时，我们需要找到第一个出列的人。根据问题的要求，第一个出列的人是从出列的下一个人开始重新报数。所以，我们可以递归调用josephus(n-1,m)，表示去掉第一个人后剩下的n-1个人按照m进行报数的出列顺序。然后，将返回的列表中第一个人加入到结果列表中。

最后返回结果列表，表示n个人按照m进行报数的出列顺序。

下面是一个用Python实现的例子：

def josephus(n,m):
if n == 1:
return [1]
else:
remaining = josephus(n-1,m)
idx = (m-1) % len(remaining)
return remaining[:idx] + [n] + remaining[idx+1:]

n = 10
m = 3
result = josephus(n,m)
print(result)

使用上述代码，当有10个人时，按照每次报数3个人出列的规则，最后出列的顺序为[4, 1, 8, 6, 2, 10, 3, 7, 5, 9]。

约瑟夫问题c++

约瑟夫问题是一个经典的问题，可以使用循环链表来解决。以下是使用 C++ 语言实现的代码：

#include <iostream>
using namespace std;

// 定义循环链表节点结构体
struct Node {
    int val;
    Node *next;
    Node(int x) : val(x), next(NULL) {}
};

// 定义函数实现约瑟夫问题
int josephus(int n, int m) {
    // 构造循环链表
    Node *head = new Node(1);
    Node *cur = head;
    for (int i = 2; i <= n; i++) {
        cur->next = new Node(i);
        cur = cur->next;
    }
    cur->next = head;

    // 开始报数
    Node *prev = NULL;
    while (cur->next != cur) {
        for (int i = 0; i < m-1; i++) {
            prev = cur;
            cur = cur->next;
        }
        prev->next = cur->next;
        delete cur;
        cur = prev->next;
    }
    int winner = cur->val;
    delete cur;
    return winner;
}

int main() {
    int n = 5, m = 3;
    int winner = josephus(n, m);
    cout << "The winner is: " << winner << endl;
    return 0;
}

在上述代码中，我们首先构造了一个循环链表，然后从链表头开始报数，每数到第 $m$ 个节点就将该节点删除，直到只剩下一个节点为止。最后返回剩下的节点的值即可。

注意，在链表中删除一个节点时，需要先保存该节点的前一个节点，以便在删除后将前一个节点与后一个节点相连。