一道程序猿面试题目, 大家来看看?

2016 年 12 月 19 日
 tl3shi

原文在此 看看 V 站的开发者对此问题怎么看.

实现一个函数, 完成 开根号 的操作, 方法签名如下.

double sqrt(int v, double t)

要求:

  1. 不能调用系统库函数, 诸如 Math.sqrt(v) 之类的;
  2. 假设计算出的结果为 r, 要求满足如下条件 (防止图片有问题留下 $|r - \sqrt v| \leq t $), 其中, ($\sqrt v$) 是真实的值, t 为给定的一个误差, 例如0.1等, 即你计算出的值r 要在给定的误差范围内.
  3. 实现语言不限, 你条件可以比上述更加苛刻, 但不能宽松, 举例而言, 我调用你的接口 sqrt(9, 0.21) 返回值属于 [2.79, 3.21] 这个区间的任意一个都满足条件.

其实你可以 拿出笔和纸, 尝试解答一下 强调一下, 一定要注意给定的误差条件, 欢迎沟通交流.

原文点我 是在微信上搞了一个投票调查(求投票), 微信公众号里的阅读原文是一个对该问题在面试过程中的模拟.

9963 次点击
所在节点    程序员
85 条回复
littleshy
2016 年 12 月 21 日
《计算机程序的构造和解释》开篇就讲这个。要不怎么说这是程序员的“圣经”呢。
StephenChow
2016 年 12 月 21 日
@hanxiV2EX 看了一上午，长知识
zjxzhqq
2016 年 12 月 21 日
public class Sqrt {

public static double sqrtBisection(double num, double deviation) {
return bisection(0, num, num, deviation);
}
public static double bisection(double left,double right,double num,double deviation) {
double center = (left + right)/2;
if (Math.pow(center-deviation, 2)<=num&&Math.pow(center+deviation, 2)>=num) {
return center;
}else if (Math.pow(center-deviation, 2)>num) {
return bisection(left, center, num, deviation);
}else {
return bisection(center, right, num, deviation);
}
}


public static void main(String[] args) {
System.out.println(sqrtBisection(10, 0.01));
}
}
结果为： 3.1640625
试着做了下
hd7771
2016 年 12 月 21 日
#include <stdio.h>
double eps = 0.1;
double abs(double x){
if(x < 0) return -x;
return x;
}
double sqrt(int v, double t){
double l = 0.0 , r = v + 0.0;
eps = t;
while(abs(r - l) <= eps){
double m = (l + r) / 2;
if(m * m > v) r = m;
else l = m;
}
return (l + r) / 2;
}
int main(){
return 0;
}

一般的算法竞赛者二分都是这样背的
yeyuexia
2016 年 12 月 21 日
sqrt' :: Double -> Double -> Double -> Double -> Double
sqrt' target buttom top t
| abs (result * result - target) < t * t = result
| result * result - target > 0 = sqrt' target buttom result t
| otherwise = sqrt' target result top t
where result = (buttom + top) / 2

sqrt :: Int -> Double -> Double
sqrt v t = sqrt' (fromIntegral v) 0 (fromIntegral v + 0.25) t

最近刚学 haskell 于是尝试着写了下，写的很难看 献丑了 orz

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://study.congcong.us/t/328753

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX