1

割り当ての場合、二分探索を使用して整数の平方根を見つけるメソッドを作成する必要があります。それが平方数でない場合は、s*s <= 数値となるような整数 s を返す必要があります (したがって、15 の場合は3) を返します。私がこれまでに持っているコードは

public class BinarySearch {

    /**
     * Integer square root Calculates the integer part of the square root of n,
     * i.e. integer s such that s*s <= n and (s+1)*(s+1) > n
     * requires n >= 0
     *
     * @param n number to find the square root of
     * @return integer part of its square root
     */
    private static int iSqrt(int n) {
        int l = 0;
        int r = n;
        int m = ((l + r + 1) / 2);

        // loop invariant
        while (Math.abs(m * m - n) > 0) {
            if ((m) * (m) > n) {
                r = m;
                m = ((l + r + 1) / 2);
            } else {
                l = m;
                m = ((l + r + 1) / 2);
            }
        }
        return m;
    }

    public static void main(String[] args) {
        //gets stuck
        System.out.println(iSqrt(15));
        //calculates correctly
        System.out.println(iSqrt(16));
    }
}

そして、これは平方数に対して正しい数を返しますが、他の整数に対しては無限ループに陥ります。問題が while 条件にあることはわかっていますが、数字が大きくなるにつれて平方数間のギャップが大きくなるため、何を入れればよいかわかりません (したがって、ギャップが以下でなければならないということは言えません)しきい値)。演習は不変条件に関するものであり、それが役立つ場合です (したがって、このように設定されている理由)。ありがとうございました。

4

4 に答える 4

0

考えてみてください:Math.abs(m*m-n) > 0は常に真の非平方数です。ゼロに.absなることはなく、負になることもないからです。それはあなたのループ状態です。そのため、ループは決して終了しません。

これで十分な情報が得られますか?

于 2014-12-07T15:27:03.590 に答える