学步园

题目：

n 个数字（0,1,…,n-1）形成一个圆圈，从数字0 开始，每次从这个圆圈中删除第m 个数字（第一个为当前数字本身，第二个为当前数字的下一个
数字）, 当一个数字删除后，从被删除数字的下一个继续删除第m 个数字。
求出在这个圆圈中剩下的最后一个数字。

该题目是以下题目的变形。

（n 个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），
凡报到3的人退出圈子，问最后留下的是原来第几号的那个人?）

思路一：

该题目还是比较简单的，在一个数组中不断的进行遍历，从Index 0开始进行数，当Index值等于m的时候，就把该位置值设置为退出标志(0), 不断的进行重复，但是要小心一个点就是当遇到Index值等于n的时候，重新设置Index值从0开始。

#include "stdafx.h"
#include <assert.h>

/*--------------------------------
删除第N个数字只到剩下最后一个数字.
Copyright by yuucyf.  2011.07.21
---------------------------------*/
int RemainLastOne(int i32Count, int i32Pos)
{
	assert(i32Count > 0 && i32Pos > 0);
	int *pi32ArrNum = new int[i32Count];
	assert(NULL != pi32ArrNum);
	for (int i32I = 0; i32I < i32Count; i32I++)
		pi32ArrNum[i32I] = i32I+1;

	int i32ExitPos = 0;
	int i32CurPos = 0;
	int i32ExitCnt= 0;
	while(i32ExitCnt != i32Count-1)
	{
		if (pi32ArrNum[i32CurPos] != 0)
			i32ExitPos++;

		if (i32ExitPos == i32Pos)
		{
			pi32ArrNum[i32CurPos] = 0; //设置退出标志位（对应的数组元素置为0）。
			i32ExitPos = 0;
			i32ExitCnt++;
		}

		i32CurPos++;
		if (i32CurPos == i32Count)
			i32CurPos = 0;
	}

	int RetVal = 0;
	for (int i32J = 0; i32J < i32Count; i32J++)
	{
		if (pi32ArrNum[i32J] != 0)
		{
			RetVal = pi32ArrNum[i32J] - 1;
		}	
	}
	delete [] pi32ArrNum;
	return RetVal;
}

int RemainLastOne_2(int i32Count, int i32Pos)
{
	assert(i32Count > 0 && i32Pos > 0);

	// if there are only one integer in the circle initially,
	// of course the last remaining one is 0
	int i32Value = 0;

	// find the last remaining one in the circle with n integers
	for (int i32I = 1; i32I <= i32Count; i32I++)
		i32Value = (i32Value + i32Pos) % i32I;

	return i32Value;
}


int _tmain(int argc, _TCHAR* argv[])
{
	_tprintf(_T("The last one is %d.\n"), RemainLastOne(20, 4));
	return 0;
}