使用C++循环链表实现约瑟夫环问题 |21xrx.com

使用C++循环链表实现约瑟夫环问题

2023-06-24 02:20:25 深夜i -- --

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

约瑟夫环问题是一个经典的问题，在计算机科学中具有重要的地位。使用C++循环链表来实现这个问题可以更有效地解决问题。

约瑟夫环问题的描述是：有n个人围成一圈，从某个人开始顺时针报数，报到第m个人出圈，接着从下一个人开始重新报数，报到第m个人同样出圈，直到所有人全部出圈为止。最后出圈的人的编号是多少？

使用C++循环链表实现约瑟夫环问题的步骤如下：

1. 定义一个结构体表示每个人的信息，包括编号和指向下一个人的指针。

2. 创建一个循环链表，将每个人的信息存储在链表中。

3. 从某个人开始，按照顺时针方向报数，每次报数到第m个人时，将这个人从链表中移除。

4. 重新开始报数，直到链表中只剩下一个人。

5. 输出最后出圈的人的编号。

以下是使用C++循环链表实现约瑟夫环问题的代码示例：


#include<iostream>
using namespace std;
//定义每个人的信息结构体
struct Person{
  int number; //编号
  Person *next; //指向下一个人的指针
};
//创建循环链表
Person* CreateList(int n){
  Person *head, *p, *q;
  head = new Person;
  head->number = 1;
  q = head;
  for(int i=2; i<=n; i++)
    p = new Person;
    p->number = i;
    q->next = p;
    q = p;
  
  q->next = head; //将最后一个人的指针指向第一个人，形成循环链表
  return head;
}
//约瑟夫环问题的求解
void Josephus(Person *head, int m){
  Person *p = head, *q = NULL;
  int i = 0;
  while(p->next != p){ //当链表中只剩下一个人时，停止运行
    i++;
    if(i == m)就将这个人移除
      q->next = p->next;
      cout<<p->number<<" ";
      delete p;
      p = q->next;
      i = 0;
    
    else
      q = p;
      p = p->next;
    
  }
  cout<<p->number<<" "; //输出最后一个人的编号
  delete p;
}
int main(){
  int n, m;
  cout<<"请输入总人数n和报数m："<<endl;
  cin>>n>>m;
  Person *head = CreateList(n);
  Josephus(head, m);
  return 0;
}

在上述代码中，CreateList函数用于创建循环链表，函数的参数n表示总人数，返回值为链表的头节点。Josephus函数用于解决约瑟夫环问题，函数的参数head为链表的头节点，m表示报数的间隔。在函数中使用p和q两个指针定位待移除的人的位置，i变量用于计数，直到计数到m时将这个人从链表中移除。最后，输出最后一个出圈的人的编号。

通过使用C++循环链表实现约瑟夫环问题，我们可以更容易地解决该问题，并得出正确的答案。这个问题也可以作为C++数据结构课程的练手题目，让学生学以致用，更好地理解链表的操作。

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

下一篇: Node.js封装DLL文件

评论区

()

相似文章