前几天去上海某外企参加笔试，由于考试较紧，其中有些大题根本没办法完成，很是郁闷。现在偶们打算在这篇文章中探讨其中一道笔试题---猫吃老鼠问题的求解。写这篇文章只是想和大家交流学习，难免会有错误和不足，希望得到大家的批评，在此偶们不胜感激！

　　一、问题描述

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

　　二、问题求解

　　我们假设老鼠按顺时针方向编号，猫从第一号老鼠开始吃。比如现有4个老鼠围成一个圆，则猫吃老鼠的顺序应该为1->3->2->4,即最后一个吃的老鼠的编号是4。

　　程序设计思路说明:

　　猫从老鼠数组从头开始移动，如果碰到老鼠且间隔标志为1，则吃该老鼠，然后间隔标志置为0，剩下的老鼠数减1，继续向后移动；如果碰到老鼠但间隔标志为0，则不吃该老鼠，间隔标志置为1，然后向后移动；如果没有碰到老鼠则继续向后移动；如果移动到数组末则再从头开始以实现圆循环。

　　老鼠数组ipArray用来表明特定位置是否有老鼠存在，1表示有老鼠存在，0表示此处的老鼠已被吃掉。

　　间隔标志ijian为1，表示接下来如果碰到老鼠就可以吃掉；如果为0，则表示刚吃过老鼠应该隔一个再吃，这时碰到下一个老鼠就置间隔标志为1，但并不吃老鼠。

　　剩下的老鼠数iyu在每吃掉一个老鼠后进行减一操作；当剩余老鼠数为1时，则直接找出该老鼠位置，并输出其编号，也就是数组下标值加1，到此程序结束。具体实现可以参看源代码

　　三、代码说明

#include "stdafx.h"
#include <iostream.h>
int main(int argc, char* argv[])
{
　　cout<<"请输入老鼠数:";
　　int itotal;　　　　//老鼠总数
　　cin>>itotal;
　　int iyu=itotal;　 //剩下未吃的老鼠数
　　int ipoint=0;　//移动指针　 //指示猫的当前位置
　　int ijian=1;　 //间隔标志　//1表示已经间隔了一个老鼠，0表示未间隔
　　int * ipArray;　//数组指针
　　
　　if(iyu<1)
　　{
　　　　cout<<"老鼠数不能小于1!"<<endl;
　　　　return 0;
　　}
　　if(iyu==1)　 //如果只有一只老鼠，则直接输出返回
　　{
　　　　cout<<"　"<<ipoint+1<<endl;
　　　　cout<<"结束!"<<endl;
　　　　return 0;
　　}
　　
　　cout<<"共"<<itotal<<"个老鼠!"<<endl;
　　　　cout<<"以下是吃老鼠的顺序输出："<<endl;
　　ipArray=new int[iyu];　//生成数组
　　for(int i=0;i<iyu;i++)　　//初始全部位置都有老鼠存在
　　{
　　　　ipArray[i]=1;　　　　　 //1表示该位置存在老鼠
　　}
　　
　　
　　for(;;)　//循环开始，依次隔一个吃老鼠，直到只剩下最后一只老鼠，输出并程序结束
　　{
　　　　　　　　ipoint=ipoint%itotal;　//确保在数组范围内
　　　　if(iyu==1)　 //只剩最后一只的老鼠，直接找出即可
　　　　{
　　　　　　if((ipArray[ipoint]==1))　 //碰到老鼠
　　　　　　{
　　　　　　　　cout<<"　"<<(ipoint+1)<<endl;
　　　　　　　　cout<<"结束!"<<endl;
　　　　　　　　return 0;　　
　　　　　　}
　　　　}
　　　　else
　　　　{
　　　　　　if((ipArray[ipoint]==1))　 //碰到老鼠
　　　　　　{
　　　　　　　　if(ijian==1)　//如果已跳过一个老鼠，则现在就可以吃
　　　　　　　　{
　　　　　　　　　　cout<<"　"<<(ipoint+1)<<endl;　 //输出吃掉的老鼠号
　　　　　　　　　　ipArray[ipoint]=0;　//条件满足则吃老鼠，置该位为0；
　　　　　　　　　　ijian=0;　　　　　　 //置间隔标志为0；
　　　　　　　　　　iyu--;　　　　　　　//剩下要吃的老鼠数减一
　　　　　　　　}
　　　　　　　　else　　 //如果刚吃过一个老鼠
　　　　　　　　{
　　　　　　　　　　ijian=1;　　//设置间隔标志为1
　　　　　　　　}
　　　　　　}
　　　　}
　　　　ipoint++;　　//移动猫的位置
　　}//endfor
　　return 0;
}四、结束语