【HDU-5973】Game of Taking Stones【威佐夫博弈】

【HDU-5973】Game of Taking Stones【威佐夫博弈】

Solution:

直接根据威佐夫博弈的定理,两堆数量之差乘上黄金分割比等于数量少的那堆的个数,先手必输,反之先手必胜。

求解黄金分割比使用公式\(\frac{\sqrt{5} – 1}{2}\),关于\(\sqrt{5}\)的求解,等价于求解函数\(f(x) = x^2 – 5\)与横坐标轴的正值交点的横坐标,显然\(\sqrt{5}\)就是上面所述问题的解,但是我们现在需要一个浮点数值,也就是一定精度下根号的浮点近似值,可以使用二分法(基于介值定理,我们知道如果在一个区间内有根,这个区间的左右端点函数值之积一定小于零),还可以使用牛顿迭代法,它的收敛速度会比二分法快,但是有时牛顿迭代法比二分法更容易出现不收敛的情况,不过对于当前函数是不存在这个问题的,因为我们确定要找的根在0到5的区间内,并且这个函数显然在这个区间内单调递增,因此选取初始值5可以确保函数值收敛到我们想要的位置上。

牛顿迭代法公式:\(x_n = x_{n – 1} – \frac{f(x_{n – 1})}{f'(x_{n – 1})}\)。

代码:

import java.util.Scanner;
import java.math.BigDecimal;

public class Main {
    private static final BigDecimal EPS = new BigDecimal("0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001");
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        BigDecimal sqrt5 = sqrtNewtownMethod("5");
        BigDecimal goldNum = sqrt5.add(BigDecimal.valueOf(1)).divide(BigDecimal.valueOf(2));
        while (in.hasNext()) {
            BigDecimal a = in.nextBigDecimal();
            BigDecimal b = in.nextBigDecimal();
            if (a.compareTo(b) > 0) {
                BigDecimal t = a;
                a = b;
                b = t;
            }
            BigDecimal c = b.subtract(a).multiply(goldNum);
            if (c.setScale(0, BigDecimal.ROUND_FLOOR).compareTo(a) == 0)
                System.out.println("0");
            else
                System.out.println("1");
        }
    }
    private static BigDecimal sqrtNewtownMethod(String b) {
        BigDecimal two = BigDecimal.valueOf(2);
        BigDecimal num = new BigDecimal(b);
        BigDecimal pre = new BigDecimal(b);
        BigDecimal crt = new BigDecimal("0");
        while (true) {
            // System.out.println(pre.subtract(pre.multiply(pre).subtract(num).divide(two.multiply(pre))));
            crt = pre.subtract(pre.multiply(pre).subtract(num).divide(two.multiply(pre), 102, BigDecimal.ROUND_FLOOR));
            if (crt.subtract(pre).abs().compareTo(EPS) < 0) break;
            pre = crt;
        }
        return crt;
    }
}