21xrx.com
2025-07-09 03:58:41 Wednesday
文章检索 我的文章 写文章
C++循环链表实现约瑟夫环问题
2023-07-05 07:48:14 深夜i     21     0
C++循环链表 约瑟夫环问题 实现

约瑟夫环问题是经典的计算机科学问题,其背景是约瑟夫和他的40个士兵在罗马军队的包围中被困。他们决定宁愿自杀也不被俘虏,于是约瑟夫提出了如下计划:他们围成一个圆圈,从某个人开始,依次报数,每报数到第M个人就将其杀死,然后从下一个人开始重新报数,直到剩余一个人为止。问题是,给定圆圈总长度n,起始报数位置p和每次报数到第M个人时的杀死操作,求在圆圈中谁会成为最后一个人。

为了解决这个问题,我们可以使用循环链表来模拟这个过程。循环链表是一种特殊的链表,其中最后一个节点连接到第一个节点,形成一个环。可以使用 C++ 语言来实现循环链表,以下是一个简单的代码示例:

#include <iostream>
using namespace std;
struct Node {
  int val;
  Node* next;
  Node(int x) : val(x), next(NULL) {}
};
Node* buildCircularList(int n) {
  Node* head = new Node(1);
  Node* prev = head;
  for (int i = 2; i <= n; i++) {
    Node* cur = new Node(i);
    prev->next = cur;
    prev = cur;
  }
  prev->next = head;
  return head;
}
Node* josephusCircle(Node* head, int m) {
  Node* prev = head;
  while (prev->next != head)
    prev = prev->next;
  
  Node* cur = head;
  int count = 1;
  while (cur->next != cur) {
    if (count == m)
      prev->next = cur->next;
      count = 1;
     else {
      prev = cur;
      count++;
    }
    cur = prev->next;
  }
  return cur;
}
int main() {
  int n = 7, m = 3;
  Node* head = buildCircularList(n);
  Node* last = josephusCircle(head, m);
  cout << last->val << endl;
  return 0;
}

首先,我们定义一个节点结构体 Node,其中包含一个整数值 val 和一个指向下一个节点的指针 next。在 buildCircularList 函数中,我们按照顺序创建 n 个节点,并将最后一个节点的 next 指向头节点,形成循环链表,并返回头节点。

在 josephusCircle 函数中,我们先找到最后一个节点 prev,然后从第一个节点 cur 开始遍历链表,如果计数器 count 等于 m,就将 prev 的 next 指向 cur 的下一个节点,即删除当前节点;否则,就将 prev 移动到 cur 的位置,并将计数器加 1,继续往后遍历。当链表中只剩一个节点时,就找到了结果。

最后,在主函数中,我们测试了一个有 7 个节点、每次报数到第 3 个人的约瑟夫环问题,输出最后一个节点的值,得到 4,符合预期。

通过以上的 C++ 代码实现,我们能够有效地处理约瑟夫环问题,也能更加深入地理解循环链表的原理和应用。

  
  

评论区