猫吃老鼠的系统化算法

　　本文示例源代码或素材下载

　　一、问题描述

　　现有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("
最后一只老鼠是 ");
　　　　}
　　　　pNextEatMouse = CatEatMouses(pNextEatMouse);
　　}
　　
　　printf("
");
　　
　　delete[] pMouseBuffer;
}演示函数主要是初始化nMouseCount个老鼠的双向链表，然后调用CatEatMouses函数来吃老鼠，一直到CatEatMouses函数返回NULL为止，说明老鼠吃完了。

　　四、结束语

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