面试例题1：Jeff and Diamond like playing game of coins.One day they designed a new set of rules:

　　（1）Totally 10 coins.

　　（2）One can take away 1,2 or 4 coins at one time by turns.

　　（3）Who takes the last loses.

　　Given these rules Whether the winning status is pre-determined or not?

　　（J和D喜欢玩硬币游戏，一天他们制定了一套规则：

　　（1）一共10枚硬币；

　　（2）每次可以取1，2，4枚；

　　（3）谁拿最后一枚谁就输。

　　可否确定谁一定会输掉比赛？

　　答案：

　　（1）从后面开始考虑，最后肯定要留1个才能保证自己赢。

　　（2）所以要设法让对方留下2，3，5个。

　　（3）也就是要自己取后留下1，4，6，7，8，9。

　　（4）如果自己取后留下6，对方取2个，与（3）矛盾，所以排除6。

　　（5）如果自己取后留下8，对方取4个，与（3）情况一样，所以也排除8。

　　（6）同样，9也不行，如果我抽后剩下9，对方抽2个，就反过来成对方抽后剩7个了，也与（3）矛盾，所以也排除。

　　（7）所以很显然，我只能抽后剩1，4，7。

　　（8）因为只能抽后剩1，4，7才能赢，我先抽的话不可能达到这几个数，很显然，只能让对方先抽，即先抽的人输。

扩展知识

（1）排除法

把一些无关的问题先予以排除，可以确定的问题先确定，尽可能缩小未知的范围，以便于问题的分析和解决。这种思维方式在我们的工作和生活中都是很有用处的。

（2）递推法

由已知条件层层向下分析，要确保每一步都能准确无误。可能会有几个分支，应本着先易后难的原则，先从简单的一支入手。

（3）倒推法

从问题最后的结果开始，一步一步往前推，直到求出问题的答案。有些问题用此法解起来很简单，如用其他方法则很难。

（4）假设法

对给定的问题，先做一个或一些假设，然后根据已给的条件进行分析，如果出现与题目给的条件有矛盾的情况，说明假设错误，可再做另一个或另一些假设。如果结果只有两种可能，那么问题就已经解决了。在科学史上，“假设”曾起了极大的作用。

（5）计算法

有些问题必须经计算才能解决。要注意的是，智力测验中的问题往往含有隐含的条件，有时给出的数是无用的。

（6）分析法

这是最基本的方法。各种方法常常要用到分析法。可以说，分析能力的高低，是一个人的智力水平的体现。分析能力不仅是先天性的，在很大程度上取决于后天的训练，应养成对客观事物进行分析的良好习惯。

（7）作图法

根据问题中已知的条件，采用适当的方法画出图形，有助于问题的解决。有些问题，在没画图之前，会觉得无处下手，画了图后就一目了然了。

（8）综合法

　　面试例题2：100美元哪里去了？

　　3个朋友住进了一家宾馆。结账时，账单总计3 000美元。3个朋友每人分摊1 000美元，并把这3 000美元如数交给了服务员，委托他代到总台交账。但在交账时，正逢宾馆实施价格优惠，总台退还给服务员500美元，实收2 500美元。服务员从这500美元退款中扣下了200美元，只退还3个客人300美元。3个客人平分了这300美元，每人取回了100美元。这样，3个客人每人实际支付900美元，共支付2 700美元，加上服务员扣的200美元，共计2 900美元，那么这100美元的差额到哪里去了？

　　答案：这道题纯粹是文字游戏，但是如果你的头脑不够清晰，很可能把你搞糊涂了。客人实际支付2 700美元，就等于总台实际结收的2 500美元加上服务员克扣的200美元。在这2 700美元上加上200美元是毫无道理的，而在这2 700美元上加退回的300美元，这是有道理的，因为这等于客人原先交给服务员的3 000美元。

　　面试例题3：击鼠标比赛现在开始！参赛者有拉尔夫、威利和保罗。

　　拉尔夫10秒钟能击10下鼠标，威利20秒钟能击20下鼠标，保罗5秒钟能击5下鼠标。以上各人所用的时间是这样计算的：从第一击开始，到最后一击结束。

　　他们是否打平手？如果不是，谁最先击完40下鼠标？

　　解析：n秒钟击n下鼠标其实是击第一下鼠标时才开始计时的，实际上击n-1下需要n秒钟，那么若击40下鼠标，拉尔夫需要(40-1)/(9/10)=39/0.9秒，威利需要(40-1)/(19/20)=39/0.95秒，保罗需要(40-1)/(4/5)=39/0.8秒，因此威利先击完。

　　答案：威利先击完。

　　面试例题4：用第一感觉判断8＋8=91这个等式正确吗？说明理由。

　　答案：正着不对，倒过来就对了。

　　面试例题5：父亲打电话给女儿，要她替自己买一些生活用品，同时告诉她，钱放在书桌上的一个信封里。女儿找到信封，看见上面写着98，以为信封内有98元，就把钱拿出来，数也没数放进书包里。在商店里，她买了90元的东西，付款时才发现，她不仅没有剩下8元，反而差了4元。回到家里，她把这事告诉了父亲，怀疑父亲把钱点错了。父亲笑着说，他并没有数错，错在女儿身上。

　　问：女儿错在什么地方？

　　答案：拿倒了，86看成是98了。

　　面试例题6：3个孩子翻衣兜，他们把兜里所有的钱都掏出来，看看一共有多少钱。结果一共有320日元。其中有两枚硬币是100日元的，两枚是50日元的，两枚是10日元的。每一个孩子所带的硬币中没有相同的。而且，没带100日元硬币的孩子也没带10日元的硬币，没带50日元硬币的孩子也没带100日元的硬币。你能弄清楚这3个日本孩子原来各自带了什么硬币吗？

　　答案：第一个小孩：100，50，10；第二个小孩：100，50；第三个小孩：10。

　　面试例题7：有一种小虫，每隔2秒钟分裂一次。分裂后的2只新的小虫经过2秒钟后又会分裂。如果最初某瓶中只有一只小虫，那么2秒后变2只，再过2秒后就变4只……2分钟后，正好满满一瓶小虫。假设这个瓶内最初放入2只这样的小虫。

　　问：经过多少时间后，正巧也是满满的一瓶？

　　答案：经过1分58秒时间，也正巧是满满一瓶。因为从一只虫蜕变为2只虫只需2秒钟。在瓶内只有一只虫子的情况下，经过2秒钟后就变成2只。这时的情况和瓶内一开始就有2只虫子的情况是一样的。出现这两种情况的时间差是2秒钟。所以，经过1分58秒后，也正好是满满一瓶。

　　面试例题8：斯芬克斯是古代希腊神话中的带翅膀的狮子女魔。传说她在底比斯附近要人猜谜，猜不出来就要杀人。一次，她要底比斯王子猜谜：“有一种动物，早上4条腿，中午2条腿，晚上3条腿，是什么动物？”聪明的王子说：“是人。”他猜中了。

　　如果你是现代的斯芬克斯，会提出什么样的问题呢？比如，1和0之间加上什么符号才可以使得到的数比0大又比1小呢？你知道吗？

　　答案：0.1

　　面试例题9：公司有1 000个苹果和10个箱子，事先将1 000个苹果分别装入10个箱子后，问：怎样做才能在客户无论需要多少苹果时，都可以整箱整箱地提供给客户？

　　答案：1，2，4，8，16，32，64，128，256，489。道理很简单，第N只箱子应该装的数量，是前面1到N-1只箱子装的数量的总和加1。

　　面试例题10：有一个100层高的大厦，你手中有两个相同的玻璃围棋子。从这个大厦的某一层扔下围棋子就会碎。用你手中的这两个玻璃围棋子，找出一个最优的策略，来得知那个临界层面。

　　分析：设总共楼层为h，a(n)（如a(1)、a(2)……）表示每一次抛棋子所在的层次，则对于任一次抛掷a(n)，必须沿着上一次抛掷所在的层向上逐个尝试，即最多必须抛掷a(n) - a(n-1) - 1 + n次。

　　依次类推，考虑平均值，将各次求和，消去之后得到：

　　(a(n) - n + (1+n)*n/2) / n

　　由于 a(n) = h，所以等式化为h/n + n/2 + 1/2。

　　其最小值发生于 n = (h*2)^(1/2)的时候。

　　代入 h = 100，得到n约等于14。

　　即在最坏情况下，约需14次完成。

　　答案：最多14次。

　　从14层开始扔第一次，如果碎了，那么从第2层开始扔，一层层加，直到13层。一共14次。

　　如果没有碎，在27层再扔一次。依次类推，从15层到26层一共12次。加上前面的14层，27层2次所以说也是14次。

　　依次这样扔：

　　14

　　14+13=27

　　27+12=39

　　39+11=50

　　50+10=60

　　60+9=69

　　69+8=77

　　77+7=84

　　84+6=90

　　90+5=95

　　96

　　97

　　98

　　99

　　最多14次。

　　算法如下。

#include <iostream>

using namespace std;

int kk[5];

int fmin2[101];

int fmax2[101][101];

int f(int n);

int main()

{

    memset(fmin2,101,sizeof(fmin2));

    memset(fmax2,0,sizeof(fmax2));   

    fmin2[0] = 0;

    fmin2[1] = 1;

    cout <<"100 floor: " << f(100) << endl;

    return 0;

}

int f(int n)

{

if(fmin2[n] < 101) return fmin2[n];

for(int i = 1; i <= n; i++)

{

    int d = f(n-i) ;

           fmax2[n][i] = (i-1) > d ? (i-1) : d;

}

int min = 101;

for(int i = 1; i <= n; i++)

{

            min = min < fmax2[n][i] ? min : fmax2[n][i];

}

fmin2[n] = 1 + min;

return 1 + min;

}

　　面试例题11：有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这5个位置上各有一只蚂蚁。木杆很细，不能同时通过两只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间。

　　解析：可以采用鬼魂算法，鬼魂的意思就是“传递能量”，“穿透”。

　　首先判断最靠近中间点的蚂蚁，用程序很好判断，就是11厘米处的蚂蚁，其实这个蚂蚁，最快的时间就是最小时间。

　　其次判断最靠外面的蚂蚁，用程序很好判断，就是3厘米处的蚂蚁，其实这个蚂蚁，最慢的时间就是最大时间。

　　其他蚂蚁无视就可以了。

　　答案：最大时间是27-3=24，最小时间是11-0=11。

　　可以用穷举法验证算法如下。

#include<iostream>

using namespace std;

//常量设置

const int APOS=0;        //A点位置

const int BPOS=30;       //B点位置

const int MAXANT=5;      //最大蚂蚁数

const int SPEED=1;       //速度

//全局变量

//初始位置已知量(必须是奇数)

int poslist[MAXANT]={3,7,11,17,23};

//用5位二进制数表示5只蚂蚁的开始方向 00000～11111,共32种

enum ANTFLAG{

ANTFLAG1 =  0x1,

ANTFLAG2 =  0x2,

ANTFLAG3 =  0x4,

ANTFLAG4 =  0x8,

ANTFLAG5 =  0x10

  //ANTFLAG6 =  0X20     //假如有更多只

  //...

};

int antflist[]={ANTFLAG1,ANTFLAG2,ANTFLAG3,ANTFLAG4,ANTFLAG5};

//根据二进制数求蚂蚁的开始方向

int StartDir(int val1,int val2){

int ir=(antflist[val1]&val2) ? 1:-1;

return ir;

}

class Ant;

//蚂蚁类

class Ant{

private:

int  m_id;                          //蚂蚁id编号（0～4）

bool m_life;                       //生命状态，初始为1，离开杆后为0

int  m_pos;                         //木杆上坐标（0～27）

int  m_dir;                         //方向(1,-1)

int  m_speed;                      //速度(1)

int  m_time;                       //爬行时间（0～？）

public:

static int count;                 //现有蚁数

static int antlist[MAXANT];       //存储每个蚂蚁的位置

public:

Ant();

void Init();                                         //蚂蚁初始化

int  GetId(){return m_id;}                           //获得ID编号

int  GetTime(){return m_time;}                       //返回时间

void SetDir(int val){ m_dir=StartDir(m_id,val);}     //初始方向

void CheckLife();                                    //检测生命状态

void ChangeDir();                                    //相遇改变方向

void RunPos();                                       //每秒后的位置

void Print(){cout<<"id: "<<m_id<<" pos: "<<m_pos

<<" dir: "<< m_dir<<" time:" <<m_time<<endl;}

};//end ANT

Ant::Ant(){ m_id=count;Init();count++;}

void Ant::Init(){

    m_pos=poslist[m_id];

m_speed=SPEED;

m_life=1;

m_time=0;

}

void Ant::CheckLife (){

if(m_life){

if(m_pos<APOS || m_pos>BPOS)

{

m_life=0;

count--;

}

else

m_time++;   

}

}

void Ant::ChangeDir(){if(m_life){m_dir*=-1;}}

void Ant::RunPos(){

if(m_life)

   m_pos+=m_dir*m_speed;

   antlist[m_id]=m_pos;

}

//一个作用蚂蚁类的类

class FunAnt{

public:

int lasttime;                           //最后一只蚂蚁离开的时间

Ant ants[MAXANT];                      //蚂蚁对象数组共5只

public:

FunAnt(){}

    //设置蚂蚁初始方向

void Funsetdir(int d){

  for(int i=0; i<MAXANT;i++)

  ants[i].SetDir(d);

}

//屏幕输出所有蚂蚁信息

void print(){

for(int i=0;i<MAXANT;i++)

ants[i].Print();

}

//一直到最后一只蚂蚁离开木杆,输出每只蚂蚁所用时间

void Run()

{  

while(ants[0].count){

   for(int i=0;i<MAXANT;i++)

   {

   ants[i].RunPos();                   //移动蚂蚁位置

               ants[i].CheckLife();      //检测蚂蚁是否在杆上

   }

   ChangeDir();                        //检测,如果蚂蚁相遇改变方向

}

lasttime=ants[0].GetTime();

        for(int i=1; i<MAXANT;i++)

{ 

bool b=lasttime<ants[i].GetTime();

if(b){lasttime=ants[i].GetTime();}

}

print();

}

//检测相邻蚂蚁位置函数,如果位置相同就调用改变方向函数

void ChangeDir(){

for(int i=0;i<MAXANT-1;i++)

{

if(ants[0].antlist[i]==ants[0].antlist[i+1])

{

ants[i].ChangeDir();

ants[i+1].ChangeDir();

}

}

}

};

int Ant::antlist[]={3,7,11,17,23};

int Ant::count=0;

//////////////////////////////////////////

int main(){

int  maxlist[32];                      //存储32次的结果数组

for(int i=0;i<32;i++){

Ant::count =0;  

FunAnt a1; 

    a1.Funsetdir(i);

a1.Run();

maxlist[i]=a1.lasttime;

cout<<"lasttime:"<<a1.lasttime<<endl;

}

int min,max;

min=max=maxlist[0];

for(int i=0;i<32 ;i++)

{

 if(max<maxlist[i])

max=maxlist[i];

 if(min>maxlist[i])

 min=maxlist[i];

}

cout<<"max:"<<max<<endl

<<"min:"<<min<<endl;

return 0;

　 }//end main