找回密码
 欢迎注册
查看: 16258|回复: 3

[讨论] 取牌游戏

[复制链接]
发表于 2008-11-13 00:17:02 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
不知道有人做过没有。

有10张牌,分别写着1~10的数字,甲乙两人依下列规则游戏:
1. 甲开始任选一张牌,由乙决定该牌分给谁;
2.从第二次开始,由得到的牌面数字总和较大者在未分配牌中选择一张牌(如果两人总和相等,则仍由上次选牌者选牌),由另一人决定该牌给谁;
3.取完所有牌后,数字和大者为胜。

请问,谁有必胜策略?为什么?如果是1~N的N张牌,有没有一般性的解法?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-13 09:17:16 | 显示全部楼层
10张牌用计算机解倒是很简单(不一定要1~10的数字).N张牌显然可以用空间复杂度$O(2^N)$的算法解决.不过N大了就很难计算了.只是不知道如果是1~N这N张牌,是否有比较好的规律
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-13 11:22:02 | 显示全部楼层
编了一下,依据现在我的状态,不一定对哦。呵呵。
在L中dx表示和对方的分数差,last表示如果分数相等该谁拿,x表示桌面上剩下了哪些牌。这些信息表明了当前的状态,用函数p表示在此状态下的得分。
sb用来缓存已经计算过的p值,防止重复计算,但是貌似效率提升不大。呵呵。
结果是-1,就是说甲会输1分。
  1. #include <conio.h>
  2. int sb[111][2][1024];
  3. int init()
  4. {
  5.         int i,j,k;
  6.         for(i=0;i<111;i++)
  7.         for(j=0;j<2;j++)
  8.         for(k=0;k<1024;k++)
  9.                 sb[i][j][k]=1000;
  10.         return 0;
  11. }       
  12. int max(int *ps,int psn)
  13. {
  14.         int i,r;
  15.         r=ps[0];
  16.         for(i=1;i<psn;i++)if(ps[i]>r)r=ps[i];
  17.         return r;
  18. }
  19. int min(int *ps,int psn)
  20. {
  21.         int i,r;
  22.         r=ps[0];
  23.         for(i=1;i<psn;i++)if(ps[i]<r)r=ps[i];
  24.         return r;
  25. }
  26. struct L{int dx,last;unsigned x;};
  27. int p(struct L s)
  28. {
  29. //        printf("%X.",s.x);
  30.         struct L s1,s2;
  31.         unsigned k;
  32.         int i,psn,p1,p2,ps[10];
  33.         if(s.x==0)return s.dx;
  34.         p1=sb[s.dx+55][s.last][(int)s.x];
  35.         if(p1!=1000)return p1;
  36.         psn=0;
  37.         if(s.dx>0||(s.dx==0&&s.last==1))
  38.         {
  39.                 for(i=0;i<10;i++)
  40.                 {
  41.                         k=1<<i;
  42.                         if((k&s.x)!=0)
  43.                         {
  44.                                 s1.x=s.x&(~k);s2.x=s.x&(~k);s1.dx=s.dx+(i+1);s2.dx=s.dx-(i+1);s1.last=1;s2.last=1;p1=p(s1);p2=p(s2);
  45.                                 ps[psn++]=(p1<p2)?p1:p2;
  46.                         }
  47.                 }
  48.                 return max(ps,psn);
  49.         }
  50.         else
  51.         {
  52.                 for(i=0;i<10;i++)
  53.                 {
  54.                         k=1<<i;
  55.                         if((k&s.x)!=0)
  56.                         {
  57.                                 s1.x=s.x&(~k);s2.x=s.x&(~k);s1.dx=s.dx+(i+1);s2.dx=s.dx-(i+1);s1.last=1;s2.last=1;p1=p(s1);p2=p(s2);
  58.                                 ps[psn++]=(p1>p2)?p1:p2;
  59.                         }
  60.                 }
  61.                 return min(ps,psn);
  62.         }
  63. }

  64. int _tmain(int argc, _TCHAR* argv[])
  65. {
  66.         L s;
  67.         s.dx=0;s.last=1;s.x=0x3ff;
  68.         init();
  69.         printf("[%d]",p(s));
  70.         _getch();
  71.         return 0;
  72. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-11-13 12:21:52 | 显示全部楼层
其实很容易证明在总分为奇数时乙有必胜策略,问题就是乙的必胜解法有多复杂,能不能在实际的博弈中实现。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 05:16 , Processed in 0.043854 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表