使用C++编写约瑟夫环程序 |21xrx.com

使用C++编写约瑟夫环程序

2023-06-27 14:41:56 深夜i -- --

C++ 约瑟夫环编程循环算法

约瑟夫环是一种经典的数学问题，它描述了一个由固定人数组成的圆形队列，队列中的每个人都有一个唯一标识符。从队列中的第一个人开始，数到指定的数之后把这个人从队列中删除，然后从这个人的下一个位置开始重新数数。这个过程一直进行，直到队列中只剩下一个人为止。

我们可以使用C++编写一个约瑟夫环程序，以下将简要介绍该程序的实现过程。

首先，我们需要获取用户输入的参数：圆形队列的人数和每次报数的数值。这可以通过C++中的cin语句实现：


int n, m;
cin >> n >> m;

接下来，我们需要创建一个含有n个节点的循环链表来表示圆形队列。每个节点的值表示该节点对应的人的唯一标识符。循环链表可以使用C++中的结构体和指针来实现：


struct Node {
  int value;
  Node* next;
};
Node* createCircle(int n) {
  Node* head = new Node;
  Node* current = head;
  for (int i = 1; i <= n; i++) {
    current->value = i;
    if (i == n)
      current->next = head;
     else
      current->next = new Node;
      current = current->next;
    
  }
  return head;
}

创建循环链表后，我们需要按照约瑟夫环的规则对圆形队列进行模拟。具体而言，我们需要从第一个节点开始遍历链表，每次数m个节点并删除当前节点。

遍历链表可以用一个while循环来实现，数m个节点可以用一个for循环来实现。为了方便删除当前节点，我们需要记录当前节点的前一个节点，并在for循环中更新current和previous指针。删除节点可以使用C++中的delete操作符来实现。


Node* current = circle;
Node* previous = nullptr;
while (current->next != current) {
  for (int i = 1; i < m; i++)
    previous = current;
    current = current->next;
  
  if (previous == nullptr) {
    previous = current->next;
    current->next = nullptr;
    delete(current);
    current = previous;
    circle = previous;
  } else {
    previous->next = current->next;
    delete(current);
    current = previous->next;
  }
}

最后，我们输出圆形队列中剩余的唯一标识符，即最后留下的那个人的标识符。


cout << "The last person standing is " << circle->value << endl;

以上就是使用C++编写约瑟夫环程序的实现过程。完整代码如下：


#include <iostream>
using namespace std;
struct Node {
  int value;
  Node* next;
};
Node* createCircle(int n) {
  Node* head = new Node;
  Node* current = head;
  for (int i = 1; i <= n; i++) {
    current->value = i;
    if (i == n)
      current->next = head;
     else
      current->next = new Node;
      current = current->next;
    
  }
  return head;
}
int main() {
  int n, m;
  cin >> n >> m;
  Node* circle = createCircle(n);
  Node* current = circle;
  Node* previous = nullptr;
  while (current->next != current) {
    for (int i = 1; i < m; i++)
      previous = current;
      current = current->next;
    
    if (previous == nullptr) {
      previous = current->next;
      current->next = nullptr;
      delete(current);
      current = previous;
      circle = previous;
    } else {
      previous->next = current->next;
      delete(current);
      current = previous->next;
    }
  }
  cout << "The last person standing is " << circle->value << endl;
  return 0;
}

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

下一篇: C++ 成绩管理系统设计报告

评论区

()

相似文章