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

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

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

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

[xiamx]

这位 @q397064399 是何方神圣....

[q397064399]

@xiamx 菜鸟一枚

[shuson]

这道题我不做

[dikT]

# Python
def sqrt(num, deli):
val_min = num - deli
val_max = num + deli
point = 1
while 1:
lower, bigger = [point, num] if num > point else [num, point]
mid = (lower + bigger)/2
tmp = mid ** 2
if tmp < val_min:
point, num = mid, bigger
num = bigger
elif tmp > val_max:
point, num = lower, mid
elif val_min < tmp < val_max:
return mid

print(sqrt(16, 0.21)) # 3.98828125

[debiann]

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

[joying]

func sqrt(_ num: Double, precision: Double) -> Double {
var start = 0.0
var end = num
while (end - start) > precision {
let middle = (start + end) / 2
if middle * middle > num {
end = middle
} else {
start = middle
}
}

return (start + end) / 2
}

[TIGERB]

我水的掉渣。。。。。。

[nbndco]

@q397064399 二分想不出结束条件完全是水平不行而已，和数学功底或者刷没刷过这个题有什么关系，只要会二分，结束条件都是显而易见的。倒是牛顿法的话结束条件难以判断一些

[q397064399]

@nbndco 跪求所谓显而易见的结束条件 谢谢

[debiann]

@nbndco 同求，谢谢。

[huntzhan]

......热身算法题难度呀，这种题面 MFG 都要求直接秒的

[nbndco]

@q397064399 区间的大小小于要求误差的时候取中值

[q397064399]

题主的本意是，
通过一些不那么一眼就能看出来的题目 来检测一个人对教科书上的基本算法应用能力，
你们又是 牛顿迭代 又是啥的，明显是刷过题 知道各种套路老司机 何必来这里折腾，

这题的坑 楼主自己都说了，用二分搜索 结束条件 是新司机一下子想不到的，
何况这是个面试， 20 分钟-30 分钟的样子，能把二分写对，然后还要写测试，

[q397064399]

@nbndco show code 吧， 不打嘴炮了，请问如何计算 你所谓的区间大小

[rogerchen]

签名都是错的，大把大把的 (v, t) 都可以让二分搜索永远停不了机。

[tl3shi]

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


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

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

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

我也当做自己在吃瓜 :)

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

[zjbztianya]

直接用循环控制二分次数。。。精度妥妥达到要求。。。

[senghoo]

对于看过 SICP 的来说很简单吧。书上列题啊。

[debiann]

@tl3shi
第一，这个帖子里我没看见有“喷子”，只看到了你对回复者的不屑。
第二，牛顿迭代法并不是什么厉害的算法，这是计算方法的送分题。只要考试及格的人都会。

[nbndco]

@q397064399 想不到的应该算是新手了，这么简单的题你要是非要胡搅蛮缠那你当我不会好了。这个题在我看来，二分基本算是白送，不需要任何前置知识，如果考虑到 double 表示的精度加点分，这个都不会还说会二分太逗了吧。
牛顿法本来就没要求，只不过这个题是有一个更好的解法，面试官又没要你会。事实上面试官希望你用二分，因为牛顿法其实是不好判断精度的。