前幾天去上海某外企參加筆試，由于考試較緊，其中有些大題根本沒辦法完成，很是郁悶。現(xiàn)在偶們打算在這篇文章中探討其中一道筆試題---貓吃老鼠問題的求解。寫這篇文章只是想和大家交流學(xué)習(xí)，難免會(huì)有錯(cuò)誤和不足，希望得到大家的批評(píng)，在此偶們不勝感激！

　　一、問題描述

　　現(xiàn)有n個(gè)老鼠圍成一圓圈，有一只貓從任意位置開始吃老鼠，每次都隔一個(gè)老鼠吃，請(qǐng)給出最后一個(gè)老鼠的編號(hào)？題目要求是任給老鼠數(shù)n，輸出貓最后吃的老鼠的編號(hào)。

　　二、問題求解

　　我們假設(shè)老鼠按順時(shí)針方向編號(hào)，貓從第一號(hào)老鼠開始吃。比如現(xiàn)有4個(gè)老鼠圍成一個(gè)圓，則貓吃老鼠的順序應(yīng)該為1->3->2->4,即最后一個(gè)吃的老鼠的編號(hào)是4。

　　程序設(shè)計(jì)思路說明:

　　貓從老鼠數(shù)組從頭開始移動(dòng)，如果碰到老鼠且間隔標(biāo)志為1，則吃該老鼠，然后間隔標(biāo)志置為0，剩下的老鼠數(shù)減1，繼續(xù)向后移動(dòng)；如果碰到老鼠但間隔標(biāo)志為0，則不吃該老鼠，間隔標(biāo)志置為1，然后向后移動(dòng)；如果沒有碰到老鼠則繼續(xù)向后移動(dòng)；如果移動(dòng)到數(shù)組末則再從頭開始以實(shí)現(xiàn)圓循環(huán)。

　　老鼠數(shù)組ipArray用來表明特定位置是否有老鼠存在，1表示有老鼠存在，0表示此處的老鼠已被吃掉。

　　間隔標(biāo)志ijian為1，表示接下來如果碰到老鼠就可以吃掉；如果為0，則表示剛吃過老鼠應(yīng)該隔一個(gè)再吃，這時(shí)碰到下一個(gè)老鼠就置間隔標(biāo)志為1，但并不吃老鼠。

　　剩下的老鼠數(shù)iyu在每吃掉一個(gè)老鼠后進(jìn)行減一操作；當(dāng)剩余老鼠數(shù)為1時(shí)，則直接找出該老鼠位置，并輸出其編號(hào)，也就是數(shù)組下標(biāo)值加1，到此程序結(jié)束。具體實(shí)現(xiàn)可以參看源代碼

　　三、代碼說明

#include "stdafx.h"
#include <iostream.h>
int main(int argc, char* argv[])
{
　　cout<<"請(qǐng)輸入老鼠數(shù):";
　　int itotal;　　　　//老鼠總數(shù)
　　cin>>itotal;
　　int iyu=itotal;　 //剩下未吃的老鼠數(shù)
　　int ipoint=0;　//移動(dòng)指針　 //指示貓的當(dāng)前位置
　　int ijian=1;　 //間隔標(biāo)志　//1表示已經(jīng)間隔了一個(gè)老鼠，0表示未間隔
　　int * ipArray;　//數(shù)組指針
　　
　　if(iyu<1)
　　{
　　　　cout<<"老鼠數(shù)不能小于1!"<<endl;
　　　　return 0;
　　}
　　if(iyu==1)　 //如果只有一只老鼠，則直接輸出返回
　　{
　　　　cout<<"　"<<ipoint+1<<endl;
　　　　cout<<"結(jié)束!"<<endl;
　　　　return 0;
　　}
　　
　　cout<<"共"<<itotal<<"個(gè)老鼠!"<<endl;
　　　　cout<<"以下是吃老鼠的順序輸出："<<endl;
　　ipArray=new int[iyu];　//生成數(shù)組
　　for(int i=0;i<iyu;i++)　　//初始全部位置都有老鼠存在
　　{
　　　　ipArray[i]=1;　　　　　 //1表示該位置存在老鼠
　　}
　　
　　
　　for(;;)　//循環(huán)開始，依次隔一個(gè)吃老鼠，直到只剩下最后一只老鼠，輸出并程序結(jié)束
　　{
　　　　　　　　ipoint=ipoint%itotal;　//確保在數(shù)組范圍內(nèi)
　　　　if(iyu==1)　 //只剩最后一只的老鼠，直接找出即可
　　　　{
　　　　　　if((ipArray[ipoint]==1))　 //碰到老鼠
　　　　　　{
　　　　　　　　cout<<"　"<<(ipoint+1)<<endl;
　　　　　　　　cout<<"結(jié)束!"<<endl;
　　　　　　　　return 0;　　
　　　　　　}
　　　　}
　　　　else
　　　　{
　　　　　　if((ipArray[ipoint]==1))　 //碰到老鼠
　　　　　　{
　　　　　　　　if(ijian==1)　//如果已跳過一個(gè)老鼠，則現(xiàn)在就可以吃
　　　　　　　　{
　　　　　　　　　　cout<<"　"<<(ipoint+1)<<endl;　 //輸出吃掉的老鼠號(hào)
　　　　　　　　　　ipArray[ipoint]=0;　//條件滿足則吃老鼠，置該位為0；
　　　　　　　　　　ijian=0;　　　　　　 //置間隔標(biāo)志為0；
　　　　　　　　　　iyu--;　　　　　　　//剩下要吃的老鼠數(shù)減一
　　　　　　　　}
　　　　　　　　else　　 //如果剛吃過一個(gè)老鼠
　　　　　　　　{
　　　　　　　　　　ijian=1;　　//設(shè)置間隔標(biāo)志為1
　　　　　　　　}
　　　　　　}
　　　　}
　　　　ipoint++;　　//移動(dòng)貓的位置
　　}//endfor
　　return 0;
}四、結(jié)束語