从 1 到 100 这 100 个数字中任意选取 10 个数,求这 10 个数字的倒数之和为 1 的所有可能结果。
扩展: 从 1 到 n 这 n 个数字中随机选取 m 个数,求这 m 个数字的倒数之和为 1 的所有可能结果。
1
vituralfuture 250 天前 via Android
枚举法,注意一下为了避免浮点数误差,不要直接取倒数,把先分母弄到等号另外一边,消除分母
|
2
Rang666 250 天前 via iPhone
递归就行,第一个是 a ,就 1-100 选 9 个,求倒数是 1-1/a
|
3
forgottencoast OP |
4
klo424 250 天前
标题应改为“算法求解”
|
5
klo424 250 天前
然后建议问问 GPT
|
6
phrack 250 天前
递归加减枝,标准操作
|
7
neteroster 250 天前 1
每次选择上界稍微剪一下(选 m 个倒数和为 k 的话最小那个一定要小于 m/k 了)就跑的出来了,总共 69014 组,不知道有没漏。应该还可以再优化。
|
8
forgottencoast OP @klo424 它不会,或者说给出的答案很差。
|
9
forgottencoast OP |
10
neteroster 249 天前 1
@forgottencoast 我最近在学 Racket ,所以用这个语言写的。这语言编译后基本操作大概比 C / C++ 慢一个数量级。
我后来还加了一个小优化,最后三个数直接查表(提前算好)。总时间在我电脑上大概 9 秒,代码和具体计时详见: https://gist.github.com/neteroster/9f59b6a868ef26fc7a43ce6a3eaac4bd |
11
forgottencoast OP |
12
v24radiant 248 天前
根据上面的代码改成 python, 优化一下剪枝, 总运行时间如下:
3.18 s ± 211 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) python 代码如下: ```python %%timeit import itertools min_sum = [0 for _ in range(10)] min_sum[0] = 1 / 100 for i in range(1, 10): min_sum[i] = min_sum[i - 1] + 1 / (100 - i) with open('resf.txt', 'w') as res_port: res_port.write("make table: \n") sum_table = {} for i in range(1, 101): for j in range(i + 1, 101): for k in range(j + 1, 101): key = 1 / i + 1 / j + 1 / k if key not in sum_table: sum_table[key] = [] sum_table[key].append((k, j, i)) def backtrack(path, start, target, n): if target < min_sum[n - 1]: return if n == 3: if target in sum_table: for c in sum_table[target]: if c[2] >= start: res_port.write(str(list(path) + list(c)) + '\n') else: kmax = int(n / target) end = min(100, kmax) + 1 start = max(start, int(1 / target)) for i in range(start, end): if 1 / i < target: backtrack(path + (i, ), i + 1, target - 1 / i, n - 1) res_port.write("backtrack: \n") backtrack((), 1, 1, 10) ``` |
13
neteroster 248 天前 via Android
@v24radiant 遗憾的是,由于 Python 默认并不以精确方式表示与运算有理数,所以如此查表将遗漏大部分的解。
|
14
v24radiant 248 天前
@neteroster #13 说反了吧, 应该是由于精度问题错误算多了答案吧😂 实际用 decimal 模块精确计算答案, 最终结果只有 242 条╮(╯▽╰)╭
|
15
neteroster 248 天前 via Android
@v24radiant 算多也是有可能的,不过我的直觉是算少(查表的时候意外撞上的可能性感觉不大),不过反正都是不精确的。
几百条肯定是少了,我原程序算的六万多条都化成整数运算检验过的,只可能少不会多。 |
16
neteroster 248 天前 via Android
@neteroster 另外,用 decimal 应该也不行。它能正确表示精确的 1/3 吗?
|
17
forgottencoast OP @neteroster
基本确定 69014 是对的,很多人算出这个结果。 |
18
v24radiant 248 天前
|
19
forgottencoast OP @v24radiant
目前看到的解决方案努力方向都是剪枝。 |
20
sillydaddy 245 天前
这个帖子发在「数学」节点下面,每人想过用一点数学知识吗?
一个数学方面的线索: 如果 p,q,r,s...都是素数(比如 2,3,5,7,...),那么 1/p + 1/q + 1/r + 1/s + ... 永远也不会等于整数(例如 1 )。 另一个数学方面的线索: 如果 p,q,r 和 s 这两组数互素(比如 2,4,7 作为一组,3 作为一组),那么 1/p + 1/q + 1/r + 1/s + ...不可能等于整数(例如 1 ),而 2,3,6 的倒数和是 1 ,它们无法拆分为互素的两组数。 通过上述(有关素数的)线索,应该可以排除大量的组合。 |
21
forgottencoast OP |