C++实现约瑟夫环的循环链表 |21xrx.com

C++实现约瑟夫环的循环链表

2023-07-08 04:27:41 深夜i -- --

C++ 约瑟夫环循环链表

约瑟夫环，是一个古老的数学问题，最早是由一位学者约瑟夫提出的。问题是这样的：有n个人站在一个圆圈里，每到第m个人就将此人杀死，直到只剩下一个人。那么，如何选定初始位置，才能保证最后剩下的人是我们想要的那个人？

在计算机科学中，我们可以使用循环链表来实现约瑟夫环。对于一个有n个结点的循环链表，我们可以选择从任意一个结点开始遍历这个链表，每次找到第m个结点，并将其删除。这个过程一直持续到只剩下一个结点为止。

以下是C++代码实现约瑟夫环的循环链表：


#include <iostream>
using namespace std;
//定义一个结构体表示链表中的结点
struct Node{
  int data;
  Node *next;
};
//创建链表
Node *createList(int n){
  Node *head = new Node NULL;
  Node *pre = head;
  for(int i=2; i<=n; i++){
    Node *curr = new Nodei;
    pre->next = curr;
    pre = curr;
  }
  pre->next = head;
  return head;
}
//删除结点，并返回下一个结点
Node *deleteNode(Node *curr){
  Node *temp = curr->next;
  curr->next = curr->next->next;
  delete temp;
  return curr->next;
}
//主函数：实现约瑟夫环
void josephus(int n, int m){
  Node *head = createList(n);
  Node *curr = head;
  while(curr->next != curr){
    for(int i=1; i<m; i++)
      curr = curr->next;
    
    curr = deleteNode(curr);
  }
  cout << "The last remaining person is: " << curr->data;
}
//测试
int main(){
  int n = 10, m = 3;
  josephus(n, m);
  return 0;
}

以上代码中，我们首先定义了一个结构体Node来表示链表中的结点，其中data表示结点的值，next指向下一个结点。在主函数中，我们调用createList函数来创建有n个结点的循环链表，并根据约瑟夫环的规则，每次找到第m个结点，并删除该节点。最后，当链表只剩下一个结点时，输出这个结点的值即可。

总结：使用C++实现约瑟夫环的循环链表，可以通过创建循环链表、删除结点和遍历链表的操作来实现。这是一个有趣而又应用广泛的算法问题，也是数据结构中很好的练习题目。

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

下一篇: C++代码：求x的y次方

评论区

()

相似文章