今天无意之中在一个VC的教程上看到了一个很有趣的算法问题的求解，与大字分享一下算法带来的乐趣！！！！！！                  
猫吃老鼠问题的求解
一、问题描述
    现有n个老鼠围成一圆圈，有一只猫从任意位置开始吃老鼠，每次都隔一个老鼠吃，请给出最后一个老鼠的编号？题目要求是任给老鼠数n，输出猫最后吃的老鼠的编号。
二、问题求解
我们假设老鼠按顺时针方向编号，猫从第一号老鼠开始吃。比如现有4个老鼠围成一个圆，则猫吃老鼠的顺序应该为1->3->2->4,即最后一个吃的老鼠的编号是4。
   程序设计思路说明:
   猫从老鼠数组从头开始移动，如果碰到老鼠且间隔标志为1，则吃该老鼠，然后间隔标志置为0，剩下的老鼠数减1，继续向后移动；如果碰到老鼠但间隔标志为0，则不吃该老鼠，间隔标志置为1，然后向后移动；如果没有碰到老鼠则继续向后移动；如果移动到数组末则再从头开始以实现圆循环。
   老鼠数组ipArray用来表明特定位置是否有老鼠存在，1表示有老鼠存在，0表示此处的老鼠已被吃掉。
   间隔标志ijian为1，表示接下来如果碰到老鼠就可以吃掉；如果为0，则表示刚吃过老鼠应该隔一个再吃，这时碰到下一个老鼠就置间隔标志为1，但并不吃老鼠。
   剩下的老鼠数iyu在每吃掉一个老鼠后进行减一操作；当剩余老鼠数为1时，则直接找出该老鼠位置，并输出其编号，也就是数组下标值加1，到此程序结束。

#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;
}

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课