猫吃老鼠的系统化算法

猫吃老鼠的系统化算法2010-06-09李斤询一、问题描述

现有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;
    }
  }
}