21xrx.com
2024-12-23 01:16:41 Monday
登录
文章检索 我的文章 写文章
C++代码实现循环链表约瑟夫环问题
2023-06-26 20:29:24 深夜i     --     --
C++ 循环链表 约瑟夫环问题 实现 代码

约瑟夫环问题是一个古老而有趣的问题，原始的故事中，约瑟夫和他的40个朋友被罗马人包围了，他们决定宁愿死也不被罗马人俘虏，于是约瑟夫提议一个游戏：大家围成一个圆圈，从某个人开始，每数三个人就杀掉他，直到剩下一个人为止。 约瑟夫是个聪明的人，他很快想出了自己的生存之道，最后他成为了唯一的幸存者。

现在我们使用 C++ 代码来模拟这个经典的约瑟夫环问题。我们可以使用循环链表来实现这个问题，这里给出具体步骤：

1. 定义链表节点结构体

struct Node {

  int data;  // 节点数据

  Node* next; // 指向下一个节点的指针

};

2. 实现链表创建和初始化函数

Node* createList(int n) {

  // 创建 n 个链表节点

  Node *head = nullptr;

  Node *tail = nullptr;

  for (int i = 1; i <= n; i++) {

    Node *node = new Node();

    node->data = i;

    node->next = nullptr;

    if (head == nullptr)

      head = node;

      tail = node;

     else

      tail->next = node;

      tail = node;

  }

  // 链表头尾相连

  tail->next = head;

  return head;

}

3. 实现游戏函数

int game(Node* head, int m) {

  Node *p = head;

  int k = 1;

  while (p->next != p) {  // 只要链表不空

    if (k == m) {    // 数到 m 时杀掉当前节点

      p->data = p->next->data;

      Node* temp = p->next;

      p->next = p->next->next;

      delete temp;

      k = 1;

    } else {

      k++;

      p = p->next;

    }

  }

  return p->data; // 返回幸存者

}

4. 主函数调用

int main() {

  int n = 41;  // 总人数

  int m = 3;  // 数到第三个人杀掉

  Node* head = createList(n);  // 创建链表

  int survivor = game(head, m); // 开始游戏

  std::cout << "The survivor is No." << survivor << std::endl;

  return 0;

}

上述代码就是使用 C++ 实现循环链表的约瑟夫环问题的代码，通过上述的代码我们便可以非常直观的看到如何使用循环链表来解决这个问题。 通过这个问题，我们可以得到 C++ 对于链表的使用理解，并且深入了解到了约瑟夫环问题。

  
  

评论区

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