Chinaunix首页 | 论坛 | 博客
  • 博客访问: 9427399
  • 博文数量: 1227
  • 博客积分: 10026
  • 博客等级: 上将
  • 技术积分: 20273
  • 用 户 组: 普通用户
  • 注册时间: 2008-01-16 12:40
文章分类

全部博文(1227)

文章存档

2010年(1)

2008年(1226)

我的朋友

分类: C/C++

2008-04-23 21:43:07

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

作者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),期待有更好的算法提出!

阅读(317) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~