用牛顿迭代法求整数的平方根
浏览:2441次 出处信息
这是一个挺常见的面试题,解法也五花八门。
下面的代码用牛顿迭代法解决这个问题。因为输入和输出都是整数,所以只要前后两项相差小于1,就可以终止了
int sqrt(int x) { if (x < 0) abort(); if (x == 0) return 0; if (x == 1) return 1; double t = x >> 1; t = (t + x / t) / 2; while (true) { double v = (t + x / t) / 2; if (fabs(v - t) < 1) { t = v; break; } t = v; } t=floor(t); if (t * t > x) t--; return t; }
我本来想用有理数运算来代替double,后来发现不行,迭代次数过多后,如果分子分母约分约不下去,就溢出了。
上面这段代码其实也就只能应付面试,实际有很多比这个更优的方案,比如打表。
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
扫一扫订阅我的微信号:IT技术博客大学习
<< 前一篇:关于libmemcached中的crc的实现
后一篇:在2048里能够得到的最大的数是多少? >>
文章信息
- 作者:A programmer's life 来源: A programmer's life
- 标签: 平方根 牛顿 迭代法
- 发布时间:2014-11-25 22:50:14
近3天十大热文
- [283] Go Reflect 性能
- [15] [译]Google Chrome中的高性能网
- [10] webapp网页调试工具Chrome Dev
- [10] PHP上传文件类型彻底判断方案及PHP+ng
- [10] Mac下.apk的反编译
- [10] 精于图片处理的10款jQuery插件
- [9] PHP加速器 eaccelerator 缓存
- [9] 在FreeNAS/BSD搭建基于Nginx+
- [9] rsync同步的艺术
- [8] Linux常用系统信息查看命令