取石子游戏(bash&wythoff&nim).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <cstdlib>
#include <time.h>

void bash_game()
{
	int n,m,t;
	printf("bash game begin\n");
	srand(time(NULL));
	printf("一堆有n个石子，两人轮流取物，至少1个，最多m个，取光者胜利\n");
	printf("n = ");
	scanf("%d",&n);
	printf("m = ");
	scanf("%d",&m);
	while (n) {
		printf("you get how much?\n");
		scanf("%d",&t);
		n -= t;
		if (n==0) {
			printf("you win\n");
			printf("========\n");
			break;
		}
		printf("remain %d\n",n);
		t = n%(m+1);
		if (t == 0) {
			t = rand()%m +1;
			srand(time(NULL));
		}
		n -= t;
		printf("com get %d, remain %d\n",t,n);
		if (n == 0) {
			printf("you lose\n");
			printf("========\n");
			break;
		}
	}
	
}

void wythoff_game()
{
	int n[2],m,t;
	int sg[210],k;
	memset(sg,0,sizeof(sg));
	k = 1;
	for (int i=1;i<=100;i++) {
		if (sg[i] == 0) {
			sg[i] = i+k;
			sg[i+k] = i;
			k++;
		}
	}
	printf("wythoff game begin\n");
	srand(time(NULL));
	printf("两堆石子n1，n2，两人轮流取物，可以从某一堆或同时从两堆取同样多的物品，数目不限，取光者胜利\n");
	printf("n1 = ");
	scanf("%d",&n[0]);
	printf("n2 = ");
	scanf("%d",&n[1]);
	while (n[0]+n[1] != 0) {
		printf("you get?\n");
		printf("1.only heap\n2.both heap\n");
		scanf("%d",&t);
		if (t==1) {
			printf("which heap do you selection?\n");
			scanf("%d",&k);
			printf("how much?\n");
			scanf("%d",&t);
			n[k-1] -= t;
		}
		else {
			printf("how much?\n");
			scanf("%d",&t);
			n[0] -= t;
			n[1] -= t;
		}
		if ((n[0]+n[1])==0) {
			printf("you win\n");
			printf("========\n");
			break;
		}
		printf("remain %d, %d\n",n[0],n[1]);
		
		int *sel;
		int *nmin,*nmax;
		if (n[0]>n[1]) {
			nmax = n;
			nmin = n+1;
		}
		else {
			nmin = n;
			nmax = n+1;
		}
		
		if (*nmin == *nmax) {//a == b
			sel = NULL;
			t = *nmin;
		}
		else if (*nmax > sg[*nmin]) {//b > bk
			sel = nmax;
			t = *nmax - sg[*nmin];
		}
		else if (*nmax < sg[*nmin]) {//b < bk
			int s = sg[*nmin] - *nmax;
			sel = NULL;
			for (int i=*nmin;i>=0;i--) {
				if (i < sg[i]) {
					s --;
				}
				if (s==0) {
					t = *nmin - i;
					break;
				}
			}
		}
		else if (*nmax == sg[*nmin]) {//b == bk
			sel = &n[rand()%2];
			t = rand()%(*sel) +1;
			srand(time(NULL));
		}
		
		if (sel == NULL) {
			n[0] -= t;
			n[1] -= t;
			printf("com get both heap %d, remain %d, %d\n",t,n[0],n[1]);
		}
		else if (sel == n) {
			*sel -= t;
			printf("com get the first heap %d, remain %d, %d\n",t,n[0],n[1]);
		}
		else {
			*sel -= t;
			printf("com get the second heap %d, remain %d, %d\n",t,n[0],n[1]);
		}
		
		if (n[0]+n[1] == 0) {
			printf("you lose\n");
			printf("========\n");
			break;
		}
	}
	
}

void nim_game()
{
	int n[3],m,t,k;
	printf("nim game begin\n");
	srand(time(NULL));
	printf("三堆有n个石子n1,n2,n3，两人轮流取物，从任意一堆中取至少1个，取光者胜利\n");
	printf("n1 = ");
	scanf("%d",&n[0]);
	printf("n2 = ");
	scanf("%d",&n[1]);
	printf("n3 = ");
	scanf("%d",&n[2]);
	while (n[0]+n[1]+n[2]) {
		printf("which heap do you selection?\n");
		scanf("%d",&k);
		printf("you get how much?\n");
		scanf("%d",&t);
		n[k-1] -= t;
		if (n[0]+n[1]+n[2]==0) {
			printf("you win\n");
			printf("========\n");
			break;
		}
		printf("remain %d, %d, %d\n",n[0],n[1],n[2]);
		
		int max,*nmax;
		int xor = n[0] ^ n[1] ^ n[2];
		max = n[0];
		nmax = n;
		for (int i=1;i<3;i++) {
			if (n[i] > max) {
				max = n[i];
				nmax = n+i;
			}
		}
		xor = xor ^ max;
		t = *nmax - xor;
		*nmax -= t;
		if (t == 0) {
			nmax = &n[rand()%3];
			t = rand()%(*nmax) +1;
			*nmax -= t;
			srand(time(NULL));
			printf("com get the %dth heap %d, remain %d, %d, %d\n",nmax-n+1,t,n[0],n[1],n[2]);
		}
		else {
			printf("com get the %dth heap %d, remain %d, %d, %d\n",nmax-n+1,t,n[0],n[1],n[2]);
		}
		if (n[0]+n[1]+n[2]==0) {
			printf("you lose\n");
			printf("========\n");
			break;
		}
	}
	
}

int main()
{
	int t;
	printf("请保证输入数据合法\n");
	while (scanf("%d",&t)==1) {
		switch(t) {
		case 1:
			bash_game();
			break;
		case 2:
			wythoff_game();
			break;
		default:
			nim_game();
		}
	}
}