约瑟夫环

约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。 
例如只有三个人，把他们叫做A、B、C，他们围成一圈，从A开始报数，假设报2的人被杀掉。

• 首先A开始报数，他报1。侥幸逃过一劫。
• 然后轮到B报数，他报2。非常惨，他被杀了
• C接着从1开始报数
• 接着轮到A报数，他报2。也被杀死了。
• 最终胜利者是C

现如今给定一个队伍人数 M ，和一个报数淘汰号 N ，编写程序依次输出淘汰的人的编号，编号从 1 开始。

解法一、对数组元素进行删除

每叫道一个人，真的把它踢出去。

void solve(vector<int>& arr,int M,int N){//M人数，N间隔
	int i = 0;
	for(int j = M;j > 0;j --){
		i = (i + N - 1) % j; //每次要删除的位置
		cout<<arr[i]<<" ";
		//删除arr[i] 
		for(int k = i;k < j - 1;k ++)
			arr[k] = arr[k + 1]; 
	}
}

代码如下：

#include<vector>
using namespace std;

void solve(vector<int>& arr,int M,int N){
	int i = 0;
	for(int j = M;j > 0;j --){
		i = (i + N - 1) % j; //每次要删除的位置
		cout<<arr[i]<<" ";
		//删除arr[i] 
		for(int k = i;k < j - 1;k ++)
			arr[k] = arr[k + 1]; 
	}
}

int main(){
	int M,N; 
	cin>>M>>N;//M是总人数，N是报数的间隔 
	vector<int> arr(M);
	for(int i = 0;i < M;i ++) arr[i] = i+1;
	for(int i = 0;i < M;i ++) cout<<arr[i]<<" ";
	cout<<endl;
	cout<<"依次出去："<<endl;
	solve(arr,M,N);
}

运行结果：

解法二、对数组元素添加标记

每叫道一个人，把它的标记置为 -1。

void solve(vector<int>& arr,int M,int N){//M人数，N间隔
	int count = M;
	int shout = 1; //报数
	int i = 0; //数组下标从0开始
	while(count != 0){ //等于0全部报完
		if(shout % N == 0 && arr[i] != -1){ //是3的倍数但是arr[i]!=-1,i和shout都要加 
			cout<<arr[i]<<" ";
			arr[i] = -1;
			count --; //队伍人数减少
			shout++;
			i = (i+1+M)%M; //预防假溢出
		}

		else if(shout % N != 0 && arr[i] != -1){ //不是3的倍数但是arr[i]!=-1,i和shout都要加 
			i = (i+1+M)%M; //预防假溢出
			shout ++;
		}
		//arr[i]==-1 那么i加shout不加
		else i = (i+1+M)%M;
	}
}

代码如下：

#include<iostream>
#include<vector>
using namespace std;

void solve(vector<int>& arr,int M,int N){
	int count = M;
	int shout = 1;
	int i = 0;
	while(count != 0){
		if(shout % N == 0 && arr[i] != -1){ //是3的倍数但是arr[i]!=-1,i和shout都要加 
			cout<<arr[i]<<" ";
			arr[i] = -1;
			count --;
			shout++;
			i = (i+1+M)%M;
		}

		else if(shout % N != 0 && arr[i] != -1){ //不是3的倍数但是arr[i]!=-1,i和shout都要加 
			i = (i+1+M)%M;
			shout ++;
		}
		//arr[i]==-1 那么i加shout不加
		else i = (i+1+M)%M;
	}
}

int main(){
	int M,N; 
	cin>>M>>N;//M是总人数，N是报数的间隔 
	vector<int> arr(M);
	for(int i = 0;i < M;i ++) arr[i] = i+1;
	for(int i = 0;i < M;i ++) cout<<arr[i]<<" ";
	cout<<endl;
	cout<<"依次出去："<<endl;
	solve(arr,M,N);
}

运行结果：