假定一个数m,从第k个小孩起,顺时针方向数,每数到第m个小孩时,该小孩离开。请分别使用c++数组和链表的方式完成全部代码。写出注释,并且可以支持用户自定义输入数据
时间: 2024-03-06 15:50:23 浏览: 18
使用C++数组的方式实现上述需求的代码如下:
```cpp
#include <iostream>
using namespace std;
const int MAX_N = 1000; // 最大小孩数量
int n, k, m;
int a[MAX_N + 1]; // 存储小孩编号的数组
int main() {
// 输入小孩数量n、起始编号k、每次数到m退出
cin >> n >> k >> m;
// 初始化小孩编号
for (int i = 1; i <= n; i++) {
a[i] = i;
}
int cur = k; // 当前小孩编号
for (int i = 0; i < n; i++) {
// 数m个小孩
for (int j = 1; j < m; j++) {
cur = (cur % n) + 1;
while (a[cur] == 0) { // 如果该编号的小孩已经退出,则跳过
cur = (cur % n) + 1;
}
}
// 输出退出的小孩编号
cout << a[cur] << " ";
a[cur] = 0; // 标记该小孩已经退出
}
return 0;
}
```
使用链表的方式实现上述需求的代码如下:
```cpp
#include <iostream>
using namespace std;
struct Node {
int val; // 存储小孩编号
Node *prev, *next; // 前驱和后继节点指针
Node(int _val): val(_val), prev(NULL), next(NULL) {}
};
int n, k, m;
int main() {
// 输入小孩数量n、起始编号k、每次数到m退出
cin >> n >> k >> m;
// 构建双向循环链表
Node *head = new Node(1), *tail = head;
for (int i = 2; i <= n; i++) {
tail->next = new Node(i);
tail->next->prev = tail;
tail = tail->next;
}
tail->next = head;
head->prev = tail;
Node *cur = head;
for (int i = 0; i < n; i++) {
// 数m个小孩
for (int j = 1; j < m; j++) {
cur = cur->next;
}
// 输出退出的小孩编号
cout << cur->val << " ";
cur->prev->next = cur->next;
cur->next->prev = cur->prev;
Node *tmp = cur;
cur = cur->next;
delete tmp; // 释放退出的小孩节点内存
}
return 0;
}
```
以上两份代码均支持用户自定义输入数据,输入格式为三个整数n、k、m,用空格隔开。例如,输入"10 3 5"表示有10个小孩,从第3个小孩开始数,每次数到第5个小孩退出。