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

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

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

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

[SuperFashi]

牛顿迭代，这题面试要出不分分钟秒掉……

[sagaxu]

两个思路，一是二分法逼近，二是牛顿法

[neoblackcap]

这个不就是二分法求解吗？牛顿迭代法迭代的次数可以更少，但是记得是不能根据任意的 elision 值来求值的。

[kkk330]

第一反应就是牛顿法, 这个比较考数学功底了吧, Leetcode 上有个基本一致的题

[kamen]

这个不是数学题吗

[misaka19000]

牛顿法

[misaka19000]

SICP 里面就有一个这样的例子，不过是用 Lisp 写的就是了

[tl3shi]

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

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

[hanxiV2EX]

用牛顿法，公式已经忘记了，初始值远取很重要。 http://diducoder.com/sotry-about-sqrt.html

[debiann]

牛顿迭代+1
误差通过证明误差收敛的公式分析(这里需要知道部分变量的准确的函数值，才能给出误差的上界)
sqrt.c(apple)的实际做法是把估计值列举出来，存储在数组中，然后再用牛顿迭代计算：
https://opensource.apple.com/source/Libm/Libm-92/ppc.subproj/sqrt.c

[ryanzyy]

函数式编程 用 fixed point 来解
参考资料 https://briangordon.github.io/2014/06/sqrts-and-fixed-points.html

[eminemcola]

看到题目，不借助搜索引擎的情况下能想到牛顿法，但具体到代码上估计还是得查一下…

[ryanzyy]

'''
function sqrt(num, ep) {
let step = (cb) => {
return (a,v) => {
let x = (v + a / v) / 2,
d = Math.abs(a - x*x);
if (d < ep) return x;
return cb(a, x);
};
};

let Z = (f) => ((x) => f((v1, v2) => x(x)(v1, v2)))(x => f((v1, v2) => x(x)(v1, v2)));

return Z(step)(num, num/2);
}

console.log(sqrt(9,0.21));
'''

[zscself]

变量 xjb 命名，函数 xjb 创建，凑凑活活写出来了。
https://oi46s5f95.qnssl.com/[e-mail]
@tl3shi

[bombless]

同感，这不数学题吗，哈哈。数值计算虽然经常被用到软件中，但它毕竟是用数学手段去解决数学问题。

[justyy]

Newton Iterative Sqrt Method https://helloacm.com/newton-iterative-sqrt-method/

[ivanlw]

道理我都懂，可是对 v 对开根号， t 是干嘛用的？

[msg7086]

@ivanlw 最大误差。

[msg7086]

sqrt = ->(sq, t) { rt = sq * 1.0; rt = (rt + sq / rt) / 2 while (rt * rt - sq).abs >= (t * t); rt }
sqrt.call(9, 0.21)
# => 3.00009155413138
sqrt.call(9, 0.0001)
# => 3.000000001396984

[q397064399]

@ivanlw t 是误差，计算机开根号 也只能求解近似值