题目，给一个整数，求它的平方根，不能使用java自带的Math.sqrt();
说来尴尬，我都不知道平方根是啥 0.0
贴心的面试官老哥告诉我就是开平方，比如4的平方根是2，100的平方根是10；
刚开始懵了，又是现场编程，本来就紧张，还不知道啥是平方根，严重影响发挥；
题解：
public class MySqrtDemo { public static void main(String[] args) { System.out.println(sqrt(100));//10 } public static int sqrt(int i) { if (i <= 0) return i; int result; //从1开始疯狂试探 for (int j = 1; true; j++) { if ((j * j <= i) && ((j + 1) * (j + 1) > i)) { result = j; //记得跳出循环 break; } } return result; } }
思路：
我这个方法没啥特点，就是从1开始疯狂试探，直到有一个数 i 满足i * i<=x&&((i+1)*(i+1)>x)，这个 i 就是x的平方根；
优化
上面这个临时想出来的算法显然太鲁莽，优化优化
基于上面的算法，大体思路不会变，我们在 j * j 不等于入参的时候，对结果进行二分后再返回，无限二分，直到不能再细分，这样的值会更接近真实平方根；
public class MySqrtDemo { public static void main(String[] args) { System.out.println(sqrt(10));// 3.1622772216796875 System.out.println(Math.sqrt(10));// 3.1622776601683795 } public static double sqrt(int i) { if (i <= 0) return i; double result; //从1开始疯狂试探 for (int j = 1; true; j++) { if (j * j == i) { result = j; //记得跳出循环 break; } else if ((j * j < i) && ((j + 1) * (j + 1) > i)) { result = half(i, j, j + 1); //记得跳出循环 break; } } return result; } public static double half(int i, double small, double big) { double average = (small + big) / 2; double result = average * average; if (result == i) { //如果平均值*平均值等于入参，直接返回 return average; } else if (result > i) { //大于，则在前一个数和平均值之间递归二分 if (String.valueOf(average).length() >= 18) return average; return half(i, small, average); } else { //小于，则在平均值后一个数之间递归二分 if (String.valueOf(average).length() >= 18) return average; return half(i, average, big); } } }
再次优化
利用牛顿法求解，这个解法对于我们这种学渣理解起来还是很有难度的，毕竟二次方程求导那些知识点早忘了
private static double mySqrt(int num) { double result = num; //精度控制，精确到多少位，但并不是截取到多少位，只是超过这个位数后面的值不精确了 double accuracy = 0.001; //精度越高，循环次数越多 while (result * result - num > accuracy) { //牛顿法，由切线方程求导转换而来，具体原理我还没搞懂 0.0 result = (result * result + num) / (2 * result); } return result; }
