0

このコードの不変条件が何であるかを理解する必要があります。複数の不変条件が存在する可能性があると思いますが、トピックをよく理解していません。また、見つけたオンライン リソースもまだ役に立ちません。二分探索用に作成したコードは次のとおりです。

public class BinarySearchSqrt {

    /** 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
     */
    private static int iSqrt(int n) {
        int l = 0;
        int r = n;
        int m = ((l + r + 1) / 2);
        /* loop invariant
         * :
         * :
         */
        while (Math.abs(l - m) > 0) {
            m = ((l + r + 1) / 2);
            if ((m + 1) * (m + 1) > n) {
                r = m - 1;
            } else if ((m * m) < n) {
                l = m + 1;
            }
        }
        return m;
    }
    public static void main(String[] args) {
        System.out.println(iSqrt(15));
        System.out.println(iSqrt(16));
    }
}

このコードは、バイナリ検索を使用して整数の平方根を見つけますが、平方数でない場合は、整数より小さい最も近い平方数の平方根を返す必要があります。

コードは機能しますが、不変式として何を配置するか、および返される正しい値がどのように示されるかを実際に理解するだけです。手がかり/説明は素晴らしいでしょう、ありがとう。

4

1 に答える 1

0

OK、この回答はほぼ半年遅れていますが、次のとおりです。

ループ不変条件は、ループの各反復の前 (および後) に保持される単純なものです。したがって、ここでは、コードが矢印でマークされた場所にあるたびに有効な条件を見つける必要があります。

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

したがって、ここでは、反復ごとに、新しい r が最小の整数 <= sqrt(n) に近くなるように r を更新するか、新しい l が最小の整数に近くなるように l を更新します。 <= sqrt(n) ですが、それを増やすことによって。したがって、ループ不変条件は単純です。

l <= 床 (sqrt(n)) <= r

于 2015-04-20T14:29:59.877 に答える