魔方吧·中文魔方俱乐部

标题: 探讨“ 两头取数的问题” 的程序设计思路 [打印本页]
作者: lulijie    时间: 2009-4-3 20:49:22     标题: 探讨“ 两头取数的问题” 的程序设计思路

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

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

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

正是因为有了前面的一堆东西，才有了两头取数的这个问题，不过这里我先不说答案，让大家讨论。
说不定有别的方法哦。
作者: lulijie    时间: 2009-4-3 21:16:57

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

只能有电脑计算吗?
作者: Cielo    时间: 2009-4-3 22:39:57

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


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

不过我对算法和程序设计很不在行，所以没办法啊，希望有高手解答，而不要总是等着看现成的答案
作者: zxl0714    时间: 2009-4-4 00:02:12

算法设计起来并不难，这道题应该是用动态规划。用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    时间: 2009-4-4 00:17:05

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

我觉得递推方程应该是如下：
            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    时间: 2009-4-4 00:34:12

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

楼上的我还理解不了，
就拿以下数列
47，30，1，47，2，30，45，7，37，82，9，97，48，32，78，92，74，83
楼上举例说明一下。
作者: zxl0714    时间: 2009-4-4 11:45:44

楼上那个数列，举几个例子。
f( 1, 1 ) = 47，f( 2, 2 ) = 30，f( 3, 3 ) = 1，因为只有一个数先拿者必拿到这么多。
f( 1, 2 ) = max{ 47 + 30 - f( 1, 1 ), 47 + 30 - f( 2, 2 ) } = 47
f( 2, 3 ) = max{ 30 + 1 - f( 2, 2 ), 30 + 1 - f( 3, 3 ) } = 30
f( 1, 3  ) = max{ 47 + 30 + 1 - f( 1, 2 ), 47 + 30 + 1 - f( 2, 3 ) } = 48
这样一直推到f( 1, n )就是先拿的人在双方不出错的情况下所能拿到的最大数值。
作者: zxl0714    时间: 2009-4-4 12:12:30

  1. #include <cstdio>

  3. int min( int a, int b ) { return ( a < b )? a: b; }

  5. int main( )
  6. {
  7.         int a[ 101 ], f[ 101 ][ 101 ], n, i, j, sum[ 101 ];
  8.         scanf("%d", &n);
  9.         for ( i = 1; i <= n; i++ )
  10.                 scanf("%d", &f[ i ][ i ]);
  11.         sum[ 0 ] = 0;
  12.         for ( i = 1; i <= n; i++ )
  13.                 sum[ i ] = sum[ i - 1 ] + f[ i ][ i ];
  14.         for ( i = 1; i < n; i++ )
  15.                 for ( j = 1; j + i <= n; j++ )
  16.                         f[ j ][ i + j ] = sum[ i + j ] - sum[ j - 1 ] - min( f[ j + 1 ][ i + j ], f[ j ][ i + j - 1 ] );
  17.         printf("%d\n", f[ 1 ][ n ]);
  18.         return 0;
  19. }
复制代码
程序写起来很简单
作者: 金眼睛    时间: 2009-4-4 13:57:41

受zxl0714的启发，提一点对于奇数项数数列甲乙二人的取数策略，抛砖引玉，大家讨论一下。

定义：当数列项数为偶数时，奇数项之和与偶数项之和差值的绝对值设为该数列的“益差”，如果“益差”为正，设较大的和为该数列的收益，先取数的人可以通过只取奇（或偶）数项来获得这个收益。

奇数项数数列，甲先取，甲的策略如下：将甲取到的值减去剩下数列的“益差”，记为Aa（可以为负），取Aa大的一边来取，如果两边Aa相等，可以取前后两项中较大的数，如果这种情况下前后两项还相等，那就任意选一边。

甲取完之后乙的策略：乙面对的是偶数项数数列，初始的时候可以设定收益期望为该数列的收益Ab，这时该选哪一边的数也确定了（注意这个数只跟奇偶项有关，不一定较大），设这个数为b，然后其收益期望调整为Ab-b。之后轮到甲取数，双方的策略没有耦合关系，甲取完后，又轮到乙取数了，乙这个时候要重新评估一下剩下的偶数项数数列，如果发现其收益大于Ab-b，则重置取数策略，否则继续按原来的奇数项或偶数项来取。

[ 本帖最后由 金眼睛 于 2009-4-4 14:00 编辑 ]
作者: lulijie    时间: 2009-4-4 18:34:05

哈哈，6楼的 f( i, j ) 表示  从数列第i个数到第j个数的排列，双方最优取法下 S先 的值。
而我的 f( i, j ) 表示从数列第i个数到第j个数的排列，双方最优取法下 S先-S后的值。
-------------------------------------------------------------------------------------------------------
定义不同，所以递推公式也不同。
我的递推公式也是正确的。
用我自己的递推公式已经算出yang_bigarm的贴 两头取数的问题 中举的例子的双方最优的取法。
已公布在两头取数的问题 的贴中，大家验证一下我解出的答案对不对。
作者: zxl0714    时间: 2009-4-4 20:08:05

你解的答案是对的，你的状态和我的状态定义不同是我看漏了，不过我不得不说你这个状态的定义有点复杂了。
作者: lulijie    时间: 2009-4-4 20:23:41

很对，楼上的定义：     f( i, j ) = max{ sum( i, j ) - f( i + 1, j ), sum( i, j ) - f( i, j - 1 ) }
               可化简为    f( i, j )=sum( i, j ) -  min{ f( i + 1, j ), f( i, j - 1 ) }
          应该更简单些。
作者: zxl0714    时间: 2009-4-4 20:33:39

是的，我的程序就是这么写的
作者: lulijie    时间: 2009-4-4 21:11:38

但是我用两种方法都试了一下，解    47 30 1 47 2 30 45 7 37 82 9 97 48 32 78 92 74 83
我的方法 3秒，
你的方法 4秒。
好像你的方法并不比我的快啊。
作者: Cielo    时间: 2009-4-4 21:41:46

原帖由 lulijie 于 2009-4-4 21:11 发表
但是我用两种方法都试了一下，解    47 30 1 47 2 30 45 7 37 82 9 97 48 32 78 92 74 83
我的方法 3秒，
你的方法 4秒。
好像你的方法并不比我的快啊。


呵呵都是强人，佩服！
作者: zxl0714    时间: 2009-4-4 21:42:46

同是O(n^2)的算法，可以算一样长，但是为什么你这个计算的这么慢，这组数据n=18，我敢说肯定0,01秒内就能出解。
作者: lulijie    时间: 2009-4-4 21:56:26

我觉得是O(2^n)的算法。
确定第一步有2个取法，再确定第二步也是2种取法，一共要18步，所以是2^18-1种方法。
作者: zxl0714    时间: 2009-4-4 22:01:40

看来你还没有理解啊。。。。。
动态规划的主要思想就是避免重复计算，你可以这么想，为了确定第1步我们要计算出所有的来比较，第2步我们就不用再计算了，因为第1步已经计算过了。
作者: lulijie    时间: 2009-4-4 22:06:40

有道理，我要好好想想。
你试过没有，要费多少时间？我要尽量向你的目标靠拢。
作者: zxl0714    时间: 2009-4-4 22:15:39

我贴个伪码
  1. input n
  2. sum( 0 ) := 0
  3. for i := 1 to n
  4. begin
  5.         input a( i )
  6.         f( i, i ) := a( i )
  7.         sum( i ) := sum( i - 1 ) + a( i )
  8. end
  9. for i := 1 to n
  10.         for j := 1 to n
  11.                 f( j, i + j ) = sum( i + j ) - sum( j - 1 ) - min( f( j + 1, i + j ), f( j, i + j - 1 ) )
  12. print f( 1, n ), sum( n ) - f( 1, n )        //f( 1, n )是S甲，sum( n ) - f( 1, n )是S乙

  14. //下面开始输出每个数第几次被取走
  15. start := 1
  16. end := n
  17. for i := 1 to n
  18. begin
  19.         if f( start + 1, end ) < f( start, end - 1 )
  20.         begin
  21.                 p( start ) := i
  22.                 start := start + 1
  23.         end
  24.         else
  25.         begin
  26.                 p( end ) := i
  27.                 end := end - 1
  28.         end
  29. end
  30. for i := 1 to n
  31.         print p( i )
复制代码
作者: zxl0714    时间: 2009-4-4 22:21:07

对于那个样例是0.000s，对于1000个数是0.031s，大部分时间是耗在了打印那1000个数是第几个被取走。
作者: yang_bigarm    时间: 2009-4-4 22:46:13

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


all, right! 正解！

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

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

递归其实就是一个栈，完全可以自己用栈来模拟递归，这样就把递归变成循环了。但是这样会比较麻烦，所以我一般都是写递归，但是递归的最大缺陷就是有可能会造成栈溢出，而且时间效率比循环稍低。
我一般把记录中间过程的递归叫做“记忆化搜索”，如果不带记忆其实就是一个dfs搜索算法。
作者: lulijie    时间: 2009-4-4 23:20:19

我知道它的精髓了。重新设计一下，运行结果如下：
先手方赚：189
取数顺序：18 17 16 15 1 14 2 13 12 11 10 9 8 7 6 5 4
花费时间：0秒
作者: lulijie    时间: 2009-4-4 23:28:20

哈哈，3600个数组成的数列，2秒解出最优取法。
先手方赚：27934
取数顺序：1 2 3600 3599 3598 3597 3596 3595 3594 3593 3592 3591 3590 3589 3588 3587 3586 3585 3584 3583 3582 3581 3580 3579 3578 3577 3576 3575 3574 3573 3572 3571 3570 3569 3568 3567 3566 3565 3564 3563 3562 3561 3560 3559 3558
......... ......
106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4
花费时间：1.99999983888119秒
作者: lulijie    时间: 2009-4-4 23:29:33

跟高手们确实学到很多，受益匪浅啊!



欢迎光临 魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/) Powered by Discuz! X2