HDU 1443( Joseph 约瑟夫问题 )

3
4
0

5
30

题目分析：这个题目我目前没找到更好的办法，上网没查到，唉，我的代码跑了500MS 郁闷死了！我是用枚举+模拟的

思路：

for i : 1 -> 14

    for j : i ->

     然后分别用长度位2 * i, 周期为 j 的循环模拟，

solve( k ,m ) :

      每次都是用 kill = (m - 1)%i （这是求本次需要去除的元素的下标）

      更新: start=((start-m)%i+i)%i   ( 其实也可以写成 ：start =( (start - kill -1) %i + i )%i   )

              end=((end - m ) % i + i )  % i; 同理也可以写成上面的那样！

 示例：

    1(0)  2(1)  3(2)  4(3)  5(4)  6(5)

假设  ：周期为5

第一次： kill = ( 5-1)%6=4（因为数组里下标4 就是第5个元素）

然后关键地方 start=(( 0 - 5 )%6+6) %6=1  这里就是关键： 此时 1(1)  2(2)  3(3) 4(4)  6(0)

同理 end=((2-5)%6+6)%6 =3;

这个时候 我们把数组 的顺序做个变动 按下标 重新 排列！

6（0）  1（1）  2（2） 3（3）  4（4）

这样不是又重复了上述过程麽？ 但是start 与end 的指向 永远都是

没变 还是指向那几个元素！

 就这样整个模拟过程的准备工作都完成了！

源程序+部分注释：

#include<iostream>
#include<cstdio>
using namespace std;
int f[15];
bool solve(int k,int m){
	bool flag=true;
	int start=0,end=k-1,kill;
	for(int i=2*k;i>k;i--){
		kill=(m-1)%i;
		//cout<<"i = "<<i<<" "<<"kill = "<<kill<<endl;
		if(kill>=start&&kill<=end){
			flag=false;
			break;
		}
		start=((start-m)%i+i)%i;
		end=((end-m)%i+i)%i;//这样是为了更新起始点，以当前点为0坐标！想象成一个圆形！
		//cout<<"start = "<<start<<" "<<" end = "<<end<<endl;
	}
	return flag;
}

int main(){
	int n;
	for(int i=1;i<=14;i++){
		for(int j=i;;j++){
			if(solve(i,j)){
				f[i]=j;
				break;
			}
		}
	}
	while(~scanf("%d",&n),n){
		printf("%d\n",f[n]);
	}
	return 0;
}

题目总结： 注意学习，模拟约瑟夫循环的过程！

三个方程：

       kill = ( m - 1 ) % n

      start = ( (start - m) % n +n )%n

     end = ((end - m )%n +n)% n;

上述的n是当前的长度，是动态的！