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

C++实现约瑟夫问题

2023-06-27 21:26:51 深夜i -- --

C++ 实现约瑟夫问题环形链表递归

约瑟夫问题是一个著名的数学问题，其背景源于古代约瑟夫和他的40个战友被罗马人包围的故事。问题的规则是：一群人站成一个圆圈，从某个人开始，每次数m个人并将这个人从圆圈中删除，然后再从他的下一个人开始继续数，直到最后只剩下一个人。现在，我们使用C++语言来解决这个问题。

首先，我们需要创建一个循环链表来表示这些人。我们可以通过定义一个“节点”的结构体来实现：


struct Node{
  int data;
  Node* next;
  Node(int x): data(x), next(NULL){}
};

上面的结构体定义了一个节点，其中包括一个整型的data成员和指向下一个节点的指针next。我们可以使用该结构体来创建一个循环链表，并且在每个节点中填入对应的数字。

接下来，我们需要编写一个函数，来模拟这个问题的求解过程。我们为其命名为“Josephus”，并传入三个参数：人数n、步长m和起始点p。这个函数应该返回最后存活下来的人的编号。


int Josephus(int n, int m, int p){
  Node* head = new Node(1); // 创建第一个节点
  Node* ptr = head; // 指向当前节点的指针
  for(int i=2; i<=n; ++i){
    ptr->next = new Node(i); // 创建新的节点，并将“next”指向它
    ptr = ptr->next; // 将指针移动到新节点
  }
  ptr->next = head; // 将链表首尾相连，形成循环链表
  // 移动指针到起始点
  for(int i=0; i<p-1; ++i)
    ptr = ptr->next;
  
  // 开始进行删除操作
  while(n > 1){
    for(int i=0; i<m-1; ++i)
      ptr = ptr->next;
    
    ptr->next = ptr->next->next;
    n--;
  }
  return ptr->data;
}

上面的函数将会创建一个长度为n的循环链表，并从第p个人开始。然后它会在链表中按照m的步长进行遍历，并删除指定的节点，直至只剩下一个节点。它将返回最后剩下的节点的编号。

最后，让我们来测试一下上面的函数：


#include <iostream>
using namespace std;
int main(){
  int n = 7, m = 3, p = 1;
  int ans = Josephus(n, m, p);
  cout << "The last man standing is: " << ans << endl;
  return 0;
}

上面的程序将会输出：The last man standing is: 4。

在本文中，我们介绍了如何使用C++来实现约瑟夫问题的求解。本问题可以用于熟悉链表的相关操作以及编写基础算法。

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

下一篇: C/C++常用算法解析

评论区

()

相似文章