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

相似文章

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政