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

2024-04-07  本文已影响0人  王月亮17

题目

假设有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);
    }
上一篇 下一篇

猜你喜欢

热点阅读