image.png

    1.  /**
    2.      * 暴力算法
    3.      * @param n n枚硬币
    4.      * @return 形成完整整阶行的总行数
    5.      */
    6.     private static int arrangeCoins(int n) {
    7.         for (int i = 1; i < n; i++) {
    8.             // 循环一次减一行
    9.             n = n - i;
    10.             // 如果剩下的硬币<=i的话，那么剩下的硬币就凑不齐下一行，直接返回i就是可以排列的最多完整行数
    11.             if (n <= i) {
    12.                 return i;
    13.             }
    14.         }
    15.         // 如果n=1，直接返回
    16.         return n;
    17.     }
     /**
     * 二分查找法
     * @param n n枚硬币
     * @return 形成完整整阶行的总行数
     */
    private static int arrangeCoins2(int n) {
        int left = 1 , right = n;
        while (left <= right) {
            int middle = left + (right - left)/2;
            // 计算从1到middle行的总硬币
            int sum = (1 + middle)*middle/2;
            // 总数相等，直接返回middle
            if (sum == n) {
                return middle;
            } else if (sum < n) {
            // 总数小于n，则左指针右移
                left = middle + 1;
            } else {
            // 总数大于n，则右指针左移
                right = middle - 1;
            }
        }
        return right;
    }

     /**
     * 牛顿迭代法
     * @param n n枚硬币
     * @return 形成完整整阶行的总行数
     */
    private static int arrangeCoins3(int n) {
        if (n == 0) {
            return n;
        }
        return (int)sqrt(n,n);
    }

    /**
     * 牛顿迭代的思路就是：根号i 一定在 i/n 和 n 之间，然后 (i/n+n)/2 在无限接近于 根号i，所以递归找到 根号i
     *  当 根号i = n时，i/n = n --> (i/n+n)/2 = n;
     * @param n
     * @param i -> 这里的i需要转换一下，(1+n)*n/2 = i --> n² = 2i - n
     * @return
     */
    public static double sqrt(double n, int i) {
        double res = ((2*i - n)/n + n)/2;
        if (res == n) {
            return n;
        } else {
            return sqrt(res,i);
        }
    }