(顺序表应用5.1.2)UVA 113 The Dole Queue(双向约瑟夫环有关问题:给出总人数n,顺时针数k个,逆时针数m个)

(顺序表应用5.1.2)UVA 113 The Dole Queue(双向约瑟夫环问题:给出总人数n,顺时针数k个,逆时针数m个)

/*
 * UVA_133.cpp
 *
 *  Created on: 2013年10月30日
 *      Author: Administrator
 */
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int maxn = 25;

int main(){
	int n,m,k;
	bool exist[maxn];

	while(scanf("%d%d%d",&n,&k,&m)!=EOF,n||k||m){
		/**
		 * left: 圈内人数
		 * exist[]: 圈中标志
		 * p: 出队序列1
		 * q: 出队序列2
		 */
		int left = n;
		int p = 0 ;
		int q = n + 1;
		memset(exist,true,sizeof(exist));

		while(left){
			/**
			 * k%left 的作用:
			 * 1)当k是left的整数倍的时候,这时只需要数left个即可
			 * 2)当k对left取余为0时,则只需要取余下来的那一部分即可.因为有一部分在转圈
			 */
			int cnt = k%left ? k%left :left;//确定间隔数
			while(cnt--){//连续数cnt个
				do{
					p = (p+1)%n ? (p+1)%n:n;//%n的作用类似于%left,但他还可以规定数的范围
				}while(!exist[p]);
			}

			cnt = m%left ? m%left:left;
			while(cnt--){
				do{
					q = (q-1+n)%n?(q-1+n)%n:n;//顺时针数
				}while(!exist[q]);
			}

			if(left < n){
				printf(",");
			}

			printf("%3d",p);

			if(p!=q){
				printf("%3d",q);
			}

			exist[p]=exist[q] = false;
			left -= ((p == q)?1:2);
		}

		printf("\n");
	}

	return 0;
}