【算法】排硬币 - 二分法/牛顿迭代

题目

假设有n枚硬币，要摆一个阶梯形，第一行1个，第二行2个，以此类推，看n枚硬币能摆多少行，返回行数。未摆满行的不算。

原理

二分法

先假设放 x 行需要 m 个硬币，用 m 与 n 对比，大于 n 则缩小 x，否则增大 x，直到算出结果。

牛顿迭代

1 + 2 + 3 + …… + x = (x * x + x) / 2 = n，所以 x = 2n - x 的平方根。求平方根可以用牛顿迭代，我们可以先设 x = n，如果 2n - x 的平方根 = x，则返回结果，否则让 x 等于计算出的平方根，如果递归，直到计算出结果。

代码

二分法

    public static void main(String[] args) {
        System.out.println(coinByDichotomy(10));
    }

    private static int coinByDichotomy(int n) {
        int low = 1, high = n;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            if ((mid * mid + mid) / 2 == n) {
                return mid;
            }
            if ((mid * mid + mid) / 2 > n) {
                high = mid - 1;
            } else if ((mid * mid + mid) / 2 < n) {
                low = mid + 1;
            }
        }
        return low - 1;
    }

牛顿迭代

    public static void main(String[] args) {
        System.out.println(coinByNewton(10));
    }

    private static int coinByNewton(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        return (int) sqrtByNewton(n, n);
    }

    private static double sqrtByNewton(double x, int n) {
        double res = (x + (2 * n - x) / x) / 2;
        if (res == x) {
            return res;
        }
        return sqrtByNewton(res, n);
    }