Вася желает представить число 2018 в виде суммы кубов естественных чисел,
Вася желает представить число 2018 в виде суммы кубов естественных чисел, содержащих меньшее количество слагаемых. Помогите ему это сделать.
В качестве ответа выведите слагаемые суммы в порядке возрастания, деля их одинарными пробелами. К примеру, для числа 10 представление с минимальным количеством слагаемых есть 8+1+1 (8 это 2 в кубе, 1 это 1 в кубе), поэтому в качестве ответа необходимо было бы вывести таковой набор чисел: 1 1 8. Если вероятных ответов с представлением числа в виде меньшего вероятного количества слагаемых несколько, выведите любой.
1 ответ
Viktor
Мысль решения: если можно использовать только 1^3, то ответ явен, дальше пытаемся выяснить, не станет ли лучше, если разрешить использовать 2^3, 3^3 и т.д.
Программка на python 3, решающая эту задачку для случайного n (в условии n = 2018):
n = int(input())
lens = list(range(n + 1))
max_terms = [1] * (n + 1)
t = 2
while t**3 lt;= n:
max_term = t**3
for k in range(max_term, n + 1):
if lens[k] gt; 1 + lens[k - max_term]:
lens[k] = 1 + lens[k - max_term]
max_terms[k] = max_term
t += 1
for_print = []
for _ in range(lens[n]):
for_print.append(max_terms[n])
n -= max_terms[n]
print(*for_print[::-1])
Программка на python 3, решающая эту задачку для случайного n (в условии n = 2018):
n = int(input())
lens = list(range(n + 1))
max_terms = [1] * (n + 1)
t = 2
while t**3 lt;= n:
max_term = t**3
for k in range(max_term, n + 1):
if lens[k] gt; 1 + lens[k - max_term]:
lens[k] = 1 + lens[k - max_term]
max_terms[k] = max_term
t += 1
for_print = []
for _ in range(lens[n]):
for_print.append(max_terms[n])
n -= max_terms[n]
print(*for_print[::-1])
Borka Kasabkin
а какой ответ?
, оставишь ответ?
Похожие вопросы
-
Вопросы ответы
Новое
NEW
Статьи
Информатика
Статьи
Последние вопросы
задание экономиоти
Рассмотри ситуацию: человек живёт на Крайнем Се-вере. С помощью каких
Экономика.
Человек живет на Крайнем Севере. С помощью каких благ удовлетворяются потребности
Экономика.
там лежат три яйца.у дома рос клен.Это гнездо сойки.на клёне гнездо
Русский язык.
Тыныштық күйіндегі карусель 35 с-та 3,0 рад/с бұрыштық жылдамдықпен үдей қозғалады.
Разные вопросы.
Сочинение на тему "Русский язык не сможет умереть!"
Математика.
Приветствую!
Меня зовут Станислав, я представляю компанию under.site.
Хотел бы предложить интересное решение
Разные вопросы.
Масса трёх одинаковых пакетов чая 180г чему равна масса
Математика.
Газообразный аммиак объёмом 2.24 л (н.у.) был полностью поглощён 14.68 мл
Химия.
Упражнение 2 Выпишите глаголы и вставьте пропущенные буквы
Русский язык.
Радиус окружности, описанной около равностороннего треугольника, равен 6. Найдите сторону треугольника
Геометрия.
Облако тегов