探讨“ 两头取数的问题” 的程序设计思路

yang_bigarm

我和我同学编了一个，序列长度2-100，随机数范围0-200，跟人打几乎每次都是电脑必胜。
序列长的时候（25以上）不论先手后手都是电脑胜。

最搞的是，可以设定电脑的不同难度等级，一开始电脑很傻，如果局面简单就会烦错误。
最高难度，不管什么局面，一个局面只要玩两盘，电脑分别先手和后手，都是电脑胜利。
这个时候可以认为已经达到了最优解，也就是赢得最多，或输得最少的策略。

正是因为有了前面的一堆东西，才有了两头取数的这个问题，不过这里我先不说答案，让大家讨论。
说不定有别的方法哦。

yang_bigarm

原帖由 zxl0714 于 2009-4-4 22:01 发表
看来你还没有理解啊。。。。。
动态规划的主要思想就是避免重复计算，你可以这么想，为了确定第1步我们要计算出所有的来比较，第2步我们就不用再计算了，因为第1步已经计算过了。

all, right! 正解！

其实不管是用递归还是动态规划，这个问题都可以求解，这两种方法求解问题各有千秋。
相比之下，递归的思路容易理解，但是动态规划的效率要跟高些(但动态规划并不总是能将指数量级的复杂度变成多项式级别的)，我们把它称作循环式；
但是如果在递归的时候记录中间过程的话，递归式也不会输给循环式(这个时候已经不是严格的递归了)。

现代计算机程序设计里面的一个非常核心的问题就是如何把递归式变成循环式，美国麻省理工学院的教科书《计算机程序的构造和解释》对这方面做了比较详尽的讲解，但是太难了，我也没有耐心把它看完。