当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

编程之美-NIM游戏分析-石头总数为奇数时如何保证先动手者必胜

发表于: 2012-07-23   作者:bylijinnan   来源:转载   浏览:
摘要: import java.util.Arrays; import java.util.Random; public class Nim { /**编程之美 NIM游戏分析 问题: 有N块石头和两个玩家A和B,玩家A先将石头随机分成若干堆,然后按照BABA...的顺序不断轮流取石头, 能将剩下的石头一次取光的玩家获胜,每次取石头时,每个玩家只能从若干堆石头中任选一堆,


import java.util.Arrays;
import java.util.Random;

public class Nim {

	/**编程之美 NIM游戏分析
问题:
有N块石头和两个玩家A和B,玩家A先将石头随机分成若干堆,然后按照BABA...的顺序不断轮流取石头,
能将剩下的石头一次取光的玩家获胜,每次取石头时,每个玩家只能从若干堆石头中任选一堆,
取这一堆石头中任意数目(大于0)个石头。
请问:
玩家A要怎样分配和取石头才能保证自己有把握取胜?

1.如果石头的个数N为偶数,A只要将其分为相同的两份,就一定能取胜。
初始:XOR(M1, M1) == 0
玩家B:XOR(M1, M2) != 0  (其中一堆的个数减少到M2)
玩家A:XOR(M2, M2) == 0  (玩家A将另一堆的个数也减少到M2)
结果:XOR(M2, M2) == 0  (直到结束状态(0, 0))

2.如果石头的个数N为奇数,B有必胜的方法。
初始:XOR(M1, M2, ... , Mn) != 0
玩家B:XOR(M1, ... , Mi', ... , Mn) == 0 (其中一堆Mi的个数减少到Mi')
玩家A:XOR(M1, ... , Mj', ... , Mn) != 0
玩家B:XOR(M1, ... , Mi', ... , Mn) == 0 (其中一堆Mi的个数减少到Mi')
结果:XOR(M1, ... , Mj' , ... , Mn) == 0 (直到结束状态(0,0))

这里就有个问题:已知XOR(M1, M2, ... , Mn) != 0,玩家B该改变那个Mi以使得XOR(M1, ... , Mi', ... , Mn) == 0呢

刚开始我的思路是基于以下结论:
1.Mi改变成Mi'后,如果数组可以分成和相等的两部分,那么数组所有元素异或的结果一定是0
--这个结论是错的,例如2^7^9=12,尽管9^(2+7)=0
2.Mi=max(M1,M2...Mn) 
--这也是错的。从max里面取走x块石头与非max里面取走x块石头,结果是不一样的
--例如(9,7,9),取走7块石头,有两种情况:XOR(9,0,9)=0; XOR(2,7,9)=12

正确的思路:
令xor=XOR(M1,M2,...Mi-1,Mi,Mi+1,...Mn);
Mi'=Mi^xor=XOR(M1,M2,...Mi-1,Mi+1,...Mn)
那么XOR(M1,M2,...Mi-1,Mi',Mi+1,...Mn)=0
	 */
	public static void main(String[] args) {
		int numOfHeap=5;	//石头堆数
		for(int i=0;i<10;i++){		//测试10次
			int[] stones=generateStones(numOfHeap);
			process(stones);
			System.out.println("=================================");
		}
		
	}
	
	//当前石头总数为奇数时,如何取石头才能使自己必胜(即使异或结果为0)
	public static void process(int[] a){
		
		if(a==null||a.length<2){
			return;
		}
		
		int size=a.length;
		int xor=0;
		for(int i=0;i<size;i++){
			xor ^=a[i];
		}
		
		if(xor==0){		//数组和(石头总数)为奇数,则不管怎么分堆,分堆的异或结果一定不是0。其他情况不在本次讨论范围内
			return;
		}
		
		int i=0;
		int diff=0;
		int mi=0;
		for(;i<size;i++){
			mi=a[i]^xor;
			if(a[i]>=mi){
				diff=a[i]-mi;
				break;
			}
		}
		
		System.out.println(Arrays.toString(a));
		System.out.println("now you should take "+diff+" stones from a["+i+"]="+a[i]);
		
		//验证一下现在异或结果是不是0
		a[i]=mi;	//取走石头
		xor=0;
		for(int x:a){
			xor ^=x;
		}
		System.out.println("XOR"+Arrays.toString(a)+"="+xor);
		
	}
	
	private static Random random=new Random();
	
	//产生指定堆数的石头数组,且保证石头总数为奇数
	public static int[] generateStones(int numOfHeap){
		if(numOfHeap<2){
			return new int[0];
		}
		int[] stones=new int[numOfHeap];
		int sum=0;
		for(int i=0;i<numOfHeap;i++){
			stones[i]=random.nextInt(10)+1;
			sum +=stones[i];
		}
		if(sum%2==0){	//保证石头总数为奇数
			stones[0] +=1;
		}
		return stones;
	}
}

编程之美-NIM游戏分析-石头总数为奇数时如何保证先动手者必胜

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
编程之美电子书下载 24点游戏大家都知道:4张牌,可以进行+ - * / 四种运算,可以使用括号,每个牌
题目: 解法: 总体来说算法分为三步: 1.遍历A的坐标。 2.遍历B的坐标。 3.判断A,B是否在一条直线。
《编程之美》读书笔记(七):数独游戏解析 前言:说实话,所有游戏都是有一定规律可循的,只要掌握游
《编程之美》读书笔记(六):连连看游戏设计 作者:薛笛 联系方式:jxuedi(Gmail邮箱--@gmail.com)
《编程之美》读书笔记(七):数独游戏解析 前言:说实话,所有游戏都是有一定规律可循的,只要掌握游
NIM(3)两堆石头的游戏 1. 问题描述 假设有两堆石头,有两个玩家会根据如下的规则轮流取石头:每人
3、题目:能否快速找出一个数组(简单起见,数组中元素值各不一样)中的两个数字,让这两个数字之和
今天开始看编程之美 。第一个问题是CPU的使用率控制,微软的问题果然高大上,我一看就傻了,啥也不
转自:http://blog.csdn.net/zhuhuiby/article/details/6742980 题目如下: 阅读以下C#代码,回答问
第一章 软件架构是什么 软件架构应该... asoftware architect that the system should be friendly
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号