VC知识库文章 - 面试题目：猫吃老鼠问题的求解

面试题目：猫吃老鼠问题的求解

作者1： 作者2：

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

一、问题描述
    现有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 
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!"<

四、结束语
    本文只是给出了一个初级的求解方法，描述的求解算法在存储空间和运行效率方面不是很好，存储复杂度为O(n),而时间复杂度约为O(n*n),期待有更好的算法提出！

--------------------next---------------------

小弟写的，请指教
int Eat(int n)
{
int _2m=1;
while(_2m<=n)_2m*=2;
return (2*(n-_2m/2+1)-1);
}
( tianpplll 发表于 2007-10-21 20:48:00)
 
每次都吃基数，不就剩偶数
然后除2进入下个循环
最后不就是:2的最高次方(做个好程序员不应该把所有事情都交给程序吧 ( softjdj 发表于 2004-10-15 16:18:00)
 
long eat(long n)
{
   long maxN=0;
   long oldN=0;
   while(max N < n)
  {
      oldN=maxN;
      maxN=maxN*2;
   }
   return oldN;
}
( softjdj 发表于 2004-10-15 16:11:00)
 
...晕，不就2的最大次方吗，一定要写怎么多代码？ ( softjdj 发表于 2004-10-15 15:59:00)
 
修改一下：
#include 
int EatMouse(int num){
int i;
if(num<1)
return 0;
if(num==1)
return 1;
for(i=1;i return (num-i/2)*2;
}
void main(){
int num;
printf("Num of mouse:\t");
scanf("%d",&num);
printf("Mouse left:\t%d\n",EatMouse(num));
} ( anbadboy 发表于 2004-3-25 21:51:00)
 
如果 第一个开始吃，隔一个再吃
最多15行就够了
mai.c文件

int EatMouse(int num)
{
if(num<1)
return 0;
if(num==1)
return 1;
for(i=1;i return (num-i/2)*2;
}
void main()
{
int num;
printf("Num of mouse:");
scanf("%d",&num);
printf("Mouse left:%d",EatMouse(num));
} ( anbadboy 发表于 2004-3-25 21:47:00)
 
最多50行程序就结束了。根本不是什么问题，也太简单了吧？？ ( flyingleaf 发表于 2004-3-25 12:31:00)
 
#include 
int main()
{
const int n = 10;
int x =0,x1=0;
int IsRelease = 1;
int cmou = 10;
int a[n] = {1,1,1,1,1,1,1,1,1,1};
while(cmou>1)
{
if(a[x]==1)
{
          if(IsRelease==1)
  {
  x1 = x;
  cout<<"release "<    }
  else{
  a[x]=0;
  cmou--;
  cout<<"eat"<   }
   IsRelease = -IsRelease;
}
x = (x+1)%n;
}
cout<<"The Last Mouse's number is: "< return 1;

} ( xben 发表于 2004-1-10 1:05:00)
 
用循环链表。链表的每个节点代表一只老鼠，按照隔一个的方法删除节点（相当于被猫吃掉），直到剩下最后一个节点。
( hailiming 发表于 2004-1-5 17:47:00)
 
Var
  i, j: integer;
  mouse: Array Of integer;
  count: integer;
Begin
  j := 0;
  listbox1.Items.Clear;
  count := strtoint(edit1.text);
  setlength(mouse, count);
  For i := 0 To count - 1 Do
    mouse[i] := 1;
  For i := 0 To count - 1 Do
    Begin
      listbox1.Items.Add(inttostr(j + 1));
      mouse[j] := 0;
      j := j + 2;
      j := j Mod count;
      If mouse[j] = 0 Then
        inc(j);
    End;

嘿嘿,小弟准备从DELPHI  2 VC了 ( Longly_Paladin 发表于 2004-1-5 0:28:00)
 
.......................................................

--------------------next---------------------