形形色色的過河問題.ppt

形形色色的過河問題,1、最古老的過河問題,一個(gè)農(nóng)夫攜帶一只狼，一只羊和一棵白菜，要借助一條小船過河。小船上除了農(nóng)民只能再帶狼、羊、白菜中的一樣。而農(nóng)民不在時(shí)，狼會(huì)吃羊，羊會(huì)吃白菜。農(nóng)民如何過河呢？,2、夫妻過河問題,（1）兩對(duì)夫妻要過河，河中只有一條小船，可容兩人。兩個(gè)丈夫都不愿讓自己的妻子和另一個(gè)男人在一起，除非自己也在場(chǎng)。如何過河？,（2）三對(duì)夫妻要過河，河中只有一條小船，可容兩人。每個(gè)丈夫都不愿讓自己的妻子和另一個(gè)男人在一起，除非自己也在場(chǎng)。如何過河？,（3）如果是四對(duì)夫妻，類似的情況，能夠安排過河嗎？,3、三人三鬼乘一船過河 現(xiàn)有三人三鬼乘一船過河，客觀約束條件如下： （1）人或鬼都會(huì)駕船；（2）任何時(shí)候在一個(gè)地方（此岸、彼岸或船上），人數(shù)不少于鬼數(shù)，否則鬼會(huì)吃掉人；（3）小船最多載兩個(gè)生物（人或鬼）。問：如何安排人鬼過河？,4、有一家五口人要在夜晚過一座獨(dú)木橋。他們家里的老爺爺行動(dòng)非常不便，過橋需要12分鐘；孩子們的父親貪吃且不愛運(yùn)動(dòng)，體重嚴(yán)重超標(biāo)，過河需要時(shí)間也較長(zhǎng)，8分鐘；母親則一直堅(jiān)持勞作，動(dòng)作還算敏捷，過橋要6分鐘；兩個(gè)孩子中姐姐需要3分鐘，弟弟只要1分鐘。當(dāng)時(shí)正是初一夜晚又是陰天，不要說月亮，連一點(diǎn)星光都沒有，真所謂伸手不見五指。所幸的是他們有一盞油燈，同時(shí)可以有兩個(gè)人借助燈光過橋。但要命的燈油將盡，這盞燈只能再維持30分鐘了！他們焦急萬分，該怎樣過橋呢？,5、動(dòng)物過河 有六只動(dòng)物：大老虎，小老虎，大獅子，小獅子，大熊，小熊。它們要過一條河，只有一只船。其中，大老虎，大獅子，大熊，小熊會(huì)劃船。大獅子，大熊，大老虎會(huì)攻擊小老虎，小獅子，小熊當(dāng)它們的父親不在身邊時(shí)(如：當(dāng)大老虎不在時(shí)，大獅子、大熊會(huì)攻擊小老虎）。請(qǐng)問，如何讓六只動(dòng)物都安全的過河呢？,6、現(xiàn)有一條河，共有八個(gè)人要過河，分別是爸爸，媽媽，兩個(gè)兒子，兩個(gè)女兒，一個(gè)警察，一個(gè)犯人現(xiàn)有一條木伐，一次最多載兩個(gè)人，在這八個(gè)人中，有媽媽，爸爸，警察會(huì)開船，即這個(gè)船上必須有爸爸，媽媽，警察三個(gè)中的一個(gè)，船才會(huì)開動(dòng)船過去無法自動(dòng)回來并且要避免以下三件事發(fā)生: ，警察不