P13-排列硬币-二分查找/牛顿迭代

//排列硬币
/*
* 总共有n枚硬币，将他们摆成一个阶梯形状，第k行就必须正好有k枚硬币
* 给定一个数字n，找出可形成完整阶梯行的总行数。
* n是一个非负整数，并且在32位有符号整型的范围内
*
* 假如n=5，
* ○
* ○ ○
* ○ ○   所以结果是2，只有第一第二行是完整的，第三行不完整
* */
public class P13 {
    public static void main(String[] args) {
        System.out.println(arrangeCoins(100));
        System.out.println(arrangeCoins2(100));
        System.out.println(arrangeCoins3(100));
    }

    //1、暴力
    //准备放硬币之前，判断行号是否小于硬币数，是的话减行号，然后下一行
    public static int arrangeCoins(int num){
        //i从1开始，作为行号
        for(int i=1; i<=num; i++){
            num = num - i;
            if(num <= i){
                return i;
            }
        }
        return 0;
    }

    //2、二分查找
    //上面的方法需要把n放完才知道结果
    /*
    * num个硬币，先假设能放num行，如果num行的硬币总数是x，x肯定大于num
    * 3个硬币，假设放3行，即总数是6，6>3是必然的，答案必然在3行及以内，用二分查找
    * 10个硬币，假设放10行，即总数是55，55必然大于10，答案必然在10行及以内，用二分查找
    * */
    public static int arrangeCoins2(int num){
        int low = 0;
        int high = num;     //假设num个硬币放num行
        while(low <= high){
            int mid = (low+high) / 2;
            //x行硬币总数是等差数列公式
            int cost = (mid+1) * mid / 2;
            if(cost == num){
                return mid;     //找到行数
            }else if(cost > num){
                high = mid - 1;
            }else{
                low = mid + 1;
            }
        }
        return high;
    }

    //3、牛顿迭代
    public static int arrangeCoins3(int num){
        if(num == 0){
            return 0;
        }
        return (int)sqrt(num, num);
    }

    //公式本来是 （x + y/x） / 2，看回P8，
    //但因为等差数列公式是 (x+1)*x / 2 = n (n就是总数的意思，等差数列求和，即总硬币数，x是行号)
    //x平方 = 2n - x，就是要求2n-x的平方根，x = 根号(2n-x)
    //牛顿迭代本来就是依赖一个公式 x = y/x，看回P8啊，要求的是y的平方根，
    //现在要求2n-x的平方根，所以要将 2n-x 代入 y
    private static double sqrt(double x, int num) {
        double res = (x + (2*num-x)/x) / 2;
        if(res == x){
            return x;
        }else{
            return sqrt(res, num);
        }
    }
}