Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1676142
  • 博文数量: 585
  • 博客积分: 14610
  • 博客等级: 上将
  • 技术积分: 7402
  • 用 户 组: 普通用户
  • 注册时间: 2008-05-15 10:52
文章存档

2013年(5)

2012年(214)

2011年(56)

2010年(66)

2009年(44)

2008年(200)

分类: C/C++

2011-09-10 14:18:08

猫吃老鼠的系统化算法

作者:

我在VC知识库网站看到猫吃老鼠问题的算法程序(原文请见:http://www.vckbase.com/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函数。如此算法清晰明了,重复利用性高。
阅读(577) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~