数学问题

巧用进制

1. 一堆不重复的砝码重量为1,3,9...3^n,用他们的组合可以称出任意重量，给定一个重量，给出砝码组合方案。 思路：砝码的重量为3的指数幂，将其转为3进制 1,10,100,1000...可以将1看成是需要砝码，0看成不需要砝码，那么101 可以看成需要一个9和1的砝码 所以可以试着将所称重量转成三进制，那么接下来要做的是处理出现2的位置，对于这种情况，可以对该位置加1，那么即可发生进位，而在原位留下-1表示减去相应的一个砝码，例如 121 可以转化为 2 -1 1 -> 1 -1 -1 1 即27-9-3+1

	private void printWeight(int a) {
		String s = Integer.toString(a, 3);
		char[] chars = new StringBuilder(s).reverse().toString().toCharArray();
		boolean overFlow = false;
		List<Integer> arr = new LinkedList<>();
		for (int i = 0; i < chars.length; i++) {
			if (chars[i] == '2'){
				arr.add(-1);
				if (i==chars.length -1){
					overFlow = true;
				}else {
					chars[i+1]+=1;
				}
			}else if (chars[i] == '3'){
				arr.add(0);
				if (i==chars.length -1){
					overFlow = true;
				}else {
					chars[i+1]+=1;
				}
			}else {
				arr.add(chars[i]-'0');
			}
		}
		if (overFlow){
			arr.add(1);
		}
		int t =(int) Math.pow(3,arr.size()-1);
		System.out.print(t);
		for (int i = arr.size()-2; i >=0;i--) {
			t = t/3;
			if (arr.get(i) == 1){
				System.out.print('+');
				System.out.print(t);
			}
			if (arr.get(i) == -1){
				System.out.print(-t);
			}
		}
	}

2. 一共有N堆石子 N>1，编号编号1...N 甲乙两人每次可以拿走任意一堆中任意数量的石子，甲乙轮流行动，最后取光石子的人获胜。 甲为先手，给定这样的石子堆，假设两人都使用最优策略，请问谁获胜。 思路：将每堆石子数目都转成二进制，然后进行异或，如果结果非0,那么先手的人总能改变其中一堆的数目使得结果为0，那么另一个人无论怎么取，剩余石子堆异或结果都不会是0，知道最后一次使得异或结果为0时取完石子。 即：异或不为0 ，先手赢，异或为0，后手赢。