|
|
欢迎访问西户网/西户社区网 XHUME.CC
您需要 登录 才可以下载或查看，没有账号？注册会员
x
- 一、问题描述
- 现有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;
- }
- }
- }三、演示函数
|
|
IP卡
狗仔卡
发表于 2008-12-11 10:35:59
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
千斤顶
显身卡
发表于 2008-12-11 10:45:12
