Вопрос по информатике:
Вася хочет представить число 2018 в виде суммы кубов натуральных чисел, содержащих наименьшее количество слагаемых. Помогите ему это сделать.
В качестве ответа выведите слагаемые суммы в порядке возрастания, разделяя их одинарными пробелами. Например, для числа 10 представление с наименьшим количеством слагаемых есть 8+1+1 (8 – это 2 в кубе, 1 – это 1 в кубе), поэтому в качестве ответа нужно было бы вывести такой набор чисел: 1 1 8. Если возможных ответов с представлением числа в виде наименьшего возможного количества слагаемых несколько, выведите любой.
- 18.02.2018 16:16
- Информатика
- remove_red_eye 14935
- thumb_up 27
Ответы и объяснения 1
Программа на python 3, решающая эту задачу для произвольного n (в условии n = 2018):
n = int(input())
lens = list(range(n + 1))
max_terms = [1] * (n + 1)
t = 2
while t**3 <= n:
max_term = t**3
for k in range(max_term, n + 1):
if lens[k] > 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])
- 19.02.2018 10:57
- thumb_up 31
Знаете ответ? Поделитесь им!
Есть сомнения?
Не нашли подходящего ответа на вопрос или ответ отсутствует? Воспользуйтесь поиском по сайту, чтобы найти все ответы на похожие вопросы в разделе Информатика.
Трудности с домашними заданиями? Не стесняйтесь попросить о помощи - смело задавайте вопросы!
Информатика — наука о методах и процессах сбора, хранения, обработки, передачи, анализа и оценки информации с применением компьютерных технологий, обеспечивающих возможность её использования для принятия решений.