博弈论 硬币游戏1

按照我们常人的想法，当前状态有三种状态 必胜，必败，或者不确定；当对了两个聪明的人来说就只有两种情况：必胜，必败；下面请看必胜态，必败态的解释；

必败态：有x枚硬币，有a[0]~a[k-1]中取法，当前不管你按那种取法取，都在人家的掌控之中，都得按照人家的节奏来，因为人家和你都是一样聪明；也就是说x-a[i] (0<=i

必胜态：当前取的人，按照自己聪明的想法取，他取过之后能使得对方不管按那种方法取，都赢不了，也就是说对方不管按那种方法取，剩下的硬币数，还是必胜态，也就是说只要自己一直按照聪明的想法取，不管对方多么聪明都无计可施；

当前为x枚硬币

当x==0时，为必败态；

当x>0时

若对于某个i （0<=i=0）x-a[i] 为必败态，那么x是必胜态；

若对于任意的i（0<=i=0）x-a[i]为必胜态，那么x就是必败态；

写程序，算是用了动态规划的思想，从小到大推出是必胜态，还是必败态；

代码：

#include
#include
#include
using namespace std;
#define Max 10010
bool win[Max];
int main()
{int i,j,x,k;int a[110];while(~scanf("%d%d",&x,&k)){for(i=0;i=a[i])win[j] |= !win[j-a[i]]; //表述法一：当j>=a[i]时，只要有一个a[i],使得j-a[i]为必败态，那么j就为必胜态；//if(j>=a[i]&&!win[j-a[i]])   // 表述法二：和上面一样； //	win[j] = true;/*if(j>=a[i])        //表述法三： { if(win[j-a[i]])continue;else break;}*/		}/*if(i>=k) win[j] = false;  // 取任意一种情况，剩下的都为必胜态，此时就为必败态； else win[j] = true;       // 只要有一种情况取后，剩下的为必败态，那么此时就是必胜态（一直按照自己聪明的想法取）*/}if(win[x]) printf("Alice\n");else printf("Bob\n");}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！