如何过河问题通解(3大3小6只动物怎么安全抵达河对岸)

标签:
休闲 |
分类: 常见问题·解迷津 |
原题目:
有一条河,如何把三组动物安全运送到河对岸?
三组动物是大熊、小熊、大老虎、小老虎、大狮子、小狮子。
河边有一条船一次只能运送最多2只动物,即1-2只动物。
三组动物中当大动物和小动物在没有同类动物看守时小动物会被大动物吃掉。
(在有同类动物时不会吃掉小动物,如小熊和大熊在一起。)
其中:大老虎、大狮子、大熊、小狮子都会划船,而小老虎、小熊不会划船。
怎样运送可以让动物们安全的到达对岸?
(导引)简单类:
题目:农夫带着A、B、C 三只动物过河,一次只能带一只,已知农夫不在场时A吃B,B吃C,如何带?
解析:1、农夫带B过去,剩AC;空着回来。
2、农夫带A过去,剩C;农夫再把B带回来,留A单独在对岸。
3、农夫把B放下,带C过去,对岸变AC;农夫可以空着回来,再把B带过去。
关键点:利用特殊的B,反复“折腾”。
(原题)复杂类:
读题目可归纳为,动物为3大3小,单独1小不能和其他2大在一起。
可利用的是某一类动物,如大A、小a都会自己划船,那这组动物就是关键。
1、如果单独大A运送,则小a会被吃掉,推断必须由小a先送,那么运送的只能是小动物。
2、因此第一环节是利用小a将小b和小c送到对岸,达到三小在对岸的情况。
3、小a回来后,如果大A去对岸将和小a分离,只能是大B大C过河。
两小回来会被剩的大A吃掉,只能是成对回来。
4、回来Bb或Cc的任意一对以后,成对过河必然是Aa,否则重复了上步。
两小回必被吃,两大回来势必下次一大过河会有小被吃,因此定是Cc回来。
5、两小过河必被吃,因此必是两大过河。
大A不能返回,否则小a被吃,因此小a单独回来。
6、此步看似回来有两种回法,本题目一个思路,产生了共四中答法。
其中如果选方案②可以看到,由这这边单独剩Aa,与对岸单独留Aa,是对称的。
( 即做到第五步已经看到题目成功解出。
因为与第三步对比,只是三大与三小的河对岸位置互换。
那么后半程近似前半程的逆向。)