取牌游戏
不知道有人做过没有。有10张牌，分别写着1～10的数字，甲乙两人依下列规则游戏：
1. 甲开始任选一张牌，由乙决定该牌分给谁；
2.从第二次开始，由得到的牌面数字总和较大者在未分配牌中选择一张牌（如果两人总和相等，则仍由上次选牌者选牌），由另一人决定该牌给谁；
3.取完所有牌后，数字和大者为胜。
请问，谁有必胜策略？为什么？如果是1～N的N张牌，有没有一般性的解法？ 10张牌用计算机解倒是很简单(不一定要1~10的数字).N张牌显然可以用空间复杂度$O(2^N)$的算法解决.不过N大了就很难计算了.只是不知道如果是1~N这N张牌,是否有比较好的规律:lol 编了一下，依据现在我的状态，不一定对哦。呵呵。
在L中dx表示和对方的分数差，last表示如果分数相等该谁拿，x表示桌面上剩下了哪些牌。这些信息表明了当前的状态，用函数p表示在此状态下的得分。
sb用来缓存已经计算过的p值，防止重复计算，但是貌似效率提升不大。呵呵。
结果是-1，就是说甲会输1分。#include <conio.h>
int sb;
int init()
{
int i,j,k;
for(i=0;i<111;i++)
for(j=0;j<2;j++)
for(k=0;k<1024;k++)
sb=1000;
return 0;
}
int max(int *ps,int psn)
{
int i,r;
r=ps;
for(i=1;i<psn;i++)if(ps>r)r=ps;
return r;
}
int min(int *ps,int psn)
{
int i,r;
r=ps;
for(i=1;i<psn;i++)if(ps<r)r=ps;
return r;
}
struct L{int dx,last;unsigned x;};
int p(struct L s)
{
// printf("%X.",s.x);
struct L s1,s2;
unsigned k;
int i,psn,p1,p2,ps;
if(s.x==0)return s.dx;
p1=sb[(int)s.x];
if(p1!=1000)return p1;
psn=0;
if(s.dx>0||(s.dx==0&&s.last==1))
{
for(i=0;i<10;i++)
{
k=1<<i;
if((k&s.x)!=0)
{
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);
ps=(p1<p2)?p1:p2;
}
}
return max(ps,psn);
}
else
{
for(i=0;i<10;i++)
{
k=1<<i;
if((k&s.x)!=0)
{
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);
ps=(p1>p2)?p1:p2;
}
}
return min(ps,psn);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
L s;
s.dx=0;s.last=1;s.x=0x3ff;
init();
printf("[%d]",p(s));
_getch();
return 0;
}
其实很容易证明在总分为奇数时乙有必胜策略，问题就是乙的必胜解法有多复杂，能不能在实际的博弈中实现。
页:
[1]