9

I have a problem to solve. N natural number is given. I need to find a list of natural numbers which sum up to that given number and at the same time the inverses up to 1.

a + b + c + ... = N
1/a + 1/b + 1/c + ... = 1

a, b, c don't have to be unique.

I have come up with following code in Java. It works for simple cases, but incredibly slow for already for N > 1000.

How can I rewrite the method so it works fast even for millions? Maybe, I should drop off recursion or cut off some of branches with mathematical trick which I miss?

SSCEE:

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;
}
4

3 回答 3

11

Graham, RL 于 1963 年发表的论文“A Theorem on Partitions”表明，对于 N > 77，存在一个解决方案，其中使用的数字是明确的，并提出了一种算法来找到这种分解。

算法如下：

  • 如果 N 小于 333 ，则使用预先计算的表来获取结果。
  • 如果 N 是奇数，求 的分解d1, d2, d3, d4, ..., dk，(N-179)/2则3, 7, 78, 91, 2*d1, 2*d2, 2*d3, ..., 2*dk是 N 的分解
  • 如果 N 是偶数，求 的分解d1, d2, d3, d4, ..., dk，(N-2)/2则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 的分解。

于 2013-05-16T14:36:01.517 回答
0

首先，更改第二个条件，以便您不必执行任何浮点运算。将 (1/a+1/b+1/c)=1 更改为 bc+ac+ab = abc。您可以使用 O(k) 除法来计算（提示：先计算右侧）。

其次，巩固你的数字。示例：如果您有 a,b,c,a,b 作为输入，则合并欺骗并将其存储为两个 a、两个 b 和一个 c。

第三，有一个基于 DP 的解决方案可以有效地解决第一个问题。您还必须存储所有部分答案。但是，您可以非常有效地存储部分答案。例如。将“x=bc+ac+ab”和“y=abc”存储为部分解。当您将 d 添加到组合中时，您有 xnew = x*d+y 和 ynew=y*d 。

如果您使用这三个指针，您的解决方案可能会更有效。

于 2013-05-16T14:21:40.793 回答
-2

如果数字不必是整数a = b = c = ... = sqrt(N)是一个解决方案。

如果允许负数，则找到a和b这样8a+3b+1=N（您可以使用欧几里德算法计算它们），然后您想要的列表是：数字 3（3a 次）、数字 2（2b 次）和数字 1（1-时间）

于 2013-05-16T13:53:26.393 回答