C++代码解决约瑟夫环问题 |21xrx.com

C++代码解决约瑟夫环问题

2023-06-28 12:17:17 深夜i 14 0

C++ 约瑟夫环代码

约瑟夫环问题是一道古老的数学问题，也被称为约瑟夫问题。问题的描述是：有n个人围成一圈，从第一个人开始报数，每报到第m个人，就将这个人杀掉，直到剩下最后一个人。

这个问题可以用C++语言编写代码来解决。我们可以使用循环链表来模拟这个环，每次删除第m个节点，并把环绕到链表开头。

以下是一份C++代码，可以解决约瑟夫环问题。

#include <iostream>
using namespace std;
// 定义循环链表节点
struct Node {
  int data;
  Node* next;
};
// 创建循环链表
Node* create_list(int n) {
  Node* head = new Node();
  Node* p = head;
  for(int i = 1; i <= n; i++) {
    Node* node = new Node();
    node->data = i;
    p->next = node;
    p = node;
  }
  p->next = head->next;
  return head->next;
}
// 解决约瑟夫环问题
void josephus(Node* head, int m) {
  Node* p = head;
  while(p->next != p) {
    // 找到第m个节点
    for(int i = 1; i < m; i++)
      p = p->next;
    
    // 删除这个节点
    Node* temp = p->next;
    p->next = temp->next;
    delete temp;
    // 绕到链表开头
    p = p->next;
  }
  // 输出最后剩下的节点
  cout << "The last one is: " << p->data << endl;
}
int main() {
  int n, m;
  cout << "Input the number of people and the counting number: ";
  cin >> n >> m;
  Node* head = create_list(n);
  josephus(head, m);
  return 0;
}

这段代码首先创建了一个循环链表，然后通过遍历链表找到需要删除的节点，删除这个节点后，再把指针指向链表开头，继续进行下一次的循环。

最终，程序输出了最后留下的节点的编号，即为解决约瑟夫环问题的答案。

通过使用C++语言编写这段代码，我们可以解决约瑟夫环问题，并且学习到了如何使用循环链表来模拟这个环。

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

下一篇: Node.js如何获取文件大小

评论区

相似文章