当前位置：首页 > article >正文

约瑟夫问题

article 2024/11/18 5:43:59

约瑟夫问题是一个经典的数学问题，也是计算机科学中常见的数据结构和算法题目之一。它的形式是：有n个人站成一排，从第一个人开始报数，每次报到m的人出列，直到所有人都出列为止。请问，最后留下的人原来在什么位置上？

这个问题可以用多种方法解决，其中包括使用数组、单链表、双向循环链表以及数学公式法等。下面我们将分别介绍这些解题方法的思路和实现。

1. 使用数组

如果我们使用数组来模拟约瑟夫问题，可以先创建一个长度为n的数组，表示n个人的编号。然后我们可以使用循环遍历该数组，并根据报数的规则删除数组中的元素，相当于把这个数组看作一个环形队列。

具体来说，从第一个人开始报数，每报到m的人就将其从数组中删除（将其值设为-1），并把后面的元素依次向前移动一位。然后从下一个人重新开始报数，直到所有人都出列。最后留下的那个人的编号就是数组中唯一一个没有被删除的数。

时间复杂度为O(nm)，其中n表示人数，m表示报数到m的人出列。

#include <iostream>
#include <vector>
using namespace std;

vector<int> josephus(int n, int m) {
    vector<int> res;                    // 存储出列顺序
    vector<bool> used(n, false);        // 标记每个人是否已经出列
    int count = 0, index = -1;          // count表示当前报数的人数，index表示当前报数的人的下标
    while (res.size() < n) {            // 循环直到所有人都出列为止
        index++;                        // 按顺序遍历人数列表
        if (index >= n) index = 0;      // 处理超出范围的情况
        if (!used[index]) count++;      // 如果这个人还没有出列，则更新计数器
        if (count == m) {               // 如果这个人需要出列
            res.push_back(index + 1);   // 将他的编号存储在出列顺序列表中
            used[index] = true;         // 标记这个人已经出列
            count = 0;                  // 重置计数器
        }
    }
    return res;
}

int main() {
    int n, m;
    cin >> n >> m;
    auto res = josephus(n, m);
    for (auto x : res) {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}

2. 使用单链表

如果我们使用单链表来模拟约瑟夫问题，我们可以创建一个带有n个节点的单链表，并将它闭合成环形链表。然后，从头结点开始依次遍历链表，每次找到要出列的节点的前一个节点，输出并删除该节点。因为单链表只能从前往后遍历，所以每次找到要出列的节点的前一个节点需要顺时针遍历m-1个节点。

时间复杂度为O(nm)，与数组解法相同。

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int d): data(d), next(nullptr) {}
};

void josephus(int n, int m) {
    Node* head = new Node(1);
    Node* prev = head;
    for (int i = 2; i <= n; i++) {
        Node* curr = new Node(i);
        prev->next = curr;
        prev = curr;
    }
    prev->next = head;  // 将链表闭合成环
    
    Node* curr = head;
    while (n > 0) {
        // 找到要出列的节点的前一个节点
        for (int i = 0; i < m-1; i++) {
            curr = curr->next;
        }
        // 输出并删除节点
        cout << curr->next->data << " ";
        Node* temp = curr->next;
        curr->next = curr->next->next;
        delete temp;
        n--;
    }

    // 释放内存
    Node* temp = head;
    while (temp != nullptr) {
        Node* next = temp->next;
        delete temp;
        temp = next;
    }
}

int main() {
    josephus(5, 3);  // 输出: 3 1 5 2 4
    return 0;
}

3. 使用双向循环链表

如果我们使用双向循环链表来模拟约瑟夫问题，我们可以创建一个带有n个节点的双向循环链表，并将它闭合成环形链表。然后，从头结点开始依次遍历链表，每次找到要出列的节点的前一个节点，输出并删除该节点。因为双向循环链表可以从前往后遍历，也可以从后往前遍历，所以每次找到要出列的节点的前一个节点需要顺时针或逆时针遍历m-1个节点。

时间复杂度为O(nm)，与单链表解法相同。

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int d): data(d), prev(nullptr), next(nullptr) {}
};

void josephus(int n, int m) {
    Node* head = new Node(1);
    Node* prev = head;
    for (int i = 2; i <= n; i++) {
        Node* curr = new Node(i);
        prev->next = curr;
        curr->prev = prev;
        prev = curr;
    }
    prev->next = head;  // 将链表闭合成环
    head->prev = prev;
    
    Node* curr = head;
    while (n > 0) {
        // 找到要出列的节点的前一个节点
        for (int i = 0; i < m-1; i++) {
            curr = curr->next;
        }
        // 输出并删除节点
        cout << curr->next->data << " ";
        Node* temp = curr->next;
        curr->next = temp->next;
        temp->next->prev = curr;
        delete temp;
        n--;
    }

    // 释放内存
    Node* temp = head;
    do {
        Node* next = temp->next;
        delete temp;
        temp = next;
    } while (temp != head);
}

int main() {
    josephus(5, 3);  // 输出: 3 1 5 2 4
    return 0;
}