Все натуральные числа, которые суммируются до N и где обратные суммы суммируются до одного

У меня проблема. 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;
}

Ответы

Ответ 1

Статья "Теорема о перегородках" , 1963 г. Грэм, RL показывает, что при N > 77 существует решение, в котором используются числа являются dinstinct и предлагают алгоритм для нахождения такого разложения.

Алгоритм следующий:

Если 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.

Ответ 2

Сначала измените второе условие, чтобы вам не пришлось выполнять арифметику с плавающей запятой. Изменить (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.

Если вы используете эти три указателя, ваше решение может быть более эффективным.

Ответ 3

Если числа не должны быть целыми, то a = b = c = ... = sqrt(N) является решением.

Если отрицательные числа разрешены, найдите a и b такие, что 8a+3b+1=N (вы можете вычислить их с помощью алгоритма Евклида), а затем список, который вы хотите: число 3 (3 раза), число 2 (2b раз) и число 1 (1-a-b раз)