我有一个问题要解决。 N
自然数给定。我需要找到一个自然数列表,这些自然数求和为给定数,同时求和为 1。
a + b + c + ... = N
1/a + 1/b + 1/c + ... = 1
a
、b
、c
不必是唯一的。
我用 Java 编写了以下代码。它适用于简单的情况,但对于 N > 1000
来说已经非常慢了。
我如何重写该方法,使其即使对数百万也能快速运行?也许,我应该放弃递归或用我错过的数学技巧切断一些分支?
上海商会:
private final static double ONE = 1.00000001;
public List<Integer> search (int number) {
int bound = (int)Math.sqrt(number) + 1;
List<Integer> list = new ArrayList<Integer>(bound);
if (number == 1) {
list.add(1);
return list;
}
for (int i = 2; i <= bound; i++) {
list.clear();
if (simulate(number, i, list, 0.0)) break;
}
return list;
}
//TODO: how to reuse already calculated results?
private boolean search (int number, int n, List<Integer> list, double sum) {
if (sum > ONE) {
return false;
}
//would be larger anyway
double minSum = sum + 1.0 / number;
if (minSum > ONE) {
return false;
}
if (n == 1) {
if (minSum < 0.99999999) {
return false;
}
list.add(number);
return true;
}
boolean success = false;
for (int i = 2; i < number; i++) {
if (number - i > 0) {
double tmpSum = sum + 1.0 / i;
if (tmpSum > ONE) continue;
list.add(i);
success = search(number - i, n - 1, list, tmpSum);
if (!success) {
list.remove(list.size() - 1);
}
if (success) break;
}
}
return success;
}
最佳答案
论文"A Theorem on Partitions", 1963 by Graham, R. L.表明对于 N > 77 存在一个解决方案,其中使用的数字是本能的,并提出了一种算法来找到这样的分解。
算法如下:
- 如果 N 小于 333 ,使用预先计算的表来获取结果。
- 如果 N 是奇数,找到
(N-179)/2
的分解d1, d2, d3, d4, ..., dk
,然后3, 7, 78, 91, 2*d1, 2*d2, 2*d3, ..., 2*dk
是 N 的分解 - 如果 N 是偶数,找到
(N-2)/2
的分解d1, d2, d3, d4, ..., dk
,然后2, 2*d1, 2*d2, 2*d3, ..., 2*dk
是 N 的分解
但由于您不关心分解中有不同的数字,您可以将预计算结果表的大小减少到 60,如果 N 是奇数,找到分解 d1, d2, d3, d4, ..., dk
为 (N-9)/2
,然后是 3, 6, 2*d1, 2*d2, 2*d3, ... , 2*dk
是 N 的分解。
关于java - 总和为 N 且逆数总和为 1 的所有自然数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16588372/