0基础做网站/泉州网站关键词排名
在刷水题的时候看到一个要开根号的, 虽然可以Math.sqrt()解决这个问题
Problem - 2009acm.hdu.edu.cn抱着好玩的心态, 找到了关于开根号的两种算法, 二分法开根号和牛顿迭代法。
第一种是二分法开根号, 当start<=end的时候, 先计算mid, 然后比较mid的平方是不是
=x, 如果相等直接返回x就行了, x比较大的话就在mid+1到end进行二分查找, 同时还要对ans进行更新, x较小的话就在start到mid+1进行二分查找。
static int SquareRoot(int x){/*** 1和0开根号都是本身*/if (x == 0 || x == 1){return x;}int start = 1,end = x, ans = 0;while (start <= end){int mid = (start+end)/2;if (mid*mid == x){return x;}//xif (mid*mid < x){start = mid+1;ans = mid;}else{end = mid-1;}}return ans;}时间复杂度是O(Log x), Math.sqrt()的好像是O(1) - -
(更具体的)
Square root of an integer - GeeksforGeekswww.geeksforgeeks.org
牛顿迭代法用求方程近似根的方法, 先估计出一个和方程的根比较接近的值, 再用
公式推算出下一个更接近的值, 不断的重复这个过程就可以得到满意的精度, 所以
比较关键的地方在于选第一个近似根, 还有起始值上面。
static int sqrtNewton(int num, int e){int guess = num/2;int e0;int cnt = 0;do {guess = (guess + num / guess)/2;e0 = guess*guess-num;cnt++;}while (e0 > e);return guess;}