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

之前面试时遇到的一个有些奇怪的问题

  •  
  •   KomiSans ·
    KomiSans · 2021-10-08 16:11:32 +08:00 · 4103 次点击
    这是一个创建于 902 天前的主题,其中的信息可能已经有所发展或是发生改变。

    1000/1+1000/2+1000/3+...+1000/n=10000 求 n 是多少(面试的 nodeJS) 我因为理解能力比较差所以先写了一下具体的实现方法 如图:

    5CLRqH.jpg

    仅仅觉得有些奇怪 自己的写法也很奇怪

    31 条回复    2021-10-11 10:23:27 +08:00
    mxT52CRuqR6o5
        1
    mxT52CRuqR6o5  
       2021-10-08 16:20:11 +08:00 via Android
    所以你求出来 n 是多少? 10000?
    KomiSans
        2
    KomiSans  
    OP
       2021-10-08 16:21:46 +08:00
    @mxT52CRuqR6o5 10000 肯定不对啊 10000 是总和...
    lisianthus
        3
    lisianthus  
       2021-10-08 16:25:31 +08:00
    算出来 n = 12367 的时候,总和是 10000.043008275803,n 不是整数
    dvsilch
        4
    dvsilch  
       2021-10-08 16:35:54 +08:00
    每次加一个数不就行了

    如果当前 n - 1 项总和 sum 小于 10000,那 sum 就再加上 1000 / n 再判断一次
    noe132
        5
    noe132  
       2021-10-08 16:39:51 +08:00
    https://www.wolframalpha.com/input/?i2d=true&i=solve+xSum%5BDivide%5B1000%2Cn%5D%2C%7Bn%2C1%2Cx%7D%5D+%3D+10000+x+%3E+0


    解出来 x 并不为整数,约等于 12366.5
    所以 12366 时小于 10000,12367 时大于 10000
    KomiSans
        6
    KomiSans  
    OP
       2021-10-08 16:41:22 +08:00
    我感觉我的解题思路总是那么谜
    013231
        7
    013231  
       2021-10-08 17:07:03 +08:00
    不限定语言和库的话...

    >>> import numpy as np
    >>> print(np.argmax(np.cumsum(1 / np.arange(1, np.exp(10))) > 10))
    12366

    n 等于 12367 时,数列和首次超过 10000.
    上面的式子中用 np.exp(10)限制搜索的上限,为什么可以做如此限定,请自行搜索“partial sum of the harmonic series”。
    zydxn
        8
    zydxn  
       2021-10-08 17:09:19 +08:00
    确定问的不是大于等于 10000 的临界值吗
    jorneyr
        9
    jorneyr  
       2021-10-08 17:12:35 +08:00   ❤️ 2
    1000/1+1000/2+1000/3+...+1000/n=10000
    =>
    1000 * (1 + 1/2 + 1/3 + ... + 1/n)
    因为 1+1/2+1/3+1/4+...+1/2007+1/2008=ln(2008)+C=8.1821 (约),C 为欧拉常数 数值是 0.5772
    =>
    Ln(N)+C=10000

    最终是一个数学问题。如果使用迭代逐项计算,得分不高,如果转换为数学问题则会加分不少。
    jorneyr
        10
    jorneyr  
       2021-10-08 17:14:13 +08:00   ❤️ 2
    利用“欧拉公式”:1+1/2+1/3+……+1/n=ln(n)+C,C 为欧拉常数 数值是 0.5772
    KomiSans
        11
    KomiSans  
    OP
       2021-10-08 17:17:03 +08:00
    @jorneyr 数学家思维 我这个单纯是为了验证我的写法对不对
    MoYi123
        12
    MoYi123  
       2021-10-08 17:18:17 +08:00   ❤️ 1
    明显 n 越大, 计算出的答案越大, f(n) 是一个单调函数.
    所以用二分法可解
    MoYi123
        13
    MoYi123  
       2021-10-08 17:29:44 +08:00
    不对,sb 了,求这个函数结果的过程中就能得到答案了,如果不用上面的数学做法,二分法反而慢了.
    crayygy
        14
    crayygy  
       2021-10-08 17:32:21 +08:00   ❤️ 2
    等式两边同除 1000 以后就是调和级数了 https://zh.wikipedia.org/wiki/%E8%B0%83%E5%92%8C%E7%BA%A7%E6%95%B0
    jxxz
        15
    jxxz  
       2021-10-08 17:39:49 +08:00
    ```
    target = 10000
    n = 1
    now = 0

    while True:
    if now >= target:
    break
    now += 1000/n
    n += 1


    print(n)
    ```

    这样吗 随便写了下
    jxxz
        16
    jxxz  
       2021-10-08 17:47:46 +08:00
    又看了下 判断顺序有点问题 break 判断放 now+=下面,差不多这个意思
    fhl
        17
    fhl  
       2021-10-08 18:29:24 +08:00
    let sum = 0;
    let num = 0;

    while(sum <= 10000) {
    num++;
    sum += 1000 / num;
    }

    console.log(num);
    fhl
        18
    fhl  
       2021-10-08 18:34:26 +08:00
    @fhl 果然需要换成算法解,换成 100000 纯计算就没边了
    longgediyi999
        19
    longgediyi999  
       2021-10-08 18:36:36 +08:00
    let start = 0

    for (let index = 1; index <= Infinity; index++) {
    start += 1000 / index
    if (start > 10000) {
    console.log(start, index)
    return
    }
    }
    ccde8259
        20
    ccde8259  
       2021-10-08 18:38:34 +08:00 via iPhone
    调和级数的近似+二分 /牛顿
    BiChengfei
        21
    BiChengfei  
       2021-10-08 19:16:00 +08:00
    如果不局限于 JS,也可能考察数据类型吧
    整形 / 整形,得到的是整形,永远不可能等于 10000

    算法解是很牛,如果是普通职位,面试官都不一定知道,或许只是想考验你数据类型、临界值处理、需求沟通、需求判断能力
    SoloCompany
        22
    SoloCompany  
       2021-10-08 20:42:57 +08:00
    @jorneyr C 取 0.5772 的精度不够, Math.exp(10 - 0.5772) = 12367.161838810916 得到的结果大了 1, 要再多两位的精确度 0.577215 才能得到正确的结果 12366.976332774619

    默认题目要求应该是精确值而不是约数, 那么迭代应该是最优解
    nicehyj
        23
    nicehyj  
       2021-10-08 20:50:25 +08:00
    这玩意有点像斐波那契数列
    qinwangzeng
        24
    qinwangzeng  
       2021-10-08 21:57:43 +08:00
    感觉你们想太复杂了?
    '''go
    func Test2110082149(t *testing.T) {
    sum := 0
    for n := 1; n < math.MaxInt64; n++ {
    sum += 1000 / n
    if sum == 10000 {
    fmt.Println(n)
    return
    }
    }
    }
    '''
    跑了 10 秒没跑出结果,此题无解
    qinwangzeng
        25
    qinwangzeng  
       2021-10-08 22:06:08 +08:00
    按题目意思,n 是整数
    liuidetmks
        26
    liuidetmks  
       2021-10-09 05:27:22 +08:00 via iPhone
    刚百度了下,除了 n=1 时以外,没有任何一个调和数是整数

    这什么岗位?
    whosesmile
        27
    whosesmile  
       2021-10-09 11:14:58 +08:00
    n=1 啊,这还写什么程序?
    换个思路,左右等式全部用 1 除,然后你就发现了,只能是 1 了啊
    MissThee
        28
    MissThee  
       2021-10-09 11:38:07 +08:00
    @whosesmile n=1 等式不就成 1000/1=10000 了。。。
    whosesmile
        29
    whosesmile  
       2021-10-09 14:35:20 +08:00
    @MissThee 给我问懵逼了,任何数除以 1 等于它本身,这不对吗?
    Frankcox
        30
    Frankcox  
       2021-10-09 15:00:04 +08:00
    @whosesmile 左边是 1000,右边是 10000,,,,,,
    whosesmile
        31
    whosesmile  
       2021-10-11 10:23:27 +08:00
    @Frankcox @MissThee 尴尬,惭愧惭愧, 看错了...
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1143 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 38ms · UTC 18:36 · PVG 02:36 · LAX 11:36 · JFK 14:36
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.