代码说

code is poetry

代码说    
碎碎念:火焰神,武装起来!超弹动双炎斩,超弹动闪光斩!  换一换

人鬼过河问题

作者:coderzheng 发布于:2014-7-15 15:17 Tuesday 分类:other  阅读模式

我们用广义表来表示人和鬼在岸上的数量,初始时为(3,3,0,0),33表示人和鬼初始时的数量, 00表示对岸人鬼的数量。
现在我们来细化问题:按照要求,每次过河时的人和鬼应为下面几种情况之一:(0,1),(1,0),(1,1),(2,0),(0,2),由于过河有去和来两种情况,约定去的时候从上面的方案中取一种并且数值取负。
接下来我们简化问题为:求一个广义表的序列,起始节点为(n,n,0,0),尾节点为(0,0,n,n),其余每一个节点表示当前的过河方案。其中负值方案表示船过去对岸,正值方案表示船回来。
首先我们证明对任意(n,n,0,0)的情况都可以经过下面的步骤转化为(n-1,n-1,1,1)的情况(注意此时船不是在对岸!)
(n,n,0,0):(0,-2) => (n,n-2,0,2)
(n,n-2,0,2):(0,1) => (n,n-1,0,1)
(n,n-1,0,1):(0,-2) => (n,n-3,0,3)
(n,n-3,0,3):(0,1) => (n,n-2,0,2)
(n,n-2,0,2):(-2,0) => (n-2,n-2,2,2)
(n-2,n-2,2,2):(-1,-1) => (n-1,n-1,1,1)
这样我们就将问题简化为(n-1,n-1,1,1) => (0,0,n,n)的问题了。
其次我们证明对(m,m,1,1),当且仅当m<=2时有解。
对任意一个方案(k1,k2), k1>=0, k2>=0, 
1)当m-k1!=0时,要同时满足:(a)m-k1>=m-k2;(b)1+k1>=1+k2;(c)k1+k2<=2
联立(a)(b)(c)可知, k1=k2=1;
这样等量的人和鬼过河之后, 下一步要么等量的人和鬼再移动回来(死循环), 要么人全回来鬼不移动, 这样接下来要避免回到初始状态,只能让鬼继续单独移动到对岸,我们看到随着鬼的数量在对岸不断增加而人的数量一直是0,这样我们就离问题的解越来越远(无解)。
2)当m-k1=0时, 由于k1<=2所以m<=2
当m=2时,
(2,2,1,1):(-2,0) => (0,2,3,1)
(0,2,3,1):(0,1) => (0,3,3,0)
(0,3,3,0):(0,-2) => (0,1,3,2)
(0,1,3,2):(0,1) => (0,2,3,1)
(0,2,3,1):(0,-2) => (0,0,3,3)
当m=1时,
(1,1,1,1):(-1,-1) => (0,0,2,2)

综上,我们得出如下的解法:



标签: 难题集锦

你可以发表评论、引用到你的网站或博客,或通过RSS 2.0订阅这个博客的所有文章。
上一篇: C语言中函数如何返回数组  |  下一篇:php设计模式之工厂模式