Posted on 2013-04-15 10:19
小明 閱讀(1477)
評論(0) 編輯 收藏 所屬分類:
數(shù)據(jù)結(jié)構(gòu)和算法
學(xué)過數(shù)值分析的都知道牛頓迭代法
令f(x) = x
2-a;
那么上式就變成:
x
n+1 =x
n-(x
n2-a)/(2*x
n)=(x
n+a/x
n)/2
實現(xiàn)的代碼如下，簡單優(yōu)美，收斂快。
public class Solution {
public int sqrt(int x) {
if(x==0) return 0;
if(x<=2) return 1;
int result = x/2;
while(true){
int next = (result+x/result)/2;
if(next>=result){
break;
}
else{
result = next;
}
};
return result;
}
}