启发式思维和逻辑倒推

     这本书，第三章讲到思维方法，比如：启发式的思考，根据结论隐藏的信息倒推。总结的很棒，我们解决问题就是用这么几种方法，包括逻辑和数学相关的所有问题。其中提到几个逻辑和编程的问题，我就顺便利用这些思维方法去思考题目的解。下面略举几例。

1.100根火柴两个人轮流取，每人每次只能取1～7根，拿到最后一根火柴赢，有必胜策略吗？
       我分析每人每次只能取1～7根，也就是我可以跟着对手后面凑数，两人每次取的根数区间是[2,14]，要是我稳定的跟着对手，根据边界条件则只能选8。对手取1根时，我取7根，对手取7根，我取1根。12 * 8 = 96，也就是我可以跟12轮，还剩100 － 96 ＝ 4根，要是我想赢，则必须开始时我先取4根。这是根据结论推倒的逆向思维过程，比仅仅知道解法有用。


2.两堆橘子，各为m和n个，两人轮流拿，拿的时候你只能选择某一堆在里面拿（即不能跨堆拿），你可以拿1～这堆里面所有剩下的橘子，谁拿到最后一个橘子谁赢。这个题目怎样能获胜？
       这个题目从最简单的情况开始思考，如果两堆各剩1个，那么后拿的人肯定赢；如果两堆各剩2个，那么先拿的人拿一个，后拿的人在另一堆拿一个，变成两堆各剩1个的情况，先拿的人拿两个，后拿的人拿另一堆的两个。
两堆各3个，各4个…… 先拿的人把一堆拿光，他会输，无论拿几个，后拿的人总可以把两边变的个数相等，最后总可以变成两堆各1个或者两堆各2个的情况。所以如果m != n，先拿的人把两堆拿成个数相等，就可以获胜。如果m == n，还是后拿吧，哈哈。


3.求最小（大）连续子序列。
       我想通过程序实现，遇到负数的时候，除非后面有正数能够大于这个，否则后面的连续数字序列就可以舍去。但我没办法预知一个负数后面跟一堆加起来没它大的数字，是否这个负数后面的数字会大于负数之前的数字，然后想到倒着遍历这个序列就可以了。
倒序遍历一堆正数，这些正数可能是最大连续子序列。遇到一个负数，如果负数和遍历过的所有正数相加结果是正数，则接着遍历；如果负数和遍历过的所有正数相加结果的负数，就说明从遍历开始到负数的子序列可以丢弃（正数的最大值留下，他们可能是最大连续子序列），再从负数下一个开始遍历就可以了。
代码如下：

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Author: Yuande Liu

l = [3, 6, -2, 4, -7, 5]
#l = [1, -2, 3]

def max_seq(l):
   total = 0 
   max_val = 0 

   for i, num in enumerate(reversed(l)):
       if num >= 0:
           total += num 
           max_val = max(total, max_val)

       elif total + num > 0:
           max_val = max(total, max_val)
           total += num 

       else:
           ret = max_seq( l[:len(l)-i-1] )
           max_val = max(ret, max_val)

   return max_val

def min_seq(l):
   return -max_seq( map(lambda x: -x, l) )

print max_seq(l)
print min_seq(l)

这里同时给出最小连续子序列。只要把序列取负值，然后调用最大连续子序列的函数，得到结果取负号。


希望这些例子能够启发大家的启发式思维，对倒推的思维逻辑有更好的理解。