Сумма кубов рекурсией - нахождение лучшей суммы кубов

Question

def sumOfCubes(n):
if n == 0:
    return
sumOfCubes(n - (int(n ** (1/3))) ** 3)
print((int(n ** (1 / 3)) ** 3), end=' ')


sumOfCubes(int(input()))

Важно! Задача должна решаться рекуррентной функцией.

Задача заключается в представлении натурального числа в виде суммы кубов других натуральных чисел, при чем должно быть наименьшее возможное число слагаемых.

Ввод: 271

Вывод: 1 27 27 216

Ввод: 100

Вывод: 1 8 27 64

Сайт, на который отправляется этот код, сообщает о неправильных ответах.

Программа должна вывести разложение переданного ей числа в виде суммы кубов других натуральных чисел. Эта сумма должна состоять из наименьшего количества слагаемых среди всех таких сумм.

Answer 1

def max_cube(n:int)->int:
    return int(n**(1/3))**3

def sum_of_cubes(n):
    if n==0: return [0]
    if n==1: return [1]

    m = max_cube(n)
    return [m]+sum_of_cubes(n-m)

n = 271
print(sum_of_cubes(n))

Answer 2

Вот такой код должен работать:

def main(N:'int>=0'):
    decompositions = []
    cubes = [i*i*i for i in range(int(N**(1/3)), 0, -1)]
    r = to_sum_of_cubes(N, cubes, decompositions)
    print(decompositions[0])
       
def to_sum_of_cubes(N:'int>=0', cubes:list, decompositions:list):
    if N in (0, 1):
        decompositions.append([N])
        return
    if not cubes:
        return
    n = N
    decomposition = []
    for idx in range(len(cubes)):
        while n >= cubes[idx]:
            decomposition.append(cubes[idx])
            n -= cubes[idx]
            
    decompositions.append(decomposition)
    to_sum_of_cubes(N, cubes[1:], decompositions)
    decompositions.sort(key=lambda x: len(x))
    decompositions = [decompositions[0]]

if __name__ == '__main__':
    main(32)

БЛОГ НА HUSL

Сумма кубов рекурсией - нахождение лучшей суммы кубов

Ответы (2 шт):