C++代码实现约瑟夫环问题 |21xrx.com

C++代码实现约瑟夫环问题

2023-07-09 13:50:57 深夜i -- --

C++ 约瑟夫环代码实现

约瑟夫环是一个经典的问题，它涉及到一个固定规则的游戏。游戏的规则是：n个人围成一圆圈，从第k个人开始报数，每数到第m个人，就将该人出圈；然后从出圈的下一个人重新开始报数，直到剩下最后一个人为止。

这个问题可以用C++编写程序来解决。下面是一个使用链表和模拟方式实现的程序：


#include <iostream>
using namespace std;
struct Node {
  int data;
  Node* next;
};
Node* createList(int n) {
  Node* head = new Node;
  Node* p = head;
  for (int i = 1; i <= n; ++i) {
    Node* q = new Node;
    q->data = i;
    p->next = q;
    p = q;
  }
  p->next = head->next;
  return head;
}
void solve(Node* head, int k, int m) {
  Node* p = head->next;
  Node* q = head->next;
  while (p->next != p) {
    for (int i = 1; i < k; ++i)
      q = p;
      p = p->next;
    
    for (int i = 1; i < m; ++i)
      q = p;
      p = p->next;
    
    cout << p->data << " ";
    q->next = p->next;
    delete p;
    p = q->next;
  }
  cout << p->data << endl;
}
int main() {
  int n, k, m;
  cin >> n >> k >> m;
  Node* head = createList(n);
  solve(head, k, m);
  return 0;
}

程序的基本思路是，首先创建一个包含n个人的循环链表，然后用两个指针p和q模拟从第k个人开始报数，每数到第m个人出圈，直到只剩下一个人为止。在每次出圈时，需要删除该节点，并将q节点的指针指向p节点的下一个节点。

这个程序的时间复杂度是O(n*m)，不过随着数据规模的增大，效率可能会变得比较低下。如果需要更快的处理速度，可以使用其他算法，例如递推或数学方法。不过无论使用哪种算法，C++都可以轻松处理这个问题，并给出正确的答案。

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

下一篇: 非Java.lang.Object类的方法

评论区

()

相似文章