过桥问题 倒水问题

/过桥问题和倒水问题都是笔试面试中的热门智力题，不但微软、GOOGＬE、百度、腾讯等公司采用，甚至在IQ测试与公务员考试中都能见到。本文不但教你如何快速用手算来解决这两种问题，并且教你如何用程序代码来计算这两种问题。绝对让你大有收获。一.过桥问题在漆黑的夜里，四位旅行者来到了一座狭窄而且没有护栏的桥边.如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，四个人一共只带了一只手电筒，而桥窄得只够让两个人同时通过。如果各自单独过桥的话，四人所需要的时间分别是1，2，５,8分钟;而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间.问题是，你如何设计一个方案,让用的时间最少。这个题目被微软、GOOGＬＥ、百度、华硕、建设银行等很多公司用作笔试题或面试题。当然也有用在IQ测试中.解答其实也容易，能者多劳这四个字就足以形容解答方案了——用时短的人必须要多跑几趟以便传递手电筒。设这四个人叫做A,B,C，D,他们所需要的时间分别是1，2，5,８分钟。第一步：A和B过桥，花费2分钟。第二步：Ａ回来,花费1分钟。第三步：C和Ｄ过桥，花费8分钟。第四步:Ｂ回来,花费2分钟.第五步:Ａ和Ｂ过桥，花费２分钟。这样只要花费２+1+８+２+2=15分钟，下面再来考虑如何用程序来解决这类问题,在写程序之前还有个细节要考虑下，比如A,B，C,D四个人所需要的时间分别是1，8,9,1０分钟.方案一第一步:A和Ｂ过桥,花费8分钟.第二步:Ａ回来，花费1分钟。第三步：C和D过桥，花费10分钟。第四步：B回来，花费8分钟。第五步：Ａ和B过桥，花费8分钟。一共要8+１+10＋8+8=３５分钟.方案二第一步:Ａ和Ｂ过桥，花费8分钟.第二步：A回来，花费1分钟。第三步：Ａ和C过桥，花费９分钟。第四步:A回来,花费１分钟.第五步：A和D过桥，花费10分钟。一共要8+1+9+1＋１0＝2９分钟。因此可以得出更加细化的解决方案—-要么是最快者将最慢的2个送过桥,要么是最快的2个将最慢2个送桥。即将过桥的人按其过桥的时间从小到大排列，设为A,Ｂ,……

Y，Ｚ.其中A和B是最快的二个，Y和Z是最慢的二个。那么就有二种方案:方案一最快者将最慢的2个送过桥第一步:Ａ和Z过桥，花费Ｚ分钟。第二步：A回来，花费A分钟。第三步:A和Y过桥，花费Y分钟。第四步:A回来，花费A分钟.这四步后总人数就减小2个，花费时间为A＋A+Y+Z分钟.方案二最快的２个将最慢的2个送过桥第一步：A和Ｂ过桥,花费Ｂ分钟。第二步：A回来,花费A分钟。第三步：Y和Z过桥，花费Z分钟。第四步:Ｂ回来，花费B分钟。这四步后总人数同样减小2个,花费时间为A＋B+Ｂ＋Z分钟。这样,每次比较一下这二种方案就能将总人数减小2.然后我们再考虑一些边界情况：有三个人过桥设为A，B，C（已经排好序，下同）.应该花费A+B+C分钟。有二个人过桥设为A，B。那么肯定是花费Ｂ分钟.有一个人过桥设为A。肯定花费A分钟。

分析至此,代码很容易写出，对输入的数据可以用快速排序来排下序(关于qsｏｒt的使用，可以参见《使用VC库函数中的快速排序函数》）.[cpp]

viewｐlaincopy／/热门智力题

-

过桥问题

＃incｌude〈iostreａｍ．h〉

＃ｉnｃlude〈stdlib。ｈ〉

ｃonｓt

int

MAXN

=

100０；

int

cmｐ（cｏnst

voiｄ

*x，ｃonｓt

vｏｉd

*y)

｛

return

＊(inｔ

＊）x-＊（iｎt

＊）y；

｝

int

main()

{

cout<<＂热门智力题

-

过桥问题"<〈endl；

couｔ＜〈”

－—bｙ

MorｅＷindｏwｓ（

）－-\n"＜〈eｎdl;

ｉnt

n,

i，

suｍ，

ａ[MＡXN]；

ｃｏｕｔ〈＜"请输入人数：”；

ｃin〉＞n;

cout<〈”请输入每个人过桥时间，以空格分开"<<enｄl；

foｒ

（i

=

0；

i

<

n；

ｉ＋+）

cin〉>a[i］;

ｑsｏrt(a，

ｎ，

sｉｚｅof（a[０］)，

cｍｐ);

sum

=

0；

ｆor

（i

=

ｎ

-

1；

ｉ

〉

２；

i

＝

i

-

2）

{

//最小者将最大2个送走或最小２个将最大2个送走

ｉf

(a［0］

＋

a［1］

+

ａ［1］

+

a［i］

〈

ａ［0]

+

a［0]

+

a［ｉ

－

1］

+

a［i])

ｓum

=

suｍ

+

ａ[０］

+

a[１］

+

ａ［1］

+

a［i］;

else

ｓum

=

ｓum

＋

a[0］

+

a［0］

+

a［i

－

１]

+

a［i］；

｝

ｉf

（i

==

２)

ｓｕｍ

=

suｍ

+

a［０］

+

a［1］

+

ａ［2];

else

ｉf

(i

==

1)

sｕm

=

suｍ

+

a［1]；

else

sum

=

a[0］；

cｏut＜<"最短过桥时间为:＂<＜sｕm〈〈endｌ；

ｒetuｒn

0;

}

程序运行结果如下:

二.倒水问题这个题目的版本非常之多,有微软版的，腾讯版的，新浪版的等等，最常见的是给你一个容量为５升的桶和一个容量为3升的桶，水不限使用,要求精确得到４升水。解法肯定有很多，可以用宽度优先搜索（BFS),也可以用穷举法。穷举法实现比较方便，其基本思想是用：用小桶容量的倍数对大桶的容量进行取余。比如3升的桶和5升的桶得到4升水可以这样做：３％5=3６%5=1９%5=4成功得到4升水。(PS：上面的过程用如何用文字描述了?）同样,用7升的桶和１1升的桶得到2升水可以这样做:７%11=714%１1=３21%1１=1０28%11=635％11=2成功得到2升水。哈哈，有了这个基本思想在用笔算答案时简直是遇神杀神，遇佛杀佛,又方便又快速！如果要求用程序来实现如何做了？eａsy，将倒水问题的基本思想用易于编程的话来翻译下——不断用小桶装水倒入大桶,大桶满了立即清空，每次判断下二个桶中水的容量是否等于指定容量。有了这个倒水问题的编程指导方针后代码非常容易写出：［cpｐ］

vｉewpｌａｉncoｐy//热门智力题

—

打水问题

//基本思想：用小桶容量的倍数对大桶的容量进行取余。

//指导方针：不断用小桶装水倒入大桶，大桶满了立即清空，

//每次判断下二个桶中水的容量是否等于指定容量.

＃include<iostream＞

#inclｕde

＜vectｏr＞

#iｎclｕｄe<string〉

usiｎg

naｍespａｃe

sｔｄ；

cｏnｓt

ｓtrｉng

ＯPERAＴOR_NＡMＥ［7］

=

｛

”装满Ａ桶＂，"装满Ｂ桶＂，

"将Ａ桶清空"，"将B桶清空＂，

＂Ａ桶中水倒入B桶”，”Ｂ桶中水倒入A桶",

”成功"

｝；

inｔ

main（)

｛

cout〈＜"热门智力题

—

打水问题"<<ｅｎｄｌ；

cｏｕt<＜”

--by

MｏrｅWinｄｏｗｓ(

）—-＼n”<〈ｅｎdl；

iｎt

a＿vｏluｍe，

b＿voｌuｍe，

goal_vｏlume；

veｃtor〈ｓtrinｇ>

record;

//记录操作步数

int

ai;

int

i,

a_watｅr，

b＿wａteｒ；

cout〈＜"请输入A桶容量，B桶容量，目标容量："；

cｉn>>a_vｏlｕme〉〉ｂ_vｏlｕme>〉goaｌ_volume；

ａ_water

=

b_ｗatｅr

=

0;

//A桶，B桶中有多少升水

ｃhar

sｚTemp［3０];

while

（tｒuｅ）

｛

if

（a_waｔer

=＝

0）//A桶没水,就装满水

｛

ａ_ｗaｔer

=

ａ_voｌuｍｅ;

sprintf（szTemp,

"

A：%d

B：%d",

ａ_water，

b＿ｗａteｒ)；

ｒeｃoｒd。ｐｕsh＿bａｃｋ（OPERATOR_NAME[0］

+

sｚTemp)；//fill

Ａ

｝

ｅlsｅ

｛

//如果A桶的水比（Ｂ桶容量－B桶的水)要多

iｆ

(a_water

>

b＿ｖoｌｕmｅ

－

b_ｗａter）

{

//A桶的水==Ａ桶的水+B桶的水—B桶容量

a_wａter

=

a＿wａｔer

+

ｂ_wａｔｅｒ—

ｂ_volｕme;

b_wａtｅr

=

b_vｏｌume；

／/B桶的水装满了

spriｎｔｆ(szTemp，

”

A：％d

B:％d”,

a_wａter,

b＿watｅr）；

rｅcｏｒｄ.pｕsｈ_bａck（ＯＰERATOR_NAME[4]

+

ｓzTemp)；／/A—>B

ｉｆ

(a_water

==

goal_voｌume）

break；

ｂ_waｔｅr

=

0;

/／将B桶清空

sprｉntf（szTｅmｐ,

"

A：%d

B：％ｄ”,

a_water,

b_watｅr）；

rｅｃorｄ.ｐush＿bａck(OPERATＯＲ_NAME［3］

＋

szＴemp）;

}

else

{

／／B桶的水==A桶的水＋Ｂ桶的水

b_ｗａｔｅr

+＝

a＿water;

a＿ｗateｒ

＝

0；

sprintf(szＴemｐ，

＂

A：％ｄ

Ｂ：%d＂，

a_ｗaｔｅr,

b_ｗaｔｅｒ);

record。push_baｃk（OＰＥＲATOR_NＡME[4]

+

ｓzTemp）；／／Ａ—〉B

iｆ

（ｂ_water

==

goal_ｖｏlume)

ｂrｅak；

｝

｝

｝

record．ｐush＿back(ＯＰERATOR_NAME[６］);

//suｃcｅｓs

cout〈〈”\ｎ-－—-—————--－-－———－－－－—－--—-－－－－－－－—－－－-－——-——－——"<<ｅndl；

ｃout〈<"一个可行的倒水方案如下”〈＜enｄl;

veｃtｏr<stｒｉng〉：：ｉｔｅratoｒ

pos;

foｒ

(pos

＝

reｃoｒd．begin()；

pos

！=

rｅcoｒd.end()；

pos++）

cｏuｔ〈＜＊pos＜〈eｎdl;

cｏut<〈”———－-———-—--－—－—－--——————－—－——-－－--——-———-——-—”<＜eｎdl;

rｅturn

0；