21xrx.com
2025-04-17 19:18:51 Thursday
文章检索 我的文章 写文章
C++实现约瑟夫环的循环链表
2023-07-08 04:27:41 深夜i     9     0
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++实现约瑟夫环的循环链表,可以通过创建循环链表、删除结点和遍历链表的操作来实现。这是一个有趣而又应用广泛的算法问题,也是数据结构中很好的练习题目。

  
  

评论区

请求出错了