C++程序实现猴子选大王问题 |21xrx.com

C++程序实现猴子选大王问题

2023-06-23 18:52:51 深夜i 19 0

C++ 猴子大王问题解决算法

猴子选大王问题是一道经典的算法问题，通常用于教学和练习编程技能。本文将介绍如何用C++语言实现这个问题。

猴子选大王问题的背景是这样的：有N只猴子围成一圈，每只猴子都有一个编号。从第一只猴子开始，数到第M只猴子，将它打败，然后从下一只猴子开始重复这个过程，直到只剩下一只猴子为止。问最后留下的是哪只猴子？

首先，我们需要创建一个猴子类，每个猴子都有一个编号和指向下一个猴子的指针。创建这个类的C++代码如下：

class Monkey {
public:
  int id;
  Monkey* next;
  Monkey(int i)
    id = i;
    next = nullptr;
  
};

然后，我们需要构造一个猴子链表，它以N个猴子为节点，每个猴子的编号递增。创建这个链表的C++代码如下：

Monkey* createMonkeyChain(int n) {
  Monkey* head = new Monkey(1);
  Monkey* p = head;
  for (int i = 2; i <= n; i++) {
    Monkey* m = new Monkey(i);
    p->next = m;
    p = m;
  }
  p->next = head;
  return head;
}

接着，我们需要编写一个函数，用于找到被打败的猴子。这个函数需要根据参数M计算出第M只猴子是谁，然后把它从链表中删除。创建这个函数的C++代码如下：

Monkey* eliminateMonkey(Monkey* head, int m) {
  Monkey* p = head;
  while (p->next != p) {
    for (int i = 1; i < m - 1; i++)
      p = p->next;
    
    Monkey* q = p->next;
    p->next = q->next;
    delete q;
    p = p->next;
  }
  return p;
}

最后，我们调用这个函数，输出最后留下的猴子的编号。在主函数中调用这些函数的C++代码如下：

int main() {
  int N = 10; // 猴子数量
  int M = 3; // 每M个猴子打败一只
  Monkey* head = createMonkeyChain(N);
  Monkey* result = eliminateMonkey(head, M);
  cout << result->id << endl;
  return 0;
}

运行这段代码，就可以得到答案是4。

总结一下，以上就是使用C++语言实现猴子选大王问题的方法。这个问题涉及到链表和逻辑运算等多种基础知识，是一个不错的算法练习题。通过编写这个程序，可以更好地理解指针操作和链表数据结构的应用。

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

下一篇: C++中的队列实现

评论区

相似文章