5

Дана следующая задача: есть число N (N <= 2 * 10 ^ 9), требуется разложить его на сумму не более, чем восьми кубов натуральных чисел (если это невозможно - вывести IMPOSSIBLE). Если есть несколько ответов - вывести любой. Я написала следующее:

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector <long long> cubes, cubes2;
long long n, a, n1;
int f(int counter) {
    if (counter > 8) {
        return -1;
    }
    if (n <= 0) {
        return 1;
    }
    cubes.push_back((long long)cbrt(n));
    n -= pow((long long)cbrt(n), 3);
    f(counter += 1);
}
int f2(int counter) {
    if (counter > 8) {
        return -1;
    }
    if (n1 <= 0) {
        return 1;
    }
    if ((long long)cbrt(n1) - 1 < 2) {
        cubes2.push_back((long long)cbrt(n1));
        n1 -= pow((long long)cbrt(n1), 3);
    }
    else {
    cubes2.push_back((long long)cbrt(n1) - 1);
    n1 -= pow((long long)cbrt(n1) - 1, 3);
    }
    f2(counter += 1);
}
int main() {
    int j;
    cin >> n;
    n1 = n;
    f(0);
    f2(0);
    if (cubes.size() <= 8) {
        for (int i = 0; i < cubes.size(); i++) {
            cout << cubes[i] << " ";
        }
    }
    else if (cubes2.size() <= 8) {
        for (int i = 0; i < cubes2.size(); i++) {
            cout << cubes2[i] << " ";
        }
    }
    else {
        cout << "IMPOSSIBLE";
    }
}

Увы, это работает не всегда. Например, это не работает на числах 1079 и 79 - выводит IMPOSSIBLE, хотя это возможно. Для того, чтобы это работало, нужно как - то скомбинировать f и f2, поскольку, например, при разложении числа 1079 сначала должна сработать функция f, а потом всегда f2. Да, при разложении кубы могут повторяться, т.е. 17 раскладывается как 2 2 1. Так же необязательно выводить оптимальное разложение, например, для числа 9 приемлемым вариантом будет 2 1.

2 ответа 2

5

Кубов, которые могут участвовать в разложении, всего 1259. Предвычислим их и сложим в таблицу - теперь это просто слагаемые.

Для данного числа N найдём (например, бинарным поиском) максимальный возможный куб Q в таблице и попробуем решить задачу для меньшей размерности N-Q. Не получается - пройдём в цикле по меньшим кубам.

Таким образом, получится рекурсивная функция с аргументами N и Count (ограничение на 8). Если N равно нулю - нашли.

Решённые подзадачи можно складывать в словарь для оптимизации (подвид динамического программирования)

6
  • а что вы имеете ввиду под "предвычислим их"? просто в цикле складывать в массив все числа, меньше либо равные cbrt(n)? 11 ноя 2020 в 6:51
  • Да, посчитать i^3 (1,8,27..), пока не превысит N, и сложить в вектор или массив.
    – MBo
    11 ноя 2020 в 6:57
  • Кубов, которые могут участвовать в разложении, всего 1259. Это с чего бы? Скажем, 7 = 2^3 + (-1)^3. Не квадраты же...
    – Akina
    11 ноя 2020 в 7:10
  • 2
    @Akina Хотя у автора не указано, но кубов натуральных чисел
    – MBo
    11 ноя 2020 в 7:12
  • @Akina кубический корень из 2 * 10 ^ 8 = 1259, поэтому 11 ноя 2020 в 7:13
2

Перевел идеи MBo в код.

#include <stack>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

vector<int> cbs;

bool solve(int N, stack<int>& sol, int count, map<int, int>& no) {

    if (N == 0) return true;

    if (N != 0 && count == 0) return false;

    for (int i = cbs.size() - 1; i >= 0; --i) {

        if (cbs[i] > N) continue;

        if (cbs[i] == N) {
            sol.push(i + 1);
            return true;
            }

        if (no[N - cbs[i]] < count) {
            sol.push(i + 1);

            if (solve(N - cbs[i], sol, count - 1, no)) return true;
            else no[N - cbs[i]] = count;

            sol.pop();
            }
        }

    return false;
    }


int main() {
    for (int i = 1; i <= 1259; ++i) cbs.push_back(i * i * i);

    stack<int> sol;
    map<int, int> no;
    int N;
    cin >> N;

    if (solve(N, sol, 8, no)) {
        while (!sol.empty()) {
            cout << sol.top() << " ";
            sol.pop();
            }
        }
    else cout << "IMPOSSIBLE";

    cout << endl;
    }

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.