首页 > 代码库 > UVa 133 双向约瑟夫环

UVa 133 双向约瑟夫环

背景:1_TlE:没有考虑到,当k,m很大的时候,就会用太多时间,那么我想到了:

k=k%n+n;// 之所以要加n,是为了避免,k是n的倍数时,k等于0。
m=m%n+n;
2_WA:经过_TLE:之后没有完善,当k不是n的倍数时就不能加n!终究来说还是没有测试所有数据,以后切题,就把所有数据保存在记事本,要全部通过,才提交!!

 好多人都说这是一个双向链表的数据结构题,被我数组模拟过了,双向约瑟夫环。。。

思路:小紫书在这里出这道题,是想让我们锻炼自顶向下的程序框架思想,即:想建立大框架,一些函数不忙写出来,框架完整后,再去写函数。方法就是用一个数组来记录,对于已经出去过的人,标记为0,下次来数的时候,为0的位置就不算。

#include<stdio.h>
 
int main(void){
    int str[21],n,k,m;
    while(scanf("%d %d %d",&n,&k,&m)!=EOF&&n*n+k*k+m*m != 0){
    	if(k%n == 0) k=k%n+n;
    	else k=k%n;
    	if(m%n == 0) m=m%n+n;
    	else m=m%n;
    	for(int i=1;i <= 20;i++)  str[i]=i;
    	int ki=n,mi=1;
    	while(1){
    	 	for(int i=k;i > 0;i--){
    	 		if(ki == n) ki=1;
					else ki++; 
    	 	 	if(str[ki]==0){
    	 	 		i++;
    	 	 	}
    	 	}
    	 	for(int i=m;i > 0;i--){
    	 	  if(mi == 1) mi=n;
					else mi--;
					if(str[mi]==0) i++; 
    	 	}
    	 	if(mi==ki){
    	 		int all0=0; 
    	 		for(int i=1;i <= n;i++) if(str[i] != 0) all0++;
    	 		if(all0 == 1){
    	 			printf("%3d\n",ki); break;
    	 		}else{
    	 			printf("%3d,",ki);
    	 		}
    	 	}else{
    	 		int two=0;
    	 		for(int i=1;i <= n;i++){
    	 			if(str[i] != 0) two++;
    	 		}
    	 		if(two == 2){
    	 			printf("%3d%3d\n",ki,mi);
    	 			break;
    	 		}else{
    	 			printf("%3d%3d,",ki,mi);
    	 		}
    	 	}
    	 	str[ki]=0;
    	 	str[mi]=0;	
    	}	
    }
	  return 0;
} 



UVa 133 双向约瑟夫环