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

V2EX = way to explore

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

现在注册

已注册用户请登录

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

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

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

奇怪

Nodejs

面试

写法

31 条回复 • 2021-10-11 10:23:27 +08:00

mxT52CRuqR6o5

2021-10-08 16:20:11 +08:00 via Android

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

KomiSans

2021-10-08 16:21:46 +08:00

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

lisianthus

2021-10-08 16:25:31 +08:00

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

dvsilch

2021-10-08 16:35:54 +08:00

每次加一个数不就行了

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

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

2021-10-08 16:41:22 +08:00

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

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

2021-10-08 17:09:19 +08:00

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

jorneyr

2021-10-08 17:12:35 +08:00

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

2021-10-08 17:14:13 +08:00

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

KomiSans

2021-10-08 17:17:03 +08:00

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

MoYi123

2021-10-08 17:18:17 +08:00

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

MoYi123

2021-10-08 17:29:44 +08:00

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

crayygy

2021-10-08 17:32:21 +08:00

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

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

2021-10-08 17:47:46 +08:00

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

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

2021-10-08 18:34:26 +08:00

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

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

2021-10-08 18:38:34 +08:00 via iPhone

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

BiChengfei

2021-10-08 19:16:00 +08:00

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

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

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

2021-10-08 20:50:25 +08:00

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

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

2021-10-08 22:06:08 +08:00

按题目意思，n 是整数

liuidetmks

2021-10-09 05:27:22 +08:00 via iPhone

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

这什么岗位？

whosesmile

2021-10-09 11:14:58 +08:00

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

MissThee

2021-10-09 11:38:07 +08:00

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

whosesmile

2021-10-09 14:35:20 +08:00

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

Frankcox

2021-10-09 15:00:04 +08:00

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

whosesmile

2021-10-11 10:23:27 +08:00

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