约瑟夫问题是一个经典的数学问题,也是计算机科学中常见的数据结构和算法题目之一。它的形式是:有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;
}
4. 数学公式法
除了用数据结构来模拟约瑟夫问题,还有一种数学公式法可以解决这个问题。根据数学公式,最后留下来的那个人的编号是一个关于n和m的递推公式,我们可以直接用递推公式来计算出最后留下来的人的编号。
具体来说,最后留下来的那个人的编号可以表示成:
f(n, m) = (f(n-1, m) + m) % n
其中,f(n, m)表示n个人中最后留下来的人的编号,%表示取余操作。
我们可以使用递归或循环来计算递推公式。时间复杂度为O(n),与其他算法相比更加高效。
总结
约瑟夫问题是一个经典的数学问题,也是计算机科学中常见的数据结构和算法题目之一。文章来源:https://www.toymoban.com/news/detail-407976.html
我们可以使用数组、单链表、双向循环链表以及数学公式法等多种方法文章来源地址https://www.toymoban.com/news/detail-407976.html
到了这里,关于约瑟夫问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!