繁體中文当前位置: 首页 > 图文教程 > 开发语言 > VC++ > 猫吃老鼠的系统化算法
- VC++
- 如何有效地使用对话框
- 一个定制CFileDialog对话框的实例
- XP风格复活节彩蛋的实现
- 程序界面多模式显示的实现
- 改变视图单调的背景
- 使窗体拥有透明效果的API
- 《电子尺》V1.02程序开发实例
- 美化你的应用程序的外观界面
- 个人考勤软件开发实例
- 使用VC6.0实现窗口的任意分割
- 如何让一个打开的文档成为活动文档
- 创建非矩形窗口的简单方法
- 轻松实现类VC界面
- 视图的缩放的完整论述
- 如何获得另一个应用程序窗口中的文本
- 如何发送命令到文档对象
- 动画窗口的实现－VC++实例一则
- 如何在其他程序的窗口上创建按钮并使之能响应
- 如何在基于对话框的程序中动态设置鼠标指针
- 扩展COleDropTarget类来支持任意窗口拖放 - 作者:王加宝
VC++ 中的 猫吃老鼠的系统化算法
出处:互联网 整理: 软晨网（RuanChen.com） 发布: 2009-10-30 浏览: 45 ::
收藏到网摘: n/a
猫吃老鼠的系统化算法 下载本文示例源代码 我在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函数。如此算法清晰明了，重复利用性高。 |
评论 (0) All
