取牌游戏

好地方

不知道有人做过没有。 有10张牌，分别写着1～10的数字，甲乙两人依下列规则游戏： 1. 甲开始任选一张牌，由乙决定该牌分给谁； 2.从第二次开始，由得到的牌面数字总和较大者在未分配牌中选择一张牌（如果两人总和相等，则仍由上次选牌者选牌），由另一人决定该牌给谁； 3.取完所有牌后，数字和大者为胜。 请问，谁有必胜策略？为什么？如果是1～N的N张牌，有没有一般性的解法？

mathe

10张牌用计算机解倒是很简单(不一定要1~10的数字).N张牌显然可以用空间复杂度$O(2^N)$的算法解决.不过N大了就很难计算了.只是不知道如果是1~N这N张牌,是否有比较好的规律

zgg___

编了一下，依据现在我的状态，不一定对哦。呵呵。 在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. }
65. int _tmain(int argc, _TCHAR* argv[])
66. {
67. L s;
68. s.dx=0;s.last=1;s.x=0x3ff;
69. init();
70. printf("[%d]",p(s));
71. _getch();
72. return 0;
73. }

复制代码

好地方

其实很容易证明在总分为奇数时乙有必胜策略，问题就是乙的必胜解法有多复杂，能不能在实际的博弈中实现。