DjangoBB LoFi version

Полная версия: acmp №398 Разбиение числа на слагаемые

Начало » Центр помощи » acmp №398 Разбиение числа на слагаемые

Enfoire

Май 30, 2017 20:49:12

Засел на этой задачке. Есть решение, которое улетает по времени, есть другое - улетает по памяти, по времени норм. Как улучшить решение или как принципиально по - другому подойти к нему?

Задано натуральное число x. Найдите число способов представить его в виде суммы четырех натуральных чисел: x = a + b + c + d, где a <= b <= c <= d.

Ввод:
натуральное число

Вывод:
количество разбиений

Решение, вылетающие по памяти:

 import itertools
 
n = int(input())
count = 0
sequence = []
rrange = list(range(1, n - (n // 3)))
 
tools = ([i for i in itertools.combinations_with_replacement(rrange, 3)
          if sum(i) <= n - 1])
 
for i in tools:    
    step = []
    k = n - sum(i)
    if k > 0:
        step.append(sorted(i + (k, ))[:3])
        if sequence.count(step) == 0:
            count += 1
    sequence.append(step)
     
print(count)

Romissevd

Май 30, 2017 21:10:46

А если вот так

 import itertools
n = int(input())
count = 0
sequence = []
rrange = list(range(1, n - (n // 3)))
tools = ([i for i in itertools.combinations_with_replacement(rrange, 4)
          if sum(i) == n])
print(len(tools))

Enfoire

Май 30, 2017 21:20:53

Romissevd
А если вот так

Не смотрел пошагово, но по ответам не добирает. И я думаю все равно по памяти вылетит. Тут надо либо отказываться вообще от функций itertools (а как грамотно тогда организовать перебор?), либо не держать в памяти tools, а выдергивать и оперировать на лету - в этом случае залет по времени..

Romissevd

Май 30, 2017 21:41:31

да там у меня не всегда берет правильные комбинации. подправил - попробуй

 import itertools
n = int(input())
rrange = list(range(1, n))
tools = ([i for i in itertools.combinations_with_replacement(rrange, 4)
          if sum(i) == n])
print(len(tools))

Enfoire

Май 31, 2017 04:33:08

Romissevd
да там у меня не всегда берет правильные комбинации. подправил - попробуй

Долгий( он в интервале на n очень долго формирует четверки, но спасибо!