v24radiant
73 天前
根据上面的代码改成 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)
```