V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
tl3shi
V2EX  ›  程序员

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

  •  
  •   tl3shi · 2016-12-19 23:33:01 +08:00 · 8954 次点击
    这是一个创建于 2880 天前的主题,其中的信息可能已经有所发展或是发生改变。

    原文在此 看看 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] 这个区间的任意一个都满足条件.

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

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

    第 1 条附言  ·  2016-12-20 00:39:25 +08:00
    其实, 本意是想让写一个二分的.
    说分分钟秒掉的, 很 easy 等等的同学, 能不去网上找, 现在动手写一个么. 然后再来看看写的是否符合题意.
    85 条回复    2016-12-21 16:59:11 +08:00
    SuperFashi
        1
    SuperFashi  
       2016-12-19 23:38:56 +08:00 via Android
    牛顿迭代,这题面试要出不分分钟秒掉……
    sagaxu
        2
    sagaxu  
       2016-12-19 23:39:12 +08:00 via Android
    两个思路,一是二分法逼近,二是牛顿法
    neoblackcap
        3
    neoblackcap  
       2016-12-19 23:41:06 +08:00
    这个不就是二分法求解吗?牛顿迭代法迭代的次数可以更少,但是记得是不能根据任意的 elision 值来求值的。
    kkk330
        4
    kkk330  
       2016-12-19 23:49:01 +08:00
    第一反应就是牛顿法, 这个比较考数学功底了吧, Leetcode 上有个基本一致的题
    kamen
        5
    kamen  
       2016-12-19 23:58:16 +08:00   ❤️ 1
    这个不是数学题吗
    misaka19000
        6
    misaka19000  
       2016-12-20 00:04:15 +08:00 via Android
    牛顿法
    misaka19000
        7
    misaka19000  
       2016-12-20 00:04:58 +08:00 via Android
    SICP 里面就有一个这样的例子,不过是用 Lisp 写的就是了
    tl3shi
        8
    tl3shi  
    OP
       2016-12-20 00:19:35 +08:00
    看来 V 站的程序猿素质高些, 哈哈. 我也认为 2 分(至少经过提示后), 应该能写出来才对. 不过实际面试过程中, 很难有人写出来. 题目就是 leetcode 上原题稍微变动加了个约束条件.

    说归说, 能 show me your code 试试吗?
    hanxiV2EX
        9
    hanxiV2EX  
       2016-12-20 00:29:16 +08:00 via iPhone   ❤️ 1
    用牛顿法,公式已经忘记了,初始值远取很重要。 http://diducoder.com/sotry-about-sqrt.html
    debiann
        10
    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
        11
    ryanzyy  
       2016-12-20 01:35:55 +08:00
    函数式编程 用 fixed point 来解
    参考资料 https://briangordon.github.io/2014/06/sqrts-and-fixed-points.html
    eminemcola
        12
    eminemcola  
       2016-12-20 01:57:43 +08:00 via Android
    看到题目,不借助搜索引擎的情况下能想到牛顿法,但具体到代码上估计还是得查一下…
    ryanzyy
        13
    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
        14
    zscself  
       2016-12-20 02:02:25 +08:00
    变量 xjb 命名,函数 xjb 创建,凑凑活活写出来了。
    https://oi46s5f95.qnssl.com/[email protected]
    @tl3shi
    bombless
        15
    bombless  
       2016-12-20 02:24:26 +08:00 via Android   ❤️ 1
    同感,这不数学题吗,哈哈。数值计算虽然经常被用到软件中,但它毕竟是用数学手段去解决数学问题。
    justyy
        16
    justyy  
       2016-12-20 02:25:31 +08:00
    ivanlw
        17
    ivanlw  
       2016-12-20 03:53:45 +08:00
    道理我都懂,可是对 v 对开根号, t 是干嘛用的?
    msg7086
        18
    msg7086  
       2016-12-20 04:09:41 +08:00
    @ivanlw 最大误差。
    msg7086
        19
    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
        20
    q397064399  
       2016-12-20 04:44:42 +08:00
    @ivanlw t 是误差,计算机开根号 也只能求解近似值
    msg7086
        21
    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
        22
    q397064399  
       2016-12-20 05:44:13 +08:00
    如果让我面试做这种狗屎题,我心里肯定会说,
    你这套路不对,这题我平时刷的时候没怎么见过,
    面试时间一般也就 20 分钟-1 小时
    这还要人编写正确的程序出来,还不给上网查资料,
    这么简单的题目,写错了就没分,我操,面试官 傻逼 脑残 负分 滚出
    为什么说这题简单呢?因为这题 一看就是烂大街的题目 我要是做不出来 不就负分了么
    (虽然我能把二分整数搜索的算法记忆的滚瓜烂熟)
    kingdaa
        23
    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
        24
    q397064399  
       2016-12-20 06:18:08 +08:00
    现在让我来说为什么这题是狗屎题了吧

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

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

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

    所以呢?

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

    面试者心里想,什么狗屎题,老子也知道这题二分是能解的,但是你这破公式,我就是想不出 一个递归检索的条件
    q397064399
        25
    q397064399  
       2016-12-20 06:26:55 +08:00
    @kingdaa
    你这错了 我瞄一眼 就知道你这错了,
    面试你这样写 直接负分滚出,题意都没看懂
    q397064399
        26
    q397064399  
       2016-12-20 06:37:21 +08:00
    所以这题在没有其他数学功底等套路的情况下,
    最多只能想到二分搜索,但是这题 难点并不在二分搜索本身,而在于从公式中(ノ*・ω・)ノ推导出结束条件,
    结束条件,刷过这个题的人,肯定会心一笑,正好踩到面试官的点
    没刷过这个题的人,心里就骂娘了
    q397064399
        27
    q397064399  
       2016-12-20 06:47:31 +08:00
    如果你真要考察 对二分搜索的应用能力,我建议出一个题目
    讲一个故事 需要应用到 3sum ,要求算法复杂度低于 O(n3) ,即可
    你这题目,面试者很难 get 到结束条件
    nagato
        28
    nagato  
       2016-12-20 07:33:26 +08:00
    这题解法太多了,之前网上看到过一篇文章,对比了 13 种不同的解法
    Cbdy
        29
    Cbdy  
       2016-12-20 07:36:56 +08:00 via Android
    方法很多,最常见就是牛顿迭代法。收敛比较快
    Death
        30
    Death  
       2016-12-20 08:25:19 +08:00 via Android
    出题人有数值分析的基础吗?……
    misaka19000
        31
    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
        32
    Cabana  
       2016-12-20 09:11:15 +08:00
    还记得以前看过一个开平方的神奇常数,用一个常数值作为起始猜值进行迭代,收敛会特别快
    tl3shi
        33
    tl3shi  
    OP
       2016-12-20 09:18:21 +08:00 via iPhone
    我想强调的不是说这道题目本身 而是说当有人给你一种思路后、能否在一步一步引导情况下思考并解决问题,最后能否将已经明白的思路变成实实在在的 code ,这肯定是较好的程序员应该具备的能力。

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

    楼上的代码貌似有不少是满足不了题意的
    ytmsdy
        34
    ytmsdy  
       2016-12-20 09:18:30 +08:00
    想到了当年 POJ 上面的一道打表题。。
    Cbdy
        35
    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
        36
    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
        37
    metowolf  
       2016-12-20 09:44:44 +08:00
    necomancer
        38
    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
        39
    pumpkin  
       2016-12-20 10:05:51 +08:00
    计算机程序的构造和解释中有非常详细的分析,由牛顿迭代法到最后抽象出的不动点搜寻,可以解决许多问题,比如求方程的根,求 PI 的值这种类型。
    xumaoxing
        40
    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
        41
    xiamx  
       2016-12-20 10:41:38 +08:00
    这位 @q397064399 是何方神圣....
    q397064399
        42
    q397064399  
       2016-12-20 10:45:38 +08:00
    @xiamx 菜鸟一枚
    shuson
        43
    shuson  
       2016-12-20 11:00:36 +08:00
    这道题我不做
    dikT
        44
    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
        45
    debiann  
       2016-12-20 11:16:48 +08:00
    @tl3shi 二分法是你期待的答案。
    但二分法并不是一个好的答案。牛顿迭代法的收敛速度比二分法快很多。
    这道题的重点不是怎么算出平方根(方法有很多),而是做误差分析。如果需要严格地证明误差小于一定的值,首先必须要有已知的参考值。所以要有数据类型允许的范围内一系列已知的答案才能完整地解这道题。
    ls 给出了各种方法,都被你否认;虽然也没有考虑误差的问题,但你也没仔细想过。
    总的来说,你不是来问问题的,你想表达的就是:“我说的就是对的,其他都是垃圾。”
    joying
        46
    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
        47
    TIGERB  
       2016-12-20 11:27:49 +08:00
    我水的掉渣。。。。。。
    nbndco
        48
    nbndco  
       2016-12-20 11:31:40 +08:00 via iPhone
    @q397064399 二分想不出结束条件完全是水平不行而已,和数学功底或者刷没刷过这个题有什么关系,只要会二分,结束条件都是显而易见的。倒是牛顿法的话结束条件难以判断一些
    q397064399
        49
    q397064399  
       2016-12-20 11:39:25 +08:00
    @nbndco 跪求所谓显而易见的结束条件 谢谢
    debiann
        50
    debiann  
       2016-12-20 11:40:32 +08:00
    @nbndco 同求,谢谢。
    huntzhan
        51
    huntzhan  
       2016-12-20 11:41:38 +08:00
    ......热身算法题难度呀,这种题面 MFG 都要求直接秒的
    nbndco
        52
    nbndco  
       2016-12-20 11:50:00 +08:00 via iPhone
    @q397064399 区间的大小小于要求误差的时候取中值
    q397064399
        53
    q397064399  
       2016-12-20 11:54:28 +08:00
    题主的本意是,
    通过一些不那么一眼就能看出来的题目 来检测一个人对教科书上的基本算法应用能力,
    你们又是 牛顿迭代 又是啥的,明显是刷过题 知道各种套路老司机 何必来这里折腾,

    这题的坑 楼主自己都说了,用二分搜索 结束条件 是新司机一下子想不到的,
    何况这是个面试, 20 分钟-30 分钟的样子,能把二分写对,然后还要写测试,
    q397064399
        54
    q397064399  
       2016-12-20 11:58:13 +08:00
    @nbndco show code 吧, 不打嘴炮了,请问如何计算 你所谓的区间大小
    rogerchen
        55
    rogerchen  
       2016-12-20 11:59:09 +08:00
    签名都是错的,大把大把的 (v, t) 都可以让二分搜索永远停不了机。
    tl3shi
        56
    tl3shi  
    OP
       2016-12-20 12:19:14 +08:00
    @debiann 能写出牛顿迭代或者仅仅这种方法当然有好的印象加分, **看中的是在交流过程中思考解决问题的能力, 不是说这道题目写出来就 NB , 写不出来就滚蛋**。


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

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

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

    我也当做自己在吃瓜 :)

    不过, 可能题目文字上面描述得还可以更好。。。 对于某些人来说是比较排斥看什么公式的。
    zjbztianya
        57
    zjbztianya  
       2016-12-20 12:33:02 +08:00
    直接用循环控制二分次数。。。精度妥妥达到要求。。。
    senghoo
        58
    senghoo  
       2016-12-20 12:39:15 +08:00
    对于看过 SICP 的来说很简单吧。书上列题啊。
    debiann
        59
    debiann  
       2016-12-20 12:43:14 +08:00 via iPhone
    @tl3shi
    第一,这个帖子里我没看见有“喷子”,只看到了你对回复者的不屑。
    第二,牛顿迭代法并不是什么厉害的算法,这是计算方法的送分题。只要考试及格的人都会。
    nbndco
        60
    nbndco  
       2016-12-20 12:46:33 +08:00 via iPhone
    @q397064399 想不到的应该算是新手了,这么简单的题你要是非要胡搅蛮缠那你当我不会好了。这个题在我看来,二分基本算是白送,不需要任何前置知识,如果考虑到 double 表示的精度加点分,这个都不会还说会二分太逗了吧。
    牛顿法本来就没要求,只不过这个题是有一个更好的解法,面试官又没要你会。事实上面试官希望你用二分,因为牛顿法其实是不好判断精度的。
    q397064399
        61
    q397064399  
       2016-12-20 13:16:27 +08:00
    @nbndco 你有时间打这么多字,就写个 递归结束条件 都不会?
    q397064399
        62
    q397064399  
       2016-12-20 13:16:54 +08:00
    @nbndco 也就一行代码吧
    nyaruko
        63
    nyaruko  
       2016-12-20 13:34:48 +08:00
    @Cbdy 这个代码貌似是当年 doom 的作者写的
    tl3shi
        64
    tl3shi  
    OP
       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
        65
    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
        66
    z657386160z  
       2016-12-20 14:06:43 +08:00
    |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
        67
    zzzreg  
       2016-12-20 14:24:31 +08:00   ❤️ 1
    膜一下 @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
        68
    ybh37  
       2016-12-20 14:44:11 +08:00
    0x5f3759df
    phx13ye
        69
    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
        70
    jiezg  
       2016-12-20 16:33:42 +08:00 via Android
    我就来看有没有提 Carmack 的开根号,果然有
    choury
        71
    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
        72
    imdoge  
       2016-12-20 16:50:20 +08:00
    想到平方根倒数速算法
    guyskk
        73
    guyskk  
       2016-12-20 16:56:41 +08:00
    最先想到的是方根倒数算法,其次是牛顿迭代法
    lcdtyph
        74
    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
        75
    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
        76
    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
        77
    yangyaofei  
       2016-12-20 18:11:36 +08:00
    泰勒级数 根下 x+1 在零点展开
    Med
        78
    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
        79
    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
        80
    wizardoz  
       2016-12-21 09:39:19 +08:00
    牛顿法知道原理,但是公式不记得了,用二分法妥妥解决。
    t 就是迭代结束的条件。
    littleshy
        81
    littleshy  
       2016-12-21 10:15:45 +08:00
    《计算机程序的构造和解释》开篇就讲这个。要不怎么说这是程序员的“圣经”呢。
    StephenChow
        82
    StephenChow  
       2016-12-21 11:17:55 +08:00
    @hanxiV2EX 看了一上午,长知识
    zjxzhqq
        83
    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
        84
    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
        85
    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
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1070 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 126ms · UTC 19:24 · PVG 03:24 · LAX 11:24 · JFK 14:24
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.