二进制搜索以计算平方根(Java)

NuNu :

我需要编写一个使用二进制搜索来递归计算输入非负整数的平方根(四舍五入到最接近的整数)的程序的帮助。

这是我到目前为止所拥有的:

import java.util.Scanner;

public class Sqrt {

  public static void main(String[] args) {

    Scanner console = new Scanner(System.in);

    System.out.print("Enter A Valid Integer: ");

    int value = console.nextInt();

    calculateSquareRoot(value);

  }

    public static int calculateSquareRoot(int value) {
      while (value > 0) {
      double sqrt = (int) Math.sqrt(value);
      System.out.println(sqrt);
    }
    return -1;
    }
}

它必须使用二进制搜索来计算平方根的事实使我感到困惑。如果有人对如何执行此操作有任何建议,将不胜感激。谢谢

谢尔顿·库珀(Sheldon L. Cooper):

Codez茶:

def sqrt(n):
  low = 0
  high = n+1
  while high-low > 1:
    mid = (low+high) / 2
    if mid*mid <= n:
      low = mid
    else:
      high = mid
  return low

要理解它,只需考虑循环不变式,即:

低低<= n <高高

如果您理解此代码,那么编写递归版本应该很简单。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

TOP 榜单

热门标签

归档