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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

• 请不要在回答技术问题时复制粘贴 AI 生成的内容

这是一个创建于 2933 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

double sqrt(int v, double t)

要求:

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

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

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

第 1 条附言 · 2016-12-20 00:39:25 +08:00

其实, 本意是想让写一个二分的.
说分分钟秒掉的, 很 easy 等等的同学, 能不去网上找, 现在动手写一个么. 然后再来看看写的是否符合题意.

sqrt

函数

double

调用

85 条回复 • 2016-12-21 16:59:11 +08:00

SuperFashi

2016-12-19 23:38:56 +08:00 via Android

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

sagaxu

2016-12-19 23:39:12 +08:00 via Android

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

neoblackcap

2016-12-19 23:41:06 +08:00

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

kkk330

2016-12-19 23:49:01 +08:00

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

kamen

2016-12-19 23:58:16 +08:00

这个不是数学题吗

misaka19000

2016-12-20 00:04:15 +08:00 via Android

牛顿法

misaka19000

2016-12-20 00:04:58 +08:00 via Android

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

tl3shi

2016-12-20 00:19:35 +08:00

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

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

hanxiV2EX

2016-12-20 00:29:16 +08:00 via iPhone

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

debiann

2016-12-20 01:31:41 +08:00

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

ryanzyy

2016-12-20 01:35:55 +08:00

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

eminemcola

2016-12-20 01:57:43 +08:00 via Android

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

ryanzyy

2016-12-20 02:02:13 +08:00

'''
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

2016-12-20 02:02:25 +08:00

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

bombless

2016-12-20 02:24:26 +08:00 via Android

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

justyy

2016-12-20 02:25:31 +08:00

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

ivanlw

2016-12-20 03:53:45 +08:00

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

msg7086

2016-12-20 04:09:41 +08:00

@ivanlw 最大误差。

msg7086

2016-12-20 04:34:55 +08:00

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

2016-12-20 04:44:42 +08:00

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

msg7086

2016-12-20 05:01:58 +08:00

上面的解法好像改变了精度了。

按照原题要求的精度来的话，牛顿迭代和二分法的 Ruby 实现：
test = ->(sq, t, rt) { (rt+t) * (rt+t) < sq || (rt-t) * (rt-t) > sq }
sqrt1 = ->(sq, t) { rt = sq * 1.0; rt = (rt + sq / rt) / 2 while test.call(sq, t, rt); rt }
sqrt2 = ->(sq, t) { (0..sq.to_f).bsearch { |rt| test.call(sq, t, rt) ? sq - rt * rt : 0 } }

sqrt1.call(9, 0.21)
# => 3.023529411764706
sqrt1.call(9, 0.0001)
# => 3.00009155413138

sqrt2.call(9, 0.21)
# => 2.993255615234375
sqrt2.call(9, 0.0001)
# => 2.9999834150075912

q397064399

2016-12-20 05:44:13 +08:00

如果让我面试做这种狗屎题，我心里肯定会说，
你这套路不对，这题我平时刷的时候没怎么见过，
面试时间一般也就 20 分钟-1 小时
这还要人编写正确的程序出来，还不给上网查资料，
这么简单的题目，写错了就没分，我操，面试官傻逼脑残负分滚出
为什么说这题简单呢？因为这题一看就是烂大街的题目我要是做不出来不就负分了么
（虽然我能把二分整数搜索的算法记忆的滚瓜烂熟）

kingdaa

2016-12-20 05:44:49 +08:00

public static double sqrt(int v, double t) {
assert (v > 0 && t > 0);
double lo = 0.0, hi = v * 1.0;
while (lo < hi) {
double mid = lo + (hi - lo) / 2;
double midSq = mid * mid;
double diff = (midSq - v) >= 0 ? (midSq - v) : (v - midSq);
if (diff <= t)
return mid;
if (midSq > v)
hi = mid;
else
lo = mid;
}
return -1.0;
}

q397064399

2016-12-20 06:18:08 +08:00

现在让我来说为什么这题是狗屎题了吧

让我解的话，只能想到一种办法，那就是根据 t 的精度进行暴力搜索
每次只加 0.0000001 （假设）直到条件不满足的时候，那么前一个解必然是在区间范围内的

这样一来，想到什么了没有，被我们暴力搜索的候选结果集是一个等差数列
既然是等差数列，那么就是有序候选集，搜索有序结果集必然采用我大二分搜索法能大大降低算法复杂度

关键是你 TM 的这公式，让我根本想不出这二分搜索递归结束的条件啊
（我们平常用二分搜索都是搜索整数递归的结束条件比较简单）

所以呢？

面试的时候，如果面试者讲暴力搜索，面试官心里面会想这么暴力？连二分都不会

面试者心里想，什么狗屎题，老子也知道这题二分是能解的，但是你这破公式，我就是想不出一个递归检索的条件

q397064399

2016-12-20 06:26:55 +08:00

@kingdaa
你这错了我瞄一眼就知道你这错了，
面试你这样写直接负分滚出，题意都没看懂

q397064399

2016-12-20 06:37:21 +08:00

所以这题在没有其他数学功底等套路的情况下，
最多只能想到二分搜索，但是这题难点并不在二分搜索本身，而在于从公式中(ﾉ*･ω･)ﾉ推导出结束条件，
结束条件，刷过这个题的人，肯定会心一笑，正好踩到面试官的点
没刷过这个题的人，心里就骂娘了

q397064399

2016-12-20 06:47:31 +08:00

如果你真要考察对二分搜索的应用能力，我建议出一个题目
讲一个故事需要应用到 3sum ，要求算法复杂度低于 O(n3) ，即可
你这题目，面试者很难 get 到结束条件

nagato

2016-12-20 07:33:26 +08:00

这题解法太多了，之前网上看到过一篇文章，对比了 13 种不同的解法

Cbdy

2016-12-20 07:36:56 +08:00 via Android

方法很多，最常见就是牛顿迭代法。收敛比较快

Death

2016-12-20 08:25:19 +08:00 via Android

出题人有数值分析的基础吗？……

misaka19000

2016-12-20 09:06:07 +08:00

```lisp
;Newton's method 二次开方
(define (sqrt x)
(define (sqrt-iter guess x)
(cond ((< (abs (- x (* guess guess))) 0.001 ) guess)
(else (sqrt-iter (improve guess x) x))
))
(define (improve guess x)
(/ (+ guess (/ x guess)) 2))
(define (abs x)
(if (< x 0)
(- x)
x))
(sqrt-iter 1.0 x))

(sqrt 4)
```

Cabana

2016-12-20 09:11:15 +08:00

还记得以前看过一个开平方的神奇常数，用一个常数值作为起始猜值进行迭代，收敛会特别快

tl3shi

2016-12-20 09:18:21 +08:00 via iPhone

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

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

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

ytmsdy

2016-12-20 09:18:30 +08:00

想到了当年 POJ 上面的一道打表题。。

Cbdy

2016-12-20 09:19:42 +08:00

@Cabana 是 0x5f375a86

贴一段神奇的代码，据说比编译器的开方函数还快 5 倍
```
float InvSqrt(float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x; // get bits for floating VALUE
i = 0x5f375a86- (i>>1); // gives initial guess y0
x = *(float*)&i; // convert bits BACK to float
x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
return x;
}
```

elvodn

2016-12-20 09:36:39 +08:00

没有用到系统库函数啊：）
```
double h_sqrt(int v, double t) {
double vd = (double)v;
double sqrt;
asm ("sqrtsd %1, %0"
: "=x" (sqrt)
: "xm" (vd));
return sqrt;
}
```

metowolf

2016-12-20 09:44:44 +08:00

牛顿迭代法，没有查资料写的
https://gist.github.com/metowolf/859e9d1b116b55c553c828ff1b99bd3e

necomancer

2016-12-20 09:55:39 +08:00

我想到平方根倒数快速算法，基于牛顿法，是雷神 3 里的一段代码，有对应 64 位的魔法数，也有误差分析，最后取倒数行不？

https://zh.wikipedia.org/wiki/%E5%B9%B3%E6%96%B9%E6%A0%B9%E5%80%92%E6%95%B0%E9%80%9F%E7%AE%97%E6%B3%95

pumpkin

2016-12-20 10:05:51 +08:00

计算机程序的构造和解释中有非常详细的分析，由牛顿迭代法到最后抽象出的不动点搜寻，可以解决许多问题，比如求方程的根，求 PI 的值这种类型。

xumaoxing

2016-12-20 10:06:37 +08:00

def simple_sqrt(v, t):
if v < 0:
raise ValueError('domain error')

if v == 0:
return 0

# binary search
if v < 1:
left, right = v, 1
else:
left, right = 0, v
while True:
mid = (left + right) / 2.0
dest = mid * mid
diff = dest - v

if diff > 0 and (mid - t) * (mid - t) <= v:
return mid
if diff < 0 and (mid + t) * (mid + t) >= v:
return mid
if diff == 0:
return mid

if diff > 0:
right = mid
else:
left = mid

xiamx

2016-12-20 10:41:38 +08:00

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

q397064399

2016-12-20 10:45:38 +08:00

@xiamx 菜鸟一枚

shuson

2016-12-20 11:00:36 +08:00

这道题我不做

dikT

2016-12-20 11:04:52 +08:00

# 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

2016-12-20 11:16:48 +08:00

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

joying

2016-12-20 11:27:04 +08:00

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

2016-12-20 11:27:49 +08:00

我水的掉渣。。。。。。

nbndco

2016-12-20 11:31:40 +08:00 via iPhone

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

q397064399

2016-12-20 11:39:25 +08:00

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

debiann

2016-12-20 11:40:32 +08:00

@nbndco 同求，谢谢。

huntzhan

2016-12-20 11:41:38 +08:00

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

nbndco

2016-12-20 11:50:00 +08:00 via iPhone

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

q397064399

2016-12-20 11:54:28 +08:00

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

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

q397064399

2016-12-20 11:58:13 +08:00

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

rogerchen

2016-12-20 11:59:09 +08:00

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

tl3shi

2016-12-20 12:19:14 +08:00

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

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

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

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

我也当做自己在吃瓜 :)

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

zjbztianya

2016-12-20 12:33:02 +08:00

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

senghoo

2016-12-20 12:39:15 +08:00

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

debiann

2016-12-20 12:43:14 +08:00 via iPhone

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

nbndco

2016-12-20 12:46:33 +08:00 via iPhone

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

q397064399

2016-12-20 13:16:27 +08:00

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

q397064399

2016-12-20 13:16:54 +08:00

@nbndco 也就一行代码吧

nyaruko

2016-12-20 13:34:48 +08:00

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

tl3shi

2016-12-20 13:46:54 +08:00

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

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

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

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

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

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

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

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

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

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

我也当做自己在吃瓜 :)

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

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

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

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

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

ixx

2016-12-20 13:53:14 +08:00

简单、暴力解
```
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

2016-12-20 14:06:43 +08:00

zzzreg

2016-12-20 14:24:31 +08:00

膜一下 @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

2016-12-20 14:44:11 +08:00

0x5f3759df

phx13ye

2016-12-20 15:07:31 +08:00

>>> 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

2016-12-20 16:33:42 +08:00 via Android

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

choury

2016-12-20 16:36:08 +08:00

```
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

2016-12-20 16:50:20 +08:00

想到平方根倒数速算法

guyskk

2016-12-20 16:56:41 +08:00

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

lcdtyph

2016-12-20 17:33:04 +08:00

奇怪……是我想的太简单了吗……感觉二分的条件很好写啊= =||
```
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

2016-12-20 17:57:40 +08:00

```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

2016-12-20 18:06:12 +08:00

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

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

yangyaofei

2016-12-20 18:11:36 +08:00

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

Med

2016-12-20 19:43:13 +08:00

``` 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

2016-12-20 20:13:07 +08:00

@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

2016-12-21 09:39:19 +08:00

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

littleshy

2016-12-21 10:15:45 +08:00

《计算机程序的构造和解释》开篇就讲这个。要不怎么说这是程序员的“圣经”呢。

StephenChow

2016-12-21 11:17:55 +08:00

@hanxiV2EX 看了一上午，长知识

zjxzhqq

2016-12-21 11:59:20 +08:00

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 16:35:03 +08:00

#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 16:59:11 +08:00

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