启发式思维之倒推法两例
倒推法之所以是一种极为深刻的思维方法,本质上是因为它充分利用了题目中一个最不易被察觉到的信息——结论。
例一:用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先取了。
我想到总有一些东西是未知的,然后,就想到前不久看到的一段话。
听人引用赛车手Mario Andretti的话"如果一切都在掌控之中,就说明你开的不够快"。与当年Peter Losecher说"我们在GE时目标如果知道如何达到,就说明定的不够高"异曲同工。关键在知道自己的极限应对能力,挑战极限时不能翻车。
不在乎解决问题的方法,而在乎解决问题的过程,就像赛车一样,开始写代码了,就使劲的写吧。
你是想说思维方法有时并不重要吗?坦白说,没看懂你的comment。
我也不知道自己想说什么,只是想到了什么就说什么。