0

我需要 hep 弄清楚这段代码的不变量是什么。我认为可能有多个不变量，但我并不真正理解我发现的主题和在线资源仍然没有真正的帮助。我为二进制搜索制作的代码是：

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

好的，所以这个答案迟了将近半年，但这里是：

循环不变量只是在循环的每次迭代之前（和之后）保持的东西。所以在这里，我们需要找到一个条件，每次代码在箭头标出的地方都有效：

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，使新的 r 更接近最小整数 <= sqrt(n)，通过减少它，或者你更新 l，使新的 l 更接近最小整数<= sqrt(n)，但是通过增加它。所以循环不变量很简单：

l <= 楼层(sqrt(n)) <= r

于 2015-04-20T14:29:59.877 回答