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

[KomiSans]

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

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

[mxT52CRuqR6o5]

所以你求出来 n 是多少？ 10000?

[KomiSans]

@mxT52CRuqR6o5 10000 肯定不对啊 10000 是总和...

[lisianthus]

算出来 n = 12367 的时候，总和是 10000.043008275803，n 不是整数

[dvsilch]

每次加一个数不就行了

如果当前 n - 1 项总和 sum 小于 10000，那 sum 就再加上 1000 / n 再判断一次

[noe132]

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]

我感觉我的解题思路总是那么谜

[013231]

不限定语言和库的话...

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

确定问的不是大于等于 10000 的临界值吗

[jorneyr]

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]

利用“欧拉公式”：1+1/2+1/3+……+1/n=ln(n)+C,C 为欧拉常数 数值是 0.5772

[KomiSans]

@jorneyr 数学家思维 我这个单纯是为了验证我的写法对不对

[MoYi123]

明显 n 越大, 计算出的答案越大, f(n) 是一个单调函数.
所以用二分法可解

[MoYi123]

不对,sb 了,求这个函数结果的过程中就能得到答案了,如果不用上面的数学做法,二分法反而慢了.

[crayygy]

等式两边同除 1000 以后就是调和级数了 https://zh.wikipedia.org/wiki/%E8%B0%83%E5%92%8C%E7%BA%A7%E6%95%B0

[jxxz]

```
target = 10000
n = 1
now = 0

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


print(n)
```

这样吗 随便写了下

[jxxz]

又看了下 判断顺序有点问题 break 判断放 now+=下面，差不多这个意思

[fhl]

let sum = 0;
let num = 0;

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

console.log(num);

[fhl]

@fhl 果然需要换成算法解，换成 100000 纯计算就没边了

[longgediyi999]

let start = 0

for (let index = 1; index <= Infinity; index++) {
start += 1000 / index
if (start > 10000) {
console.log(start, index)
return
}
}

[ccde8259]

调和级数的近似+二分 /牛顿

[BiChengfei]

如果不局限于 JS，也可能考察数据类型吧
整形 / 整形，得到的是整形，永远不可能等于 10000

算法解是很牛，如果是普通职位，面试官都不一定知道，或许只是想考验你数据类型、临界值处理、需求沟通、需求判断能力

[SoloCompany]

@jorneyr C 取 0.5772 的精度不够, Math.exp(10 - 0.5772) = 12367.161838810916 得到的结果大了 1, 要再多两位的精确度 0.577215 才能得到正确的结果 12366.976332774619

默认题目要求应该是精确值而不是约数, 那么迭代应该是最优解

[nicehyj]

这玩意有点像斐波那契数列

[qinwangzeng]

感觉你们想太复杂了？
'''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]

按题目意思，n 是整数

[liuidetmks]

刚百度了下，除了 n=1 时以外，没有任何一个调和数是整数

这什么岗位？

[whosesmile]

n=1 啊，这还写什么程序？
换个思路，左右等式全部用 1 除，然后你就发现了，只能是 1 了啊

[MissThee]

@whosesmile n=1 等式不就成 1000/1=10000 了。。。

[whosesmile]

@MissThee 给我问懵逼了，任何数除以 1 等于它本身，这不对吗？

[Frankcox]

@whosesmile 左边是 1000，右边是 10000，，，，，，

[whosesmile]

@Frankcox @MissThee 尴尬，惭愧惭愧, 看错了...