c++约瑟夫问题怎么解

约瑟夫问题是经典的数学问题，描述如下：有n个人围成一圈，从第一个人开始报数，报到m的人出圈，然后从出圈的下一个人开始重新报数，仍然是报到m的人出圈，直到所有人都出圈为止。问最后剩下的人是谁？

解决这个问题的一个经典方法是使用递归。具体步骤如下：

1. 定义一个递归函数，传入当前围成圈的人数n和要出圈的第m个人的编号。

2. 在函数中，判断当前圈中是否只剩下一个人，如果是，则返回该人的编号。

3. 如果圈中不止一个人，则从第一个人开始报数，报到m的人出圈，剩下的人组成新的圈。

4. 递归调用函数，传入新的圈中的人数和要出圈的第m个人的编号。

5. 返回递归调用的结果，即最后剩下的人的编号。

下面是C语言实现的递归解法：

int Josephus(int n, int m) {
    if (n == 1) {
        return 1;
    } else {
        return (Josephus(n - 1, m) + m - 1) % n + 1;
    }
}

其中，n表示围成圈的人数，m表示要出圈的第m个人的编号。函数返回最后剩下的人的编号。

相关问题

c++约瑟夫问题循环链表图解

好的，关于C++循环链表的约瑟夫问题，我可以给你一个简单的图解。

首先，我们需要定义一个结构体来表示链表中的每个节点：

struct Node {
    int val;
    Node* next;
    Node(int x) : val(x), next(NULL) {}
};

然后，我们可以先创建一个循环链表，其中每个节点的值为1到n：

Node* createList(int n) {
    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;
    return head;
}

接下来，我们可以按照约瑟夫问题的规则，依次删除每个第m个节点，直到只剩下一个节点为止：

int josephus(int n, int m) {
    Node* head = createList(n);
    Node* cur = head;
    while (cur->next != cur) {
        for (int i = 1; i < m - 1; i++) {
            cur = cur->next;
        }
        Node* tmp = cur->next;
        cur->next = tmp->next;
        delete tmp;
        cur = cur->next;
    }
    int ans = cur->val;
    delete cur;
    return ans;
}

这样，我们就可以得到最后剩下的节点的值，即为约瑟夫问题的解。

c++约瑟夫问题用循环链表

约瑟夫问题是一个经典的数学问题，也可以用循环链表来解决。约瑟夫问题描述如下：有n个人围成一圈，从第一个人开始报数，报到m的人出列，然后从下一个人开始重新报数，直到最后剩下一个人。要求找出最后剩下的人的编号。

为了解决这个问题，可以使用循环链表来模拟人员围成一圈的情况。首先，创建一个包含n个结点的循环链表，每个结点表示一个人，并依次编号。然后，开始进行报数并出列的循环过程，直到只剩下一个结点。

具体的步骤如下：
1. 创建一个循环链表，结点个数为n，每个结点的编号依次为1到n。
2. 设定一个指针p指向链表的首元素。
3. 开始循环，直到链表中只剩下一个结点。
4. 在循环中，从p结点开始，依次报数直到m，并将报到m的结点从链表中删除。
5. 将指针p移动到下一个结点，继续报数和删除结点的循环过程。
6. 重复执行步骤4和步骤5，直到只剩下一个结点。
7. 输出最后剩下的结点的编号，即为约瑟夫问题的解。

通过使用循环链表来模拟约瑟夫问题，可以有效地解决这个问题，并能够快速找到最后剩下的人的编号。循环链表具有循环的特性，适用于这个问题的场景，可以简化计算过程，提高求解效率。