C++链表解决约瑟夫问题 |21xrx.com

C++链表解决约瑟夫问题

2023-06-27 10:31:23 深夜i -- --

C++ 链表约瑟夫问题解决数据结构

约瑟夫问题是一个古老而又有趣的问题，它是由罗马历史学家约瑟夫斯·弗拉维斯提出的。问题的内容是：有n个人站成一圈，从第一个人开始报数，报到m的人出圈，然后从出圈的下一个人重新开始报数，直到剩下最后一个人。这个问题可以用C++链表来解决。

首先，我们需要定义一个节点结构体，每个节点存储一个人的信息和指向下一个人的指针。


struct Node {
  int info;   // 存储人的编号
  Node* next;  // 指向下一个节点的指针
};

然后，我们需要创建一个n个节点的循环链表，每个节点存储一个人的信息。使用循环链表的好处是可以保持圆形结构，方便约瑟夫问题中每次跳过m个人。


Node* createList(int n) {
  Node* head = new Node();    //创建头节点
  Node* tail = head;       //尾节点指向头节点
  for (int i = 1; i <= n; i++) {
    Node* node = new Node();  //创建新节点
    node->info = i;      //存储人的编号
    tail->next = node;     //尾节点指向新节点
    tail = node;        //新节点成为尾节点
  }
  tail->next = head;       //尾节点指向头节点，形成循环链表
  return head;
}

创建完链表后，我们需要依次跳过m个人，将每个跳过的人节点从链表中删除，直到只剩下最后一个人。


void josephus(Node* head, int m) {
  Node* p = head;
  while (p->next != p) {  // 只剩最后一个人时结束循环
    for (int i = 1; i < m; i++)
      p = p->next;    // 跳过m-1个人
    
    Node* tmp = p->next;  // tmp指向第m个人
    p->next = tmp->next;  // 从链表中删除第m个人
    delete tmp;
    p = p->next;      // p指向下一个人，从下一个人开始再次报数
  }
  cout << "The winner is " << p->info << endl; //输出最后剩下的人的编号
}

最后，在主函数中调用上述三个函数即可。


int main() {
  int n = 10;  //总共有10个人
  int m = 3;   //每次报三下
  Node* head = createList(n);
  josephus(head, m);
  return 0;
}

输出结果为：

The winner is 4

这说明在10个人中，每次报三下，最后剩下的是第四个人。C++链表的实现让解决约瑟夫问题变得简单而容易理解。

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

下一篇: C++编程求n的阶乘之和

评论区

()

相似文章