o***d
发帖数: 313 | 1 难道不是float/double么?
而且test case: sqrt(3)=1 ???
sqrt(3)=1.732 ===> 2 |
d****o
发帖数: 1055 | 2 因为让你在面试的时候能做出来。
【在 o***d 的大作中提到】
: 难道不是float/double么?
: 而且test case: sqrt(3)=1 ???
: sqrt(3)=1.732 ===> 2
|
o***d
发帖数: 313 | 3 int同样用二分法么?这个误差可大了点.
要是我就先转成float,算晚了再返回int,这样的结果跟test case的结果不同....
【在 d****o 的大作中提到】
: 因为让你在面试的时候能做出来。
|
l*******b
发帖数: 2586 | 4 再想想，误差不大的，哈哈
【在 o***d 的大作中提到】
: int同样用二分法么?这个误差可大了点.
: 要是我就先转成float,算晚了再返回int,这样的结果跟test case的结果不同....
|
o***d
发帖数: 313 | 5
,?很多case误差为1,比如sqrt(3), leetcode: results: 1, my results: 2
【在 l*******b 的大作中提到】
: 再想想，误差不大的，哈哈
|
l*******b
发帖数: 2586 | 6 res * res <= x < (res+1) * (res+1)
满足这个条件的 res 就好啦，开始我也没想到，哈哈
牛顿法是这个递推式 y = (x + x/y) / 2，得用浮点数逼近，然后初值得选好，不然得
走10几次。
没想出什么好的选取办法来，(x >> 5) + 16这类的貌似太糙了
【在 o***d 的大作中提到】
:
: ,?很多case误差为1,比如sqrt(3), leetcode: results: 1, my results: 2
|
o***d
发帖数: 313 | 7 谢大牛,明白了.
【在 l*******b 的大作中提到】
: res * res <= x < (res+1) * (res+1)
: 满足这个条件的 res 就好啦，开始我也没想到，哈哈
: 牛顿法是这个递推式 y = (x + x/y) / 2，得用浮点数逼近，然后初值得选好，不然得
: 走10几次。
: 没想出什么好的选取办法来，(x >> 5) + 16这类的貌似太糙了
|
o***d
发帖数: 313 | 8 //my code which fails test cases of leetcode
double sqar(double a)
{
if (a < 0)
throw -1;
double x1, x2, xt, at, E;
E = 0.00001;
if (a >= 1)
{
x1 = 0.99;
x2 = a+0.01;
assert(x1*x1-a < 0);
assert(x2*x2-a > 0);
}
else
{
//--original wrong codec
//x1 = 1.01;
//x2 = (a+1)/2;
x1 = a/2;
x2 = 1.01;
//--oringal wrong code, x1 could be 0
//assert(x1*x1-a < 0);
assert(x1*x1-a < E);
assert(x2*x2-a > 0);
}
while(std::fabs(x1-x2) > E)
{
xt = (x1 + x2)/2;
at = xt*xt - a;
if(at<0)
x1 = xt;
else
x2 = xt;
}
return x1;
}
【在 o***d 的大作中提到】
: 谢大牛,明白了.
|
l*******b
发帖数: 2586 | 9 不牛，呵呵，都是看来的，自己还差得远
【在 o***d 的大作中提到】
: 谢大牛,明白了.
|
