C++中的“怪物圈”问题 |21xrx.com

C++中的“怪物圈”问题

2023-07-04 17:59:26 深夜i -- --

C++ 怪物圈循环算法变量

C++中的“怪物圈”问题是一个颇具挑战的编程难题，在许多编程竞赛中都被作为考题。本文将讲解这个问题的背景和解决方法。

“怪物圈”问题的背景

假设有N只怪物，它们排成一个圆圈，编号从1到N。每次从最左边的怪物开始数，数到M的那个怪物出圈，再从它的下一个怪物开始重新数M个，直到所有的怪物都出圈为止。求出怪物出圈的顺序。

解决方法

这个问题可以用C++来解决，下面简单介绍一种基于链表的解决方法。

1. 定义一个Monster结构体来表示每一个怪物，Monster结构体包含两个成员变量，一个是该怪物的编号，另一个是指向下一个怪物的指针。

struct Monster {

int num;

Monster* next;

};

2. 创建一个大小为N的循环链表，即每个怪物的next指针都指向下一个怪物，最后一个怪物的next指针又指向第一个怪物。

Monster* createCircle(int N) {

Monster* head = new Monster 1;

Monster* cur = head;

for (int i = 2; i <= N; i++) {

cur->next = new Monster nullptr ;

cur = cur->next;

}

cur->next = head;

return head;

}

3. 然后就是模拟游戏的过程了。我们用一个指针指向当前需要出圈的怪物，每次先将指针向后移动M-1个位置，然后将该怪物的next指针指向下下一个怪物，然后将指针指向下下一个怪物。重复这个过程，直到链表中只剩下一个怪物为止。

Monster* playGame(Monster* head, int M) {

Monster* cur = head;

while (cur->next != cur) {

for (int i = 1; i < M; i++)

cur = cur->next;

Monster* temp = cur->next;

cur->next = temp->next;

delete temp;

cur = cur->next;

}

return cur;

}

4. 最后，遍历链表得到出圈的顺序即可。

void printOrder(Monster* head) {

Monster* cur = head;

while (cur->next != head)

cout << cur->num << " ";

cur = cur->next;

cout << cur->num << endl;

}

完整代码如下：

#include

using namespace std;

struct Monster {

int num;

Monster* next;

};

Monster* createCircle(int N) {

Monster* head = new Monster nullptr ;

Monster* cur = head;

for (int i = 2; i <= N; i++) {

cur->next = new Monster i;

cur = cur->next;

}

cur->next = head;

return head;

}

Monster* playGame(Monster* head, int M) {

Monster* cur = head;

while (cur->next != cur) {

for (int i = 1; i < M; i++)

cur = cur->next;

Monster* temp = cur->next;

cur->next = temp->next;

delete temp;

cur = cur->next;

}

return cur;

}

void printOrder(Monster* head) {

Monster* cur = head;

while (cur->next != head)

cout << cur->num << " ";

cur = cur->next;

cout << cur->num << endl;

}

int main() {

int N, M;

cin >> N >> M;

Monster* head = createCircle(N);

Monster* last = playGame(head, M);

printOrder(last);

return 0;

}

总结

本文介绍了C++中的“怪物圈”问题的背景和解决方法，它是一道非常适合用于检验编程能力的难题。相信通过学习本文，读者对链表的使用和算法模拟有了更深入的理解。

上一篇: idea打包java可执行jar包

下一篇: C++ 字符指针数组的初始化方法

评论区

()

相似文章