技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 用牛顿迭代法求整数的平方根

用牛顿迭代法求整数的平方根

浏览:2534次  出处信息

   这是一个挺常见的面试题,解法也五花八门。

   下面的代码用牛顿迭代法解决这个问题。因为输入和输出都是整数,所以只要前后两项相差小于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技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1