面試?yán)}1：Jeff and Diamond like playing game of coins.One day they designed a new set of rules:

　?。?）Totally 10 coins.

　?。?）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?

　?。↗和D喜歡玩硬幣游戲，一天他們制定了一套規(guī)則：

　?。?）一共10枚硬幣；

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

　?。?）誰(shuí)拿最后一枚誰(shuí)就輸。

　　可否確定誰(shuí)一定會(huì)輸?shù)舯荣悾?/p>

　　答案：

　　（1）從后面開(kāi)始考慮，最后肯定要留1個(gè)才能保證自己贏。

　?。?）所以要設(shè)法讓對(duì)方留下2，3，5個(gè)。

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

　　（4）如果自己取后留下6，對(duì)方取2個(gè)，與（3）矛盾，所以排除6。

　?。?）如果自己取后留下8，對(duì)方取4個(gè)，與（3）情況一樣，所以也排除8。

　　（6）同樣，9也不行，如果我抽后剩下9，對(duì)方抽2個(gè)，就反過(guò)來(lái)成對(duì)方抽后剩7個(gè)了，也與（3）矛盾，所以也排除。

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

　?。?）因?yàn)橹荒艹楹笫?，4，7才能贏，我先抽的話(huà)不可能達(dá)到這幾個(gè)數(shù)，很顯然，只能讓對(duì)方先抽，即先抽的人輸。

擴(kuò)展知識(shí)

（1）排除法

把一些無(wú)關(guān)的問(wèn)題先予以排除，可以確定的問(wèn)題先確定，盡可能縮小未知的范圍，以便于問(wèn)題的分析和解決。這種思維方式在我們的工作和生活中都是很有用處的。

（2）遞推法

由已知條件層層向下分析，要確保每一步都能準(zhǔn)確無(wú)誤?？赡軙?huì)有幾個(gè)分支，應(yīng)本著先易后難的原則，先從簡(jiǎn)單的一支入手。

（3）倒推法

從問(wèn)題最后的結(jié)果開(kāi)始，一步一步往前推，直到求出問(wèn)題的答案。有些問(wèn)題用此法解起來(lái)很簡(jiǎn)單，如用其他方法則很難。

（4）假設(shè)法

對(duì)給定的問(wèn)題，先做一個(gè)或一些假設(shè)，然后根據(jù)已給的條件進(jìn)行分析，如果出現(xiàn)與題目給的條件有矛盾的情況，說(shuō)明假設(shè)錯(cuò)誤，可再做另一個(gè)或另一些假設(shè)。如果結(jié)果只有兩種可能，那么問(wèn)題就已經(jīng)解決了。在科學(xué)史上，“假設(shè)”曾起了極大的作用。

（5）計(jì)算法

有些問(wèn)題必須經(jīng)計(jì)算才能解決。要注意的是，智力測(cè)驗(yàn)中的問(wèn)題往往含有隱含的條件，有時(shí)給出的數(shù)是無(wú)用的。

（6）分析法

這是最基本的方法。各種方法常常要用到分析法?？梢哉f(shuō)，分析能力的高低，是一個(gè)人的智力水平的體現(xiàn)。分析能力不僅是先天性的，在很大程度上取決于后天的訓(xùn)練，應(yīng)養(yǎng)成對(duì)客觀事物進(jìn)行分析的良好習(xí)慣。

（7）作圖法

根據(jù)問(wèn)題中已知的條件，采用適當(dāng)?shù)姆椒ó?huà)出圖形，有助于問(wèn)題的解決。有些問(wèn)題，在沒(méi)畫(huà)圖之前，會(huì)覺(jué)得無(wú)處下手，畫(huà)了圖后就一目了然了。

（8）綜合法

　　面試?yán)}2：100美元哪里去了？

　　3個(gè)朋友住進(jìn)了一家賓館。結(jié)賬時(shí)，賬單總計(jì)3 000美元。3個(gè)朋友每人分?jǐn)? 000美元，并把這3 000美元如數(shù)交給了服務(wù)員，委托他代到總臺(tái)交賬。但在交賬時(shí)，正逢賓館實(shí)施價(jià)格優(yōu)惠，總臺(tái)退還給服務(wù)員500美元，實(shí)收2 500美元。服務(wù)員從這500美元退款中扣下了200美元，只退還3個(gè)客人300美元。3個(gè)客人平分了這300美元，每人取回了100美元。這樣，3個(gè)客人每人實(shí)際支付900美元，共支付2 700美元，加上服務(wù)員扣的200美元，共計(jì)2 900美元，那么這100美元的差額到哪里去了？

　　答案：這道題純粹是文字游戲，但是如果你的頭腦不夠清晰，很可能把你搞糊涂了?？腿藢?shí)際支付2 700美元，就等于總臺(tái)實(shí)際結(jié)收的2 500美元加上服務(wù)員克扣的200美元。在這2 700美元上加上200美元是毫無(wú)道理的，而在這2 700美元上加退回的300美元，這是有道理的，因?yàn)檫@等于客人原先交給服務(wù)員的3 000美元。

　　面試?yán)}3：擊鼠標(biāo)比賽現(xiàn)在開(kāi)始！參賽者有拉爾夫、威利和保羅。

　　拉爾夫10秒鐘能擊10下鼠標(biāo)，威利20秒鐘能擊20下鼠標(biāo)，保羅5秒鐘能擊5下鼠標(biāo)。以上各人所用的時(shí)間是這樣計(jì)算的：從第一擊開(kāi)始，到最后一擊結(jié)束。

　　他們是否打平手？如果不是，誰(shuí)最先擊完40下鼠標(biāo)？

　　解析：n秒鐘擊n下鼠標(biāo)其實(shí)是擊第一下鼠標(biāo)時(shí)才開(kāi)始計(jì)時(shí)的，實(shí)際上擊n-1下需要n秒鐘，那么若擊40下鼠標(biāo)，拉爾夫需要(40-1)/(9/10)=39/0.9秒，威利需要(40-1)/(19/20)=39/0.95秒，保羅需要(40-1)/(4/5)=39/0.8秒，因此威利先擊完。

　　答案：威利先擊完。

　　面試?yán)}4：用第一感覺(jué)判斷8＋8=91這個(gè)等式正確嗎？說(shuō)明理由。

　　答案：正著不對(duì)，倒過(guò)來(lái)就對(duì)了。

　　面試?yán)}5：父親打電話(huà)給女兒，要她替自己買(mǎi)一些生活用品，同時(shí)告訴她，錢(qián)放在書(shū)桌上的一個(gè)信封里。女兒找到信封，看見(jiàn)上面寫(xiě)著98，以為信封內(nèi)有98元，就把錢(qián)拿出來(lái)，數(shù)也沒(méi)數(shù)放進(jìn)書(shū)包里。在商店里，她買(mǎi)了90元的東西，付款時(shí)才發(fā)現(xiàn)，她不僅沒(méi)有剩下8元，反而差了4元?；氐郊依?，她把這事告訴了父親，懷疑父親把錢(qián)點(diǎn)錯(cuò)了。父親笑著說(shuō)，他并沒(méi)有數(shù)錯(cuò)，錯(cuò)在女兒身上。

　　問(wèn)：女兒錯(cuò)在什么地方？

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

　　面試?yán)}6：3個(gè)孩子翻衣兜，他們把兜里所有的錢(qián)都掏出來(lái)，看看一共有多少錢(qián)。結(jié)果一共有320日元。其中有兩枚硬幣是100日元的，兩枚是50日元的，兩枚是10日元的。每一個(gè)孩子所帶的硬幣中沒(méi)有相同的。而且，沒(méi)帶100日元硬幣的孩子也沒(méi)帶10日元的硬幣，沒(méi)帶50日元硬幣的孩子也沒(méi)帶100日元的硬幣。你能弄清楚這3個(gè)日本孩子原來(lái)各自帶了什么硬幣嗎？

　　答案：第一個(gè)小孩：100，50，10；第二個(gè)小孩：100，50；第三個(gè)小孩：10。

　　面試?yán)}7：有一種小蟲(chóng)，每隔2秒鐘分裂一次。分裂后的2只新的小蟲(chóng)經(jīng)過(guò)2秒鐘后又會(huì)分裂。如果最初某瓶中只有一只小蟲(chóng)，那么2秒后變2只，再過(guò)2秒后就變4只……2分鐘后，正好滿(mǎn)滿(mǎn)一瓶小蟲(chóng)。假設(shè)這個(gè)瓶?jī)?nèi)最初放入2只這樣的小蟲(chóng)。

　　問(wèn)：經(jīng)過(guò)多少時(shí)間后，正巧也是滿(mǎn)滿(mǎn)的一瓶？

　　答案：經(jīng)過(guò)1分58秒時(shí)間，也正巧是滿(mǎn)滿(mǎn)一瓶。因?yàn)閺囊恢幌x(chóng)蛻變?yōu)?只蟲(chóng)只需2秒鐘。在瓶?jī)?nèi)只有一只蟲(chóng)子的情況下，經(jīng)過(guò)2秒鐘后就變成2只。這時(shí)的情況和瓶?jī)?nèi)一開(kāi)始就有2只蟲(chóng)子的情況是一樣的。出現(xiàn)這兩種情況的時(shí)間差是2秒鐘。所以，經(jīng)過(guò)1分58秒后，也正好是滿(mǎn)滿(mǎn)一瓶。

　　面試?yán)}8：斯芬克斯是古代希臘神話(huà)中的帶翅膀的獅子女魔。傳說(shuō)她在底比斯附近要人猜謎，猜不出來(lái)就要?dú)⑷?。一次，她要底比斯王子猜謎：“有一種動(dòng)物，早上4條腿，中午2條腿，晚上3條腿，是什么動(dòng)物？”聰明的王子說(shuō)：“是人。”他猜中了。

　　如果你是現(xiàn)代的斯芬克斯，會(huì)提出什么樣的問(wèn)題呢？比如，1和0之間加上什么符號(hào)才可以使得到的數(shù)比0大又比1小呢？你知道嗎？

　　答案：0.1

　　面試?yán)}9：公司有1 000個(gè)蘋(píng)果和10個(gè)箱子，事先將1 000個(gè)蘋(píng)果分別裝入10個(gè)箱子后，問(wèn)：怎樣做才能在客戶(hù)無(wú)論需要多少蘋(píng)果時(shí)，都可以整箱整箱地提供給客戶(hù)？

　　答案：1，2，4，8，16，32，64，128，256，489。道理很簡(jiǎn)單，第N只箱子應(yīng)該裝的數(shù)量，是前面1到N-1只箱子裝的數(shù)量的總和加1。

　　面試?yán)}10：有一個(gè)100層高的大廈，你手中有兩個(gè)相同的玻璃圍棋子。從這個(gè)大廈的某一層扔下圍棋子就會(huì)碎。用你手中的這兩個(gè)玻璃圍棋子，找出一個(gè)最優(yōu)的策略，來(lái)得知那個(gè)臨界層面。

　　分析：設(shè)總共樓層為h，a(n)（如a(1)、a(2)……）表示每一次拋棋子所在的層次，則對(duì)于任一次拋擲a(n)，必須沿著上一次拋擲所在的層向上逐個(gè)嘗試，即最多必須拋擲a(n) - a(n-1) - 1 + n次。

　　依次類(lèi)推，考慮平均值，將各次求和，消去之后得到：

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

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

　　其最小值發(fā)生于 n = (h*2)^(1/2)的時(shí)候。

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

　　即在最壞情況下，約需14次完成。

　　答案：最多14次。

　　從14層開(kāi)始扔第一次，如果碎了，那么從第2層開(kāi)始扔，一層層加，直到13層。一共14次。

　　如果沒(méi)有碎，在27層再扔一次。依次類(lèi)推，從15層到26層一共12次。加上前面的14層，27層2次所以說(shuō)也是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;

}

　　面試?yán)}11：有一根27厘米的細(xì)木桿，在第3厘米、7厘米、11厘米、17厘米、23厘米這5個(gè)位置上各有一只螞蟻。木桿很細(xì)，不能同時(shí)通過(guò)兩只螞蟻。開(kāi)始時(shí)，螞蟻的頭朝左還是朝右是任意的，它們只會(huì)朝前走或調(diào)頭，但不會(huì)后退。當(dāng)任意兩只螞蟻碰頭時(shí)，兩只螞蟻會(huì)同時(shí)調(diào)頭朝反方向走。假設(shè)螞蟻們每秒鐘可以走一厘米的距離。編寫(xiě)程序，求所有螞蟻都離開(kāi)木桿的最小時(shí)間和最大時(shí)間。

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

　　首先判斷最靠近中間點(diǎn)的螞蟻，用程序很好判斷，就是11厘米處的螞蟻，其實(shí)這個(gè)螞蟻，最快的時(shí)間就是最小時(shí)間。

　　其次判斷最靠外面的螞蟻，用程序很好判斷，就是3厘米處的螞蟻，其實(shí)這個(gè)螞蟻，最慢的時(shí)間就是最大時(shí)間。

　　其他螞蟻無(wú)視就可以了。

　　答案：最大時(shí)間是27-3=24，最小時(shí)間是11-0=11。

　　可以用窮舉法驗(yàn)證算法如下。

#include<iostream>

using namespace std;

//常量設(shè)置

const int APOS=0;        //A點(diǎn)位置

const int BPOS=30;       //B點(diǎn)位置

const int MAXANT=5;      //最大螞蟻數(shù)

const int SPEED=1;       //速度

//全局變量

//初始位置已知量(必須是奇數(shù))

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

//用5位二進(jìn)制數(shù)表示5只螞蟻的開(kāi)始方向 00000～11111,共32種

enum ANTFLAG{

ANTFLAG1 =  0x1,

ANTFLAG2 =  0x2,

ANTFLAG3 =  0x4,

ANTFLAG4 =  0x8,

ANTFLAG5 =  0x10

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

  //...

};

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

//根據(jù)二進(jìn)制數(shù)求螞蟻的開(kāi)始方向

int StartDir(int val1,int val2){

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

return ir;

}

class Ant;

//螞蟻類(lèi)

class Ant{

private:

int  m_id;                          //螞蟻id編號(hào)（0～4）

bool m_life;                       //生命狀態(tài)，初始為1，離開(kāi)桿后為0

int  m_pos;                         //木桿上坐標(biāo)（0～27）

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

int  m_speed;                      //速度(1)

int  m_time;                       //爬行時(shí)間（0～？）

public:

static int count;                 //現(xiàn)有蟻數(shù)

static int antlist[MAXANT];       //存儲(chǔ)每個(gè)螞蟻的位置

public:

Ant();

void Init();                                         //螞蟻初始化

int  GetId(){return m_id;}                           //獲得ID編號(hào)

int  GetTime(){return m_time;}                       //返回時(shí)間

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

void CheckLife();                                    //檢測(cè)生命狀態(tài)

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;

}

//一個(gè)作用螞蟻類(lèi)的類(lèi)

class FunAnt{

public:

int lasttime;                           //最后一只螞蟻離開(kāi)的時(shí)間

Ant ants[MAXANT];                      //螞蟻對(duì)象數(shù)組共5只

public:

FunAnt(){}

    //設(shè)置螞蟻初始方向

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();

}

//一直到最后一只螞蟻離開(kāi)木桿,輸出每只螞蟻所用時(shí)間

void Run()

{  

while(ants[0].count){

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

   {

   ants[i].RunPos();                   //移動(dòng)螞蟻位置

               ants[i].CheckLife();      //檢測(cè)螞蟻是否在桿上

   }

   ChangeDir();                        //檢測(cè),如果螞蟻相遇改變方向

}

lasttime=ants[0].GetTime();

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

{ 

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

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

}

print();

}

//檢測(cè)相鄰螞蟻位置函數(shù),如果位置相同就調(diào)用改變方向函數(shù)

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];                      //存儲(chǔ)32次的結(jié)果數(shù)組

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