c语言之取石子游戏（ACM题目.doc

c语言之取石子游戏（ACM题目） 在这个游戏中，我们需要从两堆石子中取石子，游戏规定，每次可以在任意的一堆中取走任意多的石子，也可以在两堆中同时取走相同数量的石子。我们的目标是让先取者获胜。 我们需要了解游戏的规则：游戏开始由两个人轮流取石子，每次可以采取两种不同的取法：一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。 在这个游戏中，我们可以发现一个规律：a 与 b 的差逐步增大（增量为 1），a 不能是前面计算的 b 值。因此，我们可以写出如下算法： 我们需要写出一个 Swap 函数，用于交换 two integer 的值： ```c void Swap(int *a,int *b){ int t; if(*a>*b) { t=*a; *a=*b; *b=t; } } ``` 然后，我们需要写出一个 Another 函数，用于计算 b 值： ```c int Another(int a){ int i,b=0,j,tem; int langth=1; int index=1; for(i=1;i<=a;i+=2) { for(j=i;j<langth+i;j++) { b=j+index; index++; tem=j; if(j==a) break; } i=tem; langth++; } return b; } ``` 我们可以写出 main 函数，用于读取输入，计算 b 值，并输出结果： ```c void main(){ int a,b,n,num,i; int index=0,*p; scanf("%d",&n); num=n; p=malloc(sizeof(int)*n); while(n--) { scanf("%d%d",&a,&b); if(a>b) Swap(&a,&b); if(b==Another(a)) p[index++]=0; else p[index++]=1; } for(i=0;i<num;i++) printf("%d\n",p[i]); } ``` 在这个算法中，我们首先读取输入，交换 a 和 b 的值，使得 a 小于等于 b。然后，我们计算 b 值，使用 Another 函数。如果 b 值等于 Another 函数的返回值，则输出 0，否则输出 1。 这个游戏的关键是找到规律，使用递推的方法计算 b 值。通过这个算法，我们可以快速计算出 b 值，并输出结果。 在这个游戏中，我们可以看到，先取者的胜算是比较大的，我们可以通过计算 b 值，来确定先取者的胜算。这个游戏也可以用于研究策略和算法的应用。