第二弹，博弈游戏与动态规划

题目描述：

Alice 和 Bob 在玩取石子游戏，每次只能取1或素数，规定每次都是Alice 先取，最后一个把石子取光的人获胜，假设两个人都足够聪明。

输入格式：

有多组测试数据。输入多组测试数据，每次只输入一个整数n（n<=1,000,000)

输出格式：

每行输出每次获胜的人。

Example input

1 3

Example output

Alice

Alice

解题思路：

由数学归纳法可以证明，只要输入的数n不是4的倍数，那么Alice获胜，否则，Bob获胜。

但是，没有灵感怎么推出上面的结论呢？

我尝试用动态规划来做这道题，尽管这会运行效率很低，但是你可以打印出一些数据，根据数据推结论也不失为一个可行的办法。

考虑用1表示Alice胜利，0表示Alice失败。

d【n】表示共有n个石子，最后哪一个人获胜。

显然如果n是素数，Alice获胜，d【n】=1；

否则的话，如果d【n-prime（i）】能到达某个Alice的必败态，那么Alice必胜，否则，Alice必败。

这是为什么呢？

首先，我们考虑我们说的胜利与失败的前提是什么？

我们假定好了Alice先取，Bob后取，所以我们得出了必胜的结论。

但此时，我们取了某个素数后，剩下的数如果是某个我们以知道的Alice的必败态，那么，由于此时Alice与Bob的操作顺序与必败态是的操作顺序相反，（因为上一次是Alice取的），那么可以肯定的是，Alice必胜。否则，Alice必败，因为Alice无论怎么取，她到达的地方都是必胜态，但此时都变成了必败态。

所以核心的动态方程为

if （n是素数） d【n】=1；

else

if d【n-prime(i)】==0 

then d【n】=1；

else d【n】=0；

代码如下：

#include <iostream>
#include <cmath>

using namespace std;

bool isprime(int num){		//判断素数 
	int root = sqrt(num);
	for(int i=2;i<=root;i++){
		if(num%i==0) return false;
	}
	return true;
} 

int prime[101000];
int d[1000010]; 

void create(){				//建立素数数组 
	int count=100000;
	int num=2;
	int p=1;
	prime[0]=1; 			//包含1 
	while(count>0){
		if(isprime(num)){
			count--;
			prime[p++]=num;
		}
		num++;
	}
}

void getresult(int n){		//得到结果 
	d[1]=1;
	for(int i=2;i<=n;i++){
		if(isprime(i)) {			//如果是素数，直接先取获胜 
			d[i]=1;
			continue;
		}
		for(int j=0;j<=1000000;j++){
			if(d[i-prime[j]]==0 && i-prime[j]>0){		//假如前面有某个状态为必败态d[i-prime[j]]=0，那么d[i]必胜 
				d[i]=1;
				break;
			}
		}								//如果找不到，必败（全局数组自动初始化为0） 
	}
	if(d[n]==1) cout<<"先手赢";
	else	cout<<"后手赢"; 
}

int main(){
	int n;
	create();
	while(cin>>n){
		getresult(n);
		cout<<endl;
	}
	for(int i=1;i<=n;i++){		//打表 
		cout<<d[i]<<‘,‘;
		if(i%12==0){
			cout<<endl;
		}
	}
}

第二弹，博弈游戏与动态规划

原文：http://blog.csdn.net/xhy4930633490/article/details/18418183