2016大连站 hdu5973 Game of Taking Stones(Java高精度+威佐夫博弈+牛顿迭代)

题目

威佐夫博弈裸题，两堆石子(a,b)，1<=a,b<=1e100

问能否先手必胜，能输出1，否则输出0

思路来源

https://blog.csdn.net/Li_Yufeng/article/details/78044019?utm_source=blogxgwz9 牛顿迭代的题解

https://blog.csdn.net/Young_12138/article/details/71074765 二分答案的题解

https://www.cnblogs.com/zwfymqz/p/8469863.html 威佐夫博弈原理

https://blog.csdn.net/xiaoyu714543065/article/details/8656177 高精度 小数位数异常

https://www.zhihu.com/question/20690553/answer/146104283 牛顿迭代原理

https://zhuanlan.zhihu.com/p/64728645?utm_source=qq&utm_medium=social&utm_oi=1009214313768173568 Leetcode牛顿迭代代码

题解

威佐夫博弈，

当局面为时，先手必败，否则先手必胜

牛顿迭代搞出sqrt开根函数，求出，用高精度的函数判断即可

关于牛顿迭代

一般用于求二次方程的解，适用函数有局限性，

原理：https://www.zhihu.com/question/20690553/answer/146104283 

基础应用：https://zhuanlan.zhihu.com/p/64728645?utm_source=qq&utm_medium=social&utm_oi=1009214313768173568

此处用于求，求x的过程，令，则

先找到零点右侧的解（一定要选好初值），则每次向左迭代，直到零点，

只能从一侧向零点迭代，选左侧也可，

本次取的横坐标为，则下一次取的横坐标，

二次方程这里化简得，

简易代码

以下代码，用于求的x的整数部分

来自https://zhuanlan.zhihu.com/p/64728645?utm_source=qq&utm_medium=social&utm_oi=1009214313768173568

class Solution {
    public int mySqrt(int x) {
        if(x == 1 || x == 0)
            return x;
        int a = x >> 1;
        while(a > x / a){
            a = (a + x/a) / 2;
        }
        return a;
    }
}

代码

import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.*;

public class Main {
	public static BigDecimal sqrt(BigDecimal a, int d) {
		BigDecimal one = new BigDecimal("1");
		BigDecimal two = new BigDecimal("2");
		BigDecimal eps = one.divide(new BigDecimal(10).pow(d));
		if (a.abs().compareTo(eps) < 0)
			return new BigDecimal("0");
		BigDecimal dif = a.subtract(one);
		if (dif.abs().compareTo(eps) < 0)
			return one;
		BigDecimal ans = a.divide(two, d, BigDecimal.ROUND_HALF_EVEN);
		while (ans.multiply(ans).subtract(a).compareTo(eps) > 0) {
			ans = (ans.add(a.divide(ans, d, BigDecimal.ROUND_HALF_EVEN)));
			ans = ans.divide(two);
		}
		return ans;
	}

	public static void main(String[] args) {
		Scanner cin = new Scanner(new BufferedInputStream(System.in));
		PrintWriter cout = new PrintWriter(System.out);
		BigDecimal a, b, c, gold;
		BigDecimal one = new BigDecimal("1");
		BigDecimal two = new BigDecimal("2");
		BigDecimal five = new BigDecimal("5");
		BigDecimal eps = one.divide(new BigDecimal("10").pow(50));
		gold = sqrt(five,100);
		gold = gold.add(one).divide(two);
		while (cin.hasNext()) {
			a = cin.nextBigDecimal();
			b = cin.nextBigDecimal();
			if (a.compareTo(b) > 0) {
				c = a;
				a = b;
				b = c;
			}
			b = b.subtract(a);
			b = b.multiply(gold);
			b = b.setScale(0,RoundingMode.FLOOR);
			if (b.subtract(a).abs().compareTo(eps)<0)
				System.out.println("0");
			else
				System.out.println("1");
		}
	}

}