leetcode:这题 int sqrt(int)??!!为啥用int# JobHunting - 待字闺中o*d2012-12-29 08:121 楼难道不是float/double么?而且test case: sqrt(3)=1 ???sqrt(3)=1.732 ===> 2
d*o2012-12-29 08:122 楼因为让你在面试的时候能做出来。【在 o***d 的大作中提到】: 难道不是float/double么?: 而且test case: sqrt(3)=1 ???: sqrt(3)=1.732 ===> 2
o*d2012-12-29 08:123 楼int同样用二分法么?这个误差可大了点.要是我就先转成float,算晚了再返回int,这样的结果跟test case的结果不同....【在 d****o 的大作中提到】: 因为让你在面试的时候能做出来。
l*b2012-12-29 08:124 楼再想想,误差不大的,哈哈【在 o***d 的大作中提到】: int同样用二分法么?这个误差可大了点.: 要是我就先转成float,算晚了再返回int,这样的结果跟test case的结果不同....
o*d2012-12-29 08:125 楼,?很多case误差为1,比如sqrt(3), leetcode: results: 1, my results: 2【在 l*******b 的大作中提到】: 再想想,误差不大的,哈哈
l*b2012-12-29 08:126 楼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*d2012-12-29 08:127 楼谢大牛,明白了.【在 l*******b 的大作中提到】: res * res <= x < (res+1) * (res+1): 满足这个条件的 res 就好啦,开始我也没想到,哈哈: 牛顿法是这个递推式 y = (x + x/y) / 2,得用浮点数逼近,然后初值得选好,不然得: 走10几次。: 没想出什么好的选取办法来,(x >> 5) + 16这类的貌似太糙了
o*d2012-12-29 08:128 楼//my code which fails test cases of leetcodedouble 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;elsex2 = xt;}return x1;}【在 o***d 的大作中提到】: 谢大牛,明白了.