使用链表完成约瑟夫问题,如何加代码使其可以随机一个小孩开始数,使用c++面对对象思想完成
时间: 2024-03-08 08:48:13 浏览: 128
好的,下面是使用 C++ 面向对象思想完成约瑟夫问题,并实现随机一个小孩开始数的示例代码。
```cpp
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
// 小孩节点类
class ChildNode {
public:
int data;
ChildNode* next;
ChildNode(int data = 0, ChildNode* next = NULL) {
this->data = data;
this->next = next;
}
};
// 约瑟夫问题类
class JosephusProblem {
private:
ChildNode* head; // 头节点指针
int count; // 小孩总数
public:
// 构造函数
JosephusProblem() {
head = NULL;
count = 0;
}
// 析构函数
~JosephusProblem() {
ChildNode* cur = head;
while (cur) {
ChildNode* tmp = cur;
cur = cur->next;
delete tmp;
}
head = NULL;
count = 0;
}
// 添加小孩节点
void add_child(int data) {
ChildNode* new_node = new ChildNode(data);
if (!head) {
head = new_node;
}
else {
ChildNode* cur = head;
while (cur->next) {
cur = cur->next;
}
cur->next = new_node;
}
count++;
}
// 随机一个小孩开始数数
void random_start() {
if (!head) {
cout << "链表为空,无法进行操作!" << endl;
return;
}
// 将链表中的所有小孩编号存储到数组中
int* child_list = new int[count];
ChildNode* cur = head;
for (int i = 0; i < count; i++) {
child_list[i] = cur->data;
cur = cur->next;
}
// 随机生成一个数组下标,将该小孩作为起始点开始数数
srand((unsigned)time(NULL));
int start_index = rand() % count;
// 开始数数
int current_index = start_index;
while (count > 1) {
// 找到要删除的小孩的前一个节点
int prev_index = (current_index - 1 + count) % count;
ChildNode* prev_node = head;
for (int i = 0; i < prev_index; i++) {
prev_node = prev_node->next;
}
// 删除该小孩节点
ChildNode* current_node = prev_node->next;
prev_node->next = current_node->next;
delete current_node;
count--;
current_index = (current_index + 2) % count;
}
// 输出最后留下的小孩编号
cout << "最后留下的小孩编号为:" << head->data << endl;
// 释放内存
delete[] child_list;
}
};
int main() {
// 创建约瑟夫问题对象
JosephusProblem jp;
// 添加小孩节点
jp.add_child(1);
jp.add_child(2);
jp.add_child(3);
jp.add_child(4);
jp.add_child(5);
jp.add_child(6);
// 随机一个小孩开始数数
jp.random_start();
return 0;
}
```
上述代码实现了使用 C++ 面向对象思想完成约瑟夫问题,并实现随机一个小孩开始数的功能。可以根据实际情况修改参数。
阅读全文