2009年4月24日星期五

How To Solve It,1

譬如《How To Solve It》上面举的例子:通过一个9升水的桶和一个4升水的桶在河里取6升水。这个题目通过正向试错,很快也能发现答案,然而通过反向归约,则能够不偏不倚的命中答案。
如果是正向试错,也就是分析6L的水如何装在这两个桶里,也就是两种结果
9L桶 4L桶
6 0

2 4
再来分析如何装入,这个纯属暴力算法。考虑情况1,也就是9L桶中倒出3L,由于9-3=6,4-3=1,9-1=8,8=2*4;也就可以分析出交换过程了。考虑情况2,这个情况相比第一种要复杂一些,因为结果是不可解,换句话说,(2,4)情况可转化成(6,0)即最终结果仅一种。

如果采用的是逆向推理,比较适应直觉思考。其实在正向推理的过程中我不知不觉用到了逆向推理。呵呵,也就是算式写的顺序,如果是正向的话,应该从8=2*4开始推。

说了这么多,这道题还有许多的拓展问题。其实在思考方式上很像——编程人员最优美也是最头疼的递归算法。

没有评论:

发表评论