李斤询

下载本文示例源代码

我在VC知识库网站看到猫吃老鼠问题的算法程序(原文请见：http://{域名已经过期}/document/viewdoc/?id=952)，觉得可以使程序更加的系统化，条理更清楚点。为此本人思索了一个新的算法程序，请各位赐教。

一、问题描述
现有n个老鼠围成一圆圈，有一只猫从任意位置开始吃老鼠，每次都隔一个老鼠吃，请给出最后一个老鼠的编号？题目要求是任给老鼠数n，输出猫最后吃的老鼠的编号。

二、问题求解
我们假设有N个老鼠，序号依次为1,2,3,......,N-1,N，并且按序号先后以顺时针围成一圈。

老鼠信息的结构定义如下，使用双向列表，如下：

typedef struct MouseNode

{

	int nNO;

	MouseNode *pNext;

	MouseNode *pPre;



	MouseNode() { nNO = 0; pNext = NULL; pPre = NULL; }

	MouseNode(int NO) { nNO = NO; pNext = NULL; pPre = NULL; }



}MouseNode;



		

我的算法只有一个函数，这个函数完成吃一圈老鼠。传入的参数是双向链表中本次要吃掉的第一个老鼠,返回值是下一圈吃老鼠时要第一个吃掉的老鼠。
函数代码如下：

 // CatEatMouses 

/*

本函数只吃一圈老鼠，循环调用它来吃完老鼠

	参数		本次要吃掉的老鼠

	返回		下一圈吃老鼠时候要吃的第一个老鼠

				若返回值为空，则说明老鼠已经吃完了

*/

MouseNode *CatEatMouses(MouseNode *pStartMouse)

{

	MouseNode *pFirst = pStartMouse;

	MouseNode *pFirstNotEatMouse = pFirst->pNext;

	if(pFirst == pFirstNotEatMouse)

	{

		printf("%d ", pFirst->nNO);

		return NULL; // 吃完了 

	}

	bool bCanEat = true;

	while (true)

	{

		if(pFirst == pFirstNotEatMouse)

		{

			if(bCanEat)

			{

				return pFirstNotEatMouse;

			}

			else

			{

				return pFirstNotEatMouse->pNext;

			}

		}

		if(bCanEat)

		{

			pFirst->pPre->pNext = pFirst->pNext;

			pFirst->pNext->pPre = pFirst->pPre;

			printf("%d ", pFirst->nNO);

			pFirst = pFirst->pNext;

			bCanEat = false;

		}

		else

		{

			pFirst = pFirst->pNext;

		}

	}

}

三、演示函数
演示函数代码如下：

void DemoEatMouse(int nMouseCount)

{

	if(nMouseCount <= 1)

	{

		printf("1");

		return ;

	}

	// 开辟N个老鼠内存并初始化 

	MouseNode *pMouseBuffer = new MouseNode[nMouseCount];

	

	// 初始化双向链表 

	pMouseBuffer[0].pNext = &pMouseBuffer[1];

	pMouseBuffer[0].pPre = &pMouseBuffer[nMouseCount - 1];

	pMouseBuffer[0].nNO = 1;

	pMouseBuffer[nMouseCount - 1].pNext = &pMouseBuffer[0];

	pMouseBuffer[nMouseCount - 1].pPre = &pMouseBuffer[nMouseCount - 2];

	pMouseBuffer[nMouseCount - 1].nNO = nMouseCount;

	for(int i = 1;i < nMouseCount - 1;i++)

	{

		pMouseBuffer[i].pPre = &pMouseBuffer[i - 1];

		pMouseBuffer[i].pNext = &pMouseBuffer[i + 1];

		

		pMouseBuffer[i].nNO = i + 1;

	}

	

	// 开始吃老鼠 

	MouseNode *pNextEatMouse = &pMouseBuffer[0];

	while (pNextEatMouse)

	{

		if(pNextEatMouse->pNext == pNextEatMouse)

		{

			printf("\n最后一只老鼠是 ");

		}

		pNextEatMouse = CatEatMouses(pNextEatMouse);

	}

	

	printf("\n\n");

	

	delete[] pMouseBuffer;

}

演示函数主要是初始化nMouseCount个老鼠的双向链表，然后调用CatEatMouses函数来吃老鼠，一直到CatEatMouses函数返回NULL为止，说明老鼠吃完了。

四、结束语
算法的实现不是说结果对就可以了，我们应该力求让他系统化；如本算法，最终目标是吃掉所有的老鼠，但是我们抓住其中的规律，变换实现每次吃一圈的CatEatMouses函数，每次吃完一圈后又形成一个新的双向链表，在调用CatEatMouse函数。如此算法清晰明了，重复利用性高。