C++代码：约瑟夫环 |21xrx.com

C++代码：约瑟夫环

2023-07-12 15:31:14 深夜i -- --

C++ 约瑟夫环算法链表循环

约瑟夫环是一个经典的数学问题，它涉及到人们围成一圈，选择一个数作为开始点，按照一定规则进行数数和淘汰，最终留下的人获胜。这个问题可以用C++实现，并使用链表来存储。

首先，定义一个链表节点class，包含一个整数值和指向下一个节点的指针。代码如下：


class Node {
public:
  int value;
  Node* next;
  Node(int v, Node* n=NULL): value(v), next(n){};
};

然后，定义一个函数实现约瑟夫环的具体过程。该函数接受两个参数：参与游戏的人数n和淘汰规则k。该函数会创建一个大小为n的链表，并在其中循环淘汰，直到只剩下一个节点。代码如下：


int josephus(int n, int k) {
  Node* head = new Node(1);
  Node* temp = head;
  for(int i=2; i<=n; i++){
    temp->next = new Node(i);
    temp = temp->next;
  }
  temp->next = head;
  Node* curr = head;
  Node* prev = temp;
  int count = 0;
  while(curr->next != curr) {
    count++;
    if(count % k == 0)
      prev->next = curr->next;
      delete curr;
      curr = prev->next;
     else
      prev = curr;
      curr = curr->next;
    
  }
  int result = curr->value;
  delete curr;
  return result;
}

该函数的实现过程如下：

1. 创建一个大小为n的链表，并将所有节点链接起来。

2. 使用curr和prev指针遍历链表，直到只剩下一个节点。

3. 在遍历的过程中，根据淘汰规则k，每遍历到k个节点就将当前节点删除。

4. 最后，返回最后一个节点的值，即为存活者的编号。

使用上述代码实现约瑟夫环，可以轻松解决这个经典问题。C++的链表结构和指针操作充分利用了现代计算机的高效性能，并简化了代码实现过程。

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

下一篇: C++ 缺省参数

评论区

()

相似文章