数组例题——约瑟夫问题

据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个山洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

我们将问题简化，$n$个人围成一个圆圈，每个人的编号依次是1、2、3、……、$n$。从第一个人开始数数，数到$m$的人出圈。然后由出圈的下一个人重新数数，数到$m$的人又出圈……输入$n$和$m$（$1 \le n \le 100,1 \le m \le 1,000,000$），依次输出出圈人的编号。

一、借助数组记录圈里人的编号

最朴素的做法，借助数组记录圈里人的编号。模拟整个过程，有人出圈就将数组对应位置元素删除，可知模拟过程中整个数组实时记录了圈里人的所有编号。此外还需要借助一个变量模拟数数的过程，特别是有人出圈后，下一个人继续数数（而不是重新数数）。这里给出比较原始的参考程序：

#include<iostream>
using namespace std;
const int N = 100;
//数组a记录圈里人的编号 
int a[N+1];
int main()
{
	int n,m,i,j,p;
	cin>>n>>m;

	//开始时n个人都在圈里，第i个人的编号i存储在a[i]中 
	for(i=1;i<=n;i++) a[i] = i;

	//变量p用来记录数数的人对应数组中的下标
	//初始值设置为0（进入模拟过程执行p++，正好第1个人数1） 
	p = 0;

	//n次循环n个人依次出圈，控制变量i正好是圈里人的数量 
	for(i=n;i>=1;i--){
		//当前圈里有i个人，从编号p的人开始，m个人依次数数 
		for(j=1;j<=m;j++){
			p++;
			//发现是第(i+1)个人数数，修正成第1个人数数（构成一个圈） 
			if(p==i+1) p=1; 
		}
		
		cout<<a[p]<<" ";
		
		//删除数组元素a[p]（数组依次前移1位，覆盖掉a[p]） 
		for(j=p;j<i;j++) a[j] = a[j+1];
		
		//出圈后，下次数数要从新的a[p]开始，执行p--
		//这样下次数数第一次执行p++时，正好这个位置的人数1 
		p--;
	}
	return 0; 
}

很容易发现，每次m个人数数，其实可以不用一个循环来模拟，这里是可以直接计算出来出圈人的下标：

#include<iostream>
using namespace std;
const int N = 100;
//数组a记录圈里人的编号 
int a[N+1];
int main()
{
    int n,m,i,j,p;
    cin>>n>>m;

    //开始时n个人都在圈里，第i个人的编号i存储在a[i]中 
    for(i=1;i<=n;i++) a[i] = i;

    //变量p用来记录数数的人对应数组中的下标
    //初始值设置为0（进入模拟过程执行p++，正好第1个人数1） 
    p = 0;

    //n次循环n个人依次出圈，控制变量i正好是圈里人的数量 
    for(i=n;i>=1;i--){
        //当前圈里有i个人，从编号p的人开始，m个人依次数数
		//计算本次出圈（数到m的人）的下标p 
        p = (p+m)%i;
        if(p==0) p = i;
        
        cout<<a[p]<<" ";
        
        //删除数组元素a[p]（数组依次前移1位，覆盖掉a[p]） 
        for(j=p;j<i;j++) a[j] = a[j+1];
        
        //出圈后，下次数数要从新的a[p]开始，执行p--
        //这样下次数数第一次执行p++时，正好这个位置的人数1 
        p--;
    }
    return 0; 
}

上面的代码计算本次出圈人的下标使用的核心代码p = (k+m)%i; 使用了模运算，原因是随着出列人数的增多，$k+m$会大于$i$。其实原始数据输入时也有可能$m$远大于$n$，即使是第1段示例代码借助循环来模拟每次数数，也完全不用每次数到$m$。

二、借助数组记录每个人的状态（是否出圈）

上面使用数组来记录圈里人的编号，当有人出圈时，要借助大量的数组元素前移来删除数组元素，降低了效率。其实我们还可以用数组来记录每个人的状态，a[p]记录编号为p的人是否出圈，0表示没有出圈，1表示出圈。此时要模拟整个过程，对于数组里的每个元素都要考察，发现没有出圈才数数。可以在循环里嵌套一个循环，一次性把这一轮出圈的人计算出来：

#include<iostream>
using namespace std;
const int N = 100;
//a[p]记录编号为p的人是否已经出圈：0-没有出圈，1-已经出圈
//全局数组a所有元素会被自动初始化成0，也就表示最开始时所有人都没有出圈（都在圈里） 
int a[N+1];
int main()
{
    int n,m;
    cin>>n>>m;

    //变量p记录正在考察的人的编号
    //注意每个人（不管有没有出圈）都要考察，但是只有还在圈里的人才数数
    //p初始值设置成0，后面一进循环p++，正好考察编号为1的人
    int p = 0;

	for(int i=n;i>=1;i--){    //n次循环，每次出圈一人
        int tot = 0;    //tot记录数数数到几
        while(tot!=m){ 
            p++;                //考察下一个人 
            if(p>n) p=1;        //回到编号为1的人
            if(a[p] == 0) {     //编号为p的人还在圈里
                tot++;
            }
        }
        //出循环后，编号为p的人数到了m 
        a[p] = 1;            //记录编号为p的人出圈
        cout<<p<<" ";        //编号为p的人出圈，输出p
    }
    return 0; 
}

m如果比当前圈内剩余人数(n-p)大很多，这里会数好多圈，效率低下，可以使用模运算来提高效率：

#include<iostream>
using namespace std;
const int N = 100;
//a[p]记录编号为p的人是否已经出圈：0-没有出圈，1-已经出圈
//全局数组a所有元素会被自动初始化成0，也就表示最开始时所有人都没有出圈（都在圈里） 
int a[N+1];
int main()
{
    int n,m;
    cin>>n>>m;

    //变量p记录正在考察的人的编号
    //注意每个人（不管有没有出圈）都要考察，但是只有还在圈里的人才数数
    //p初始值设置成0，后面一进循环p++，正好考察编号为1的人
    int p = 0;

	for(int i=n;i>=1;i--){    //n次循环，每次出圈一人
		//md是修正后的本轮次要数到多少结束 
        int md = m%i;		//i是当前还在圈里的人数 
        if(md==0) md = i; 
        
        int tot = 0;    //tot记录数数数到几
        while(tot!=md){ 
            p++;                //考察下一个人 
            if(p>n) p=1;        //回到编号为1的人
            if(a[p] == 0) {     //编号为p的人还在圈里
                tot++;
            }
        }
        //出循环后，编号为p的人数到了m 
        a[p] = 1;            //记录编号为p的人出圈
        cout<<p<<" ";        //编号为p的人出圈，输出p
    }
    return 0; 
}

这样的处理方式避免了数组大量元素的移动，但是数组的每个元素（即使对应的人已经出圈）都要考虑是否数数，同样会耗费大量的时间。如果不用考察已经出圈的人，程序的效率还可以进一步提升，更优化的程序我们在后面的章节会介绍到。