알고리즘 디자인 과 분석: 제2 장 재 귀 2.4 라운드 게임

/*
    ：12             ，           ，
  7          ，          “1”。      ，
            ，                 ？

    :
      :1~n   .  n+1       1

1）    :
            {Y:     ，   1          
						{N:      

  :【          】
6 3 1（         ）
12(   ) 7(      ) 1
  :
1
12

  :【         】
8 5 3（         ）
100 9999 98
10000 10000 10000
0 0 0
  :
1
93
2019
*/

/*
  :
1     		if(pVisArr[iNextNum] == 0)//           ，   
2 	//    0，        ;         ，     ，           ：         ，       
	memset(pVisArr,0,sizeof(pVisArr));
3 		if(iNextNum > iTotalNum)//    1   0
		{
			iNextNum = 1;
		}
*/

#include <stdio.h>
#include <string.h>

const int MAXSIZE = 10000 + 2;

int lastNumber(int iTotalNum,int iKickNum,int iStartNum)
{
	int iRemainNum = iTotalNum;
	int iCount = 1;
	int pVisArr[MAXSIZE];
	//    0，        ;         ，     ，           ：         ，       
	memset(pVisArr,0,sizeof(pVisArr));
	int iNextNum;
	while(iRemainNum > 1)
	{
		iNextNum = (iStartNum + 1);//        ，  ：    1~n,        iTotalNum+1   iTotalNum
		if(iNextNum > iTotalNum)//    1   0
		{
			iNextNum = 1;
		}
		if(pVisArr[iNextNum] == 0)//           ，   
		{
			iCount++;
			if(iCount == iKickNum)//            
			{
				pVisArr[iNextNum] = 1;//      ，       0
				iCount = 0;
				iRemainNum--;
			}
		}
		iStartNum = iNextNum;
	}
	for(int k = 1 ; k <= iTotalNum ; k++ )
	{
		if(pVisArr[k] == 0)
		{
			return k;
		}
	}
	return -1;
}

int lastNumber_firstDel(int iTotalNum,int iKickNum,int iStartNum)
{
	int iRemainNum = iTotalNum - 1;//         
	int iCount = 0;
	int pVisArr[MAXSIZE];
	//    0，        ;         ，     ，           ：         ，       
	memset(pVisArr,0,sizeof(pVisArr));
	pVisArr[iStartNum] = 1;
	int iNextNum;
	while(iRemainNum > 1)
	{
		iNextNum = (iStartNum + 1);//        ，  ：    1~n,        iTotalNum+1   iTotalNum
		if(iNextNum > iTotalNum)//    1   0
		{
			iNextNum = 1;
		}
		if(pVisArr[iNextNum] == 0)//           ，   
		{
			iCount++;
			if(iCount == iKickNum)//            
			{
				pVisArr[iNextNum] = 1;//      ，       0
				iCount = 0;
				iRemainNum--;
			}
		}
		iStartNum = iNextNum;
	}
	for(int k = 1 ; k <= iTotalNum ; k++ )
	{
		if(pVisArr[k] == 0)
		{
			return k;
		}
	}
	return -1;
}

void process()
{
	int iTotalNum,iKickNum,iStartNum;
	while(EOF != scanf("%d %d %d",&iTotalNum,&iKickNum,&iStartNum) )
	{
		if(iTotalNum == 0 && iKickNum == 0 && iStartNum == 0)
		{
			break;
		}
		//printf("%d
",lastNumber(iTotalNum,iKickNum,iStartNum));
		printf("%d
",lastNumber_firstDel(iTotalNum,iKickNum,iStartNum));
	}
}

int main(int argc,char* argv[])
{
	process();
	getchar();
	return 0;
}