用牛顿迭代法求整数的平方根
浏览:2519次 出处信息
这是一个挺常见的面试题,解法也五花八门。
下面的代码用牛顿迭代法解决这个问题。因为输入和输出都是整数,所以只要前后两项相差小于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天十大热文
- [66] Oracle MTS模式下 进程地址与会话信
- [65] Go Reflect 性能
- [64] 如何拿下简短的域名
- [60] android 开发入门
- [59] 图书馆的世界纪录
- [59] 【社会化设计】自我(self)部分――欢迎区
- [58] IOS安全–浅谈关于IOS加固的几种方法
- [54] 视觉调整-设计师 vs. 逻辑
- [48] 界面设计速成
- [48] 读书笔记-壹百度:百度十年千倍的29条法则