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

lulijie

源自yang_bigarm的贴 两头取数的问题
N个数字排成一列，甲乙两个人轮流取数。取数规则如下：
               每人每次取一个数，必须取第一个数，或最后一个数。取走的数从数列中拿走。
所有的数都拿走后，将甲取走的数相加得到S甲，乙取走的数相加得到S乙。
甲取数的目标是使得S甲尽可能大，乙取数的目标是使得S乙尽可能大。
若甲乙都是最优取法，那么S甲和S乙是多少？
S甲和S乙 肯定和这N个数以及它们的排列顺序有关。
------------------------------------------------------------------------------------------------------------
我想编程让电脑来寻找，最后输入这一串数字，电脑自动给出最优的取法和结果。
但考虑了很久，觉得难以入手，虽然有一点眉目，但觉得非常的麻烦，执行速度估计会让人难受。
现在想征求大家的意见，给出好的思路、好的点子，大家一起探讨一下程序设计方面应该如何入手才好！

yang_bigarm

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

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

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

lulijie

我的思路是穷举法，把所有的可能都让电脑计算一下，找出最优的取法。
两头取数给出的是18个数字，一个2^18-1=262143种取法。可以在电脑运算的忍耐速度之内。
但是如何从262143种取法选出甲乙都是最优的取法并不容易。显然比较这262143种取法的S甲-S乙哪个值最大，是不行的，因为乙有选择权。

kexin_xiao

只能有电脑计算吗?

Cielo

原帖由 lulijie 于 2009-4-3 21:16 发表
我的思路是穷举法，把所有的可能都让电脑计算一下，找出最优的取法。
两头取数给出的是18个数字，一个2^18-1=262143种取法。可以在电脑运算的忍耐速度之内。
但是如何从262143种取法选出甲乙都是最优的取法并不容易 ...

穷举肯定不行，怎么说也得用递归吧……

不过我对算法和程序设计很不在行，所以没办法啊，希望有高手解答，而不要总是等着看现成的答案

zxl0714

算法设计起来并不难，这道题应该是用动态规划。用f( i, j )来表示第i个数到第j个数的先拿的人能拿到的最大值，这样有状态转移方程f( i, j ) = max{ sum( i, j ) - f( i + 1, j ), sum( i, j ) - f( i, j - 1 ) }，sum( i, j )表示第i个数到第j个数的和，这样就可以递推了。

zxl0714

如果n是偶数，谁先手谁肯定不会输，因为先手的人必然可以取得所有奇数位置上的数或者偶数位置上的数。当n是奇数的时候就没那么简单了。

lulijie

我觉得递推方程应该是如下：
            f( i, j ) 表示   从数列第i个数到第j个数的排列，双方最优取法下 S先-S后的值。
         那么     f( i, j ) =  max{  a( i) - f( i + 1, j )  ，a(  j ) - f( i, j - 1 )  } ，       a(i)表示原数列第i个数。
递推公式有了，那么从哪里开始递推呢？也就是说初始的i，j等于多少呢？

zxl0714

楼上的递推公式显然错了。
首先当i等于j的时候f( i, j )可以确定，可以从这里出发，自底向上，也可以用递归自顶向下。

lulijie

楼上的我还理解不了，
就拿以下数列
47，30，1，47，2，30，45，7，37，82，9，97，48，32，78，92，74，83
楼上举例说明一下。