本文主要是介绍【算法】求平方根 - 二分法/牛顿迭代,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目
求一个数的平方根,要求返回小于等于平方根的正整数。
原理
二分法
遍历每次取中间数,大了就往小取,小了就往大取,直到取到正确的值。
牛顿迭代
求num的平方根,则是求 num / x 和 x 的均值,这个值会越来越趋近于真正的平方根。
比如求12的平方根,2 * 6 = 12,那么 (2 + 6) / 2的值就会更趋近于平方根。
代码
二分法
public static void main(String[] args) {System.out.println(sqrtByBinary(24));}private static int sqrtByBinary(int num) {int index = -1, l = 0, r = num;while (l <= r) {int mid = l + (r - l) / 2;if (mid * mid <= num) {index = mid;l = mid + 1;} else {r = mid - 1;}}return index;}
牛顿迭代
public static void main(String[] args) {System.out.println(newtonSqrt(24, 24));}public static int newtonSqrt(double i, int num) {double res = (i + num/i) / 2;if (res == i) {return (int) res;}return newtonSqrt(res, num);}
这篇关于【算法】求平方根 - 二分法/牛顿迭代的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!