所有自然数总和N,反转总和为1

Question

我有一个问题要解决.N给出了自然数.我需要找到一个自然数列表,它总结了给定的数字,同时反转最多为1.

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

a,b,c不必是唯一的.

我在Java中提出了以下代码.它适用于简单的情况,但已经非常缓慢N > 1000.

如何重写方法,以便即使对数百万人也能快速工作？也许,我应该放弃递归或用数学技巧切断一些分支,我想念？

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

Answer 1

由Graham,RL于1963年发表的论文"分区上的一个定理"表明,对于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的分解