面试题目:猫吃老鼠问题的求解
作者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---------------------
阅读(377) | 评论(0) | 转发(0) |