面试题目：猫吃老鼠问题的求解算法改进

一、问题描述 现有n个老鼠围成一圆圈，有一只猫从任意位置开始吃老鼠，每次都隔一个老鼠吃，请给出最后一个老鼠的编号？题目要求是任给老鼠数n，输出猫最后吃的老鼠的编号。

二、代码说明
#include <iostream>
#include <vector>
using namespace std;

int fun1(int itotal);

int main()
{
   cout<<”请输入老鼠数:”;
   int itotal;        //老鼠总数
   cin>>itotal;

   fun(itotal);
   
   return 1;
}

int fun(int itotal)
{
   vector<int> locVec; //存取每次开始的位置
   int ileft = itotal;//剩余的老鼠数
   
   int startLoc = 1;//每次吃的开始位置
   locVec.push_back(startLoc);
   while(ileft>1)
   {
      if(startLoc == 1)
      {
         if(ile ft % 2 == 0)
         {
             startLoc = 1;
         }
         else
         {
             startLoc = 2;
         }
         ileft = ileft/2;
      }
      else
      {
         if(ile ft % 2 == 0)
         {
             startLoc = 2;
             ileft = ileft/2;
         }
         else
         {
             startLoc = 1;
             ileft = ileft/2 + 1;
         }
      }
      locVec.push_back(startLo c);
   }

   //以下计算老鼠的标号
   int n = 1;
   for( int i=locVec.size()-2;i>=0;–i)
   {
      n *= 2;
      if( locVec == 2)
      {
         –n;
      }
   }
   cout>> n >>endl;

   return 1;
}

三、结束语

数学是计算机技术的有力工具！