约瑟夫环问题——学习入门并掌握数组实现

约瑟夫环问题——初步认知与数组实现方式

初次接触到约瑟夫环问题，是在学习C语言的过程中，具体的问题描述如下：假设有n个人围成一个圆圈，从某一位开始（例如第一个人），按照顺时针方向依次报数，当数到m时，该人将被淘汰。随后，下一位继续从1开始报数，重复这一过程，直至只剩下最后一个人，并将其输出。

解决思路：

Step 1：创建一个长度为n的数组；

Step 2：确定需要删除的元素位置i = (i + m -1) % n；这一公式背后的逻辑是什么呢？因为初始时第一个人对应的索引为0，每次增加m-1即可找到下一个需要移除的对象。若将数组视为一个循环结构，则这一计算方式能够准确地定位到下一个被淘汰者。

Step 3：在删除i位置的元素后，后续的元素需要向前移动以填补空缺；

Step 4：当i恰好指向数组最后一个元素时，在删除之后由于其后无其他元素可供移动，因此需将i重置为0；

以下为基于数组实现的具体代码示例：

 #include <iostream>

    
 using namespace std; 
    
  
    
 int main()
    
 {
    
 	int m, n; 
    
 	cin >> n >> m; 
    
  
    
 	int *p=new int[n