约瑟夫问题---C++

今天来讲一道饶有名气的题目，约瑟夫问题

约瑟夫问题

这道题目有许多大佬用队列、递归、链表来解这道题目而这题的难度也确实非同小可！

可是你们难道没有想过？用数组去解决吗？没错一维数组！为了想出解决办法我掉了23根头发。真的，不管你们信不信。。。。

还是一样，先画图分析。

1.数组模拟环状，数组类型

可以发现，我们可以用数组来模拟这样一个环状！当t==n+1的时候，也就是说已经循环一圈完了。那此时的程序估计也快结束了，当然这时不可能的。 既然如此！我们不妨把数组类型定义成bool类型！false是没出圈，而true是已经出圈的人。然后循环判断即可。

 2.人数减少（细枝末节）

其实人数减少，就是把已经出圈的人定为true，就是把对应的数组下标定为true。每次出圈的话将f递增即可，最后

题目代码：

#include<cstdio>
int n,m,s,f,t;
bool a[1002];
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=1002;i++){
		a[i]=false;
	}
	do{
		t++;
		if(t==n+1){
			t=1;
		}
		if(a[t]==false){
			s++;
		}
		if(s==m){
			s=0;
			printf("%d ",t);
			a[t]=true;
			f++;
		}
	}while(f!=n);
	return 0;
} 

不去试试？