启发式思维之倒推法两例


倒推法之所以是一种极为深刻的思维方法,本质上是因为它充分利用了题目中一个最不易被察觉到的信息——结论。

刘未鹏《暗时间》132页提及的两个例子。

例一:用9升的桶和4升的桶各一个从河里取6升的水。

思维过程:6 = 9 - 3,9已知,3未知,3 = 4 - 1,4已知,1未知,1 = 9 - 4 - 4,9和4皆已知。

所以解法是:用9升的桶取9升水,往4升的桶里倒两次,余1升水,存在4升的桶中;再用9升的桶取9升水,把已经有1升水的4升的桶倒满,则9升的桶中便剩6升水。

当然, 反向推导时,也有可能走偏。比如我一开始就这样思考的:6 = 5 +1,5 = 9 - 4,1 = 5 - 4,这一过程中5 + 1难以实现,因为9升的桶和4升的桶分别只有一个,如果有多个,还是可行的。

例二:100根火柴,两个人轮流取,每人每次只能取1~7根,谁拿到最后一根谁赢;问有必胜策略吗?有的话,是先手还是后手必胜?

设两个人为A和B,假定B必胜,先考虑最后一步(第N步), 每一步都是A先取,B后取。反向推导过程如下:

第N步:必须为8根,这样A随便怎么取(1~7根),B都可以一次将剩余的取完。

第N-1步:要想第N步有8根,B取之前必须为9~15根,那么A取之前必须为16根。

第N-2步:要想第N-1步有16根,B取之前必须为17~23根,那么A取之前必须为24根。

第N-3步:要想第N-2步有24根,B取之前必须为25~31根,那么A取之前必须为32根。

......

这时,注意到数字8,16,24,32,......都是8的倍数。也就是说,只要B取完后,保证剩下的火柴数为8的倍数就可以了。考虑100根火柴的情况,B想必胜的话,最好B先取4根,剩下96根(8 * 12),然后A取,B再取,保证剩下88根,依此类推。最终B胜。

简单来说:假定火柴总数为N根,B先取N%8(N模8)根,随后A取m根,B就取8-m根。

如果A不知道此必胜方法,那么即使A先取,B也可能获胜。只要在当中的某步,保证B取后剩余8 * N根即可。

至此,我们没有考虑N为8的倍数的情况,当总数为8的倍数时,就得让A先取了。

发表评论 | Trackback
2011年11月23日 | 归档于 思维方法
标签:
  1. Jay
    回复 | 引用
    2011年11月24日 22:56 | #1

    我想到总有一些东西是未知的,然后,就想到前不久看到的一段话。

    听人引用赛车手Mario Andretti的话"如果一切都在掌控之中,就说明你开的不够快"。与当年Peter Losecher说"我们在GE时目标如果知道如何达到,就说明定的不够高"异曲同工。关键在知道自己的极限应对能力,挑战极限时不能翻车。

    不在乎解决问题的方法,而在乎解决问题的过程,就像赛车一样,开始写代码了,就使劲的写吧。

    • 春庭
      回复 | 引用
      2011年11月25日 09:00 | #2

      你是想说思维方法有时并不重要吗?坦白说,没看懂你的comment。

      • Jay
        回复 | 引用
        2011年11月25日 21:49 | #3

        我也不知道自己想说什么,只是想到了什么就说什么。

发表评论

XHTML: 您可以使用这些标签: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>