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

[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] 这个区间的任意一个都满足条件.

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

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

[q397064399]

@nbndco 你有时间打这么多字，就写个 递归结束条件 都不会？

[q397064399]

@nbndco 也就一行代码吧

[nyaruko]

@Cbdy 这个代码貌似是当年 doom 的作者写的

[tl3shi]

@rogerchen 这不正是应该考察应试者的问题嘛。。定义了一个接口， 让实现，说这个接口是错误的。好吧。
@debiann 那我错了。。开发者头条那喷了。 我并没有任何对回复者不屑的意思。

>
看来 V 站的程序猿素质高些, 哈哈. 我也认为 2 分(至少经过提示后), 应该能写出来才对. 不过实际面试过程中, 很难有人写出来. 题目就是 leetcode 上原题稍微变动加了个约束条件.

说归说, 能 show me your code 试试吗?


>
我想强调的不是说这道题目本身 而是说当有人给你一种思路后、能否在一步一步引导情况下思考并解决问题，最后能否将已经明白的思路变成实实在在的 code ，这肯定是较好的程序员应该具备的能力。

二分就是期待的答案，然而事实上就是并没有多少人写出。 结束条件就是一个坑给刷过这道题的人埋的，没刷过的人期望是经过提示后能写出二分。

楼上的代码貌似有不少是满足不了题意的


>
能写出牛顿迭代或者仅仅这种方法当然有好的印象加分， **看中的是在交流过程中思考解决问题的能力， 不是说这道题目写出来就 NB ， 写不出来就滚蛋**。


还有其他一些喷子， 麻烦好好看看原文好么。。。

http://mp.weixin.qq.com/s/0PsaOCR2k566SD9bRtgmlg

你们使劲喷吧， 让喷子来得更猛一些 喷之前， 求看完原文， 及想强调的东西。

我也当做自己在吃瓜 :)

不过， 可能题目文字上面描述得还可以更好。。。 对于某些人来说是比较排斥看什么公式的。


-----
哪条有不屑的意思？ 如果有， 可能回复给你的语气不太好吧？
再看看你的， “总的来说，你不是来问问题的，你想表达的就是：“我说的就是对的，其他都是垃圾。””
其实， 你前面部分， 我**挺认同**的。

“二分法是你期待的答案。
但二分法并不是一个好的答案。牛顿迭代法的收敛速度比二分法快很多。
这道题的重点不是怎么算出平方根（方法有很多），而是做误差分析。如果需要严格地证明误差小于一定的值，首先必须要有已知的参考值。所以要有数据类型允许的范围内一系列已知的答案才能完整地解这道题。
ls 给出了各种方法，都被你否认；虽然也没有考虑误差的问题，但你也没仔细想过。”

一直强调， 面试过程不是说要追求这道题目完成的答案。

咱俩的讨论， 就此打住吧。 如果有冒犯你的地方还请见谅。

[ixx]

简单、暴力解
```
function sq(v,t){
var i = 1;
var d = 1;
while(true){
if(i*i == v){
return i;
}
if(i*i < v){
i+=d;
} else {
i = i-d;
if(d < t){
break;
} else {
d*=0.1;
}
}
}
return i;
}
```

[z657386160z]

|r^2-v| <= t 是推不出来|r - \sqrt(v)| <= t 的吧，而且用|r*r - v|判断可能会溢出，应该用 r-2t <= (v-t^2)/r <= r+2t 来判断，这里假设 t^2<v ，如果大于 v ，直接返回 0 就行了。

[zzzreg]

膜一下 @msg7086 , 顺便楼主要的一行代码
sqrt = ->(v, t) { (0.0..v).bsearch { |x| (x-t) ** 2 < v && v < (x+t) ** 2 ? 0 : v - x ** 2 } }
sqrt.call(2, 0.001) # => 1.4140625

[ybh37]

0x5f3759df

[phx13ye]

>>> def newton(x, y=1.0, tolerance=0.001):
... if (abs(y*y-x) < tolerance):
... return y
... else:
... return newton(x, (y+x/y)/2)
...
>>> newton(2)
1.4142156862745097
>>> newton(3)
1.7321428571428572
>>> newton(9)
3.00009155413138

[jiezg]

我就来看有没有提 Carmack 的开根号，果然有

[choury]

```
double sqrt(int v, double t){
double x = 1;
while(x*x -v > t || v - x*x > t){
x = x+(v-x*x)/(2*x);
}
return x;
}
```

[imdoge]

想到平方根倒数速算法

[guyskk]

最先想到的是方根倒数算法，其次是牛顿迭代法

[lcdtyph]

奇怪……是我想的太简单了吗……感觉二分的条件很好写啊= =||
```
double simple_sqrt(double x, double e) {
double left = 0.0, right = 1.0 < x ? x : 1.0;
e = e < 0 ? -e : e;
if (x < e) return 0;

while (right - left >= e / 2) {
double middle = left + (right - left) / 2;
if (middle > x / middle) right = middle;
else left = middle;
}

return left;
}
```

[srlp]

```python
def sqrt(v, t):
"""assuming v is positive int, t is positive double"""
start = 1
end = v // 2
while True:
mid = start + (end - start) / 2.0
print('start = {}, mid = {}, end = {}'.format(start, mid, end))
if abs(mid * mid - v) <= t:
# we have abs(mid - sqrt(v)) <= abs(mid * mid - v) <= t
return mid
elif mid * mid < v:
start = mid
else:
end = mid
return start
```

[srlp]

想太多了，二分法下，限制 x 是正整数， v 是正小数的情况下，结束条件用 |x*x - v| <= t 就行。因为我们有：

t >= |x*x - v| = |x - sqrt(v)| * |x + sqrt(v)| >= |x - sqrt(v)|

[yangyaofei]

泰勒级数 根下 x+1 在零点展开

[Med]

``` java
public double sqrt(int v, double t) {
double min = 0;
double max = v;
double minRes = 0;
double maxRes = max * max;

double tmpMin = min;

while (v - minRes > t || maxRes - v > t) {
minRes = min * min;
if (minRes < v) {
tmpMin = min;
min = (min + max) / 2;
} else if (minRes == v) {
return min;
} else {
max = min;
maxRes = minRes;

min = tmpMin;
minRes = min * min;
}
}

System.out.println(min);
System.out.println(max);

return min;
}
```
结果:
3.005859375
3.0234375

[Med]

@Med
``` java
public double sqrt(int v, double t) {
double min = 0;
double max = v;
double minRes = 0;
double maxRes = max * max;

double tmpMin = min;

while (v - minRes > t || maxRes - v > t) {
if (minRes < v) {
tmpMin = min;
min = (min + max) / 2;
} else if (minRes == v) {
return min;
} else {
max = min;
maxRes = minRes;

min = tmpMin;
}

minRes = min * min;
}

System.out.println(min);
System.out.println(max);

return min;
}
```
输出
2.98828125
3.0234375

[wizardoz]

牛顿法知道原理，但是公式不记得了，用二分法妥妥解决。
t 就是迭代结束的条件。