21xrx.com
2024-12-23 04:58:14 Monday
登录
文章检索 我的文章 写文章
C++循环链表实现约瑟夫环问题
2023-07-05 07:48:14 深夜i     --     --
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++ 代码实现，我们能够有效地处理约瑟夫环问题，也能更加深入地理解循环链表的原理和应用。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复