C语言的取石头游戏,----超高难度的算法题
C语言的取石头游戏,----超高难度的算法题


有甲乙两个人玩取石子游戏,共有n个石子(1 <=n <=30000)两个人轮流取,甲先取.每次最多取m个(1 <=m <=30000)最少取一个,当轮到谁取的时候没有石子了,谁就赢.
比如4个石子,每次最多取3个,那末先取的人(甲)一定赢n和m谁大没有限制.)
(甲拿走3个,乙只拿走1个,下面轮到甲了,但是没有石子了,甲赢了．）
　现在要求你写一个程序，输入n(总的石子个数），最多可以取的石子个数m，输出甲（先取的人）是否会赢，会赢的话输出YES,否则输出LOSE.
　我们这里假设甲乙两个人都采取最好的策略，也就是甲乙都非常想赢而且足够聪明．
　比如输入４　３　输出YES

请教高手

[解决办法]
可以这么做，假设f(n,m)计算出在有n个石子，每次可以取[1,m]个的情况下，先取的人是否一定可以赢。如果f(n,m)返回真，那么意味着存在一个方案，使得先取的人取t个并且f(n-t,m)为假。因此可以这样计算f
bool f(int n, int m)
{
int i = (n - m > 0 ? n - m : 1);

while (i < n && f(i, m))
i++;

return i == n ? false : true;
}
这个算法的复杂度很高，采用迭代的方式可以获得线性的复杂度，代码如下
#include <stdio.h>
#include <stdlib.h>

int S[30001] = {-1}; //每一个S[i]相当于f(i, m)，这里忽略了S[0]

void stone (int n, int m)
{
int lose = 1;

S[1] = 0;
for (int i = 2; i <= n; i++)
{
S[i] = (lose ? 1 : 0);

if (i - m > 0 && S[i - m] == 0)
--lose;

if (S[i] == 0)
++lose;
}
}

int main ()
{
stone (4, 3);

printf ( "%s ", (S[4] == 1 ? "YES " : "LOSE "));

system ( "pause ");
}
[解决办法]
n=100,m=98时应该返回LOSE吧，可是LS返回YES噢，我的代码：

#include <stdio.h>

#define MAXN 30000
int a[MAXN+1];

int DPfun(int n,int m)
{
int i,k;
if(n==1)
return false;
else if( m> =(n-1) )
return true;
else{
a[1]=0;
for(i=2;i <=(m+1);i++)
a[i]=1;
for(i=(m+2); i <=n; i++)
{
for(k=1;k <=m && a[i-k];k++);
if(k> m)
a[i]=0;
else
a[i]=1;
}
return a[n];
}
}

int main()
{
int n,m;
scanf( "%d %d ", &n,&m);
if(DPfun(n,m))
printf( "YES\n ");
else
printf( "LOSE\n ");

return 0;
}