2
with open('input.txt', 'r') as y:

    num = int(y.readline())

    def recurs(cycle, num):
        if num == 0:
            return 1
        c = 0
        for i in range(1, cycle):
            if num - i < 0:
                break
            c += recurs(i, num - i)
        return c
with open('output.txt', 'w') as f:

    f.write(str(recurs(num + 1, num)))

Сам код полностью рабочий, но при проверке на сайте acmp.ru (задача 16: лесенка) превышает лимит по времени на 9м тесте. После проведенной мною проверки код начинает уходить за лимит времени при вводимом числе 100 и выше. Как ускорить код?

4 ответа 4

4

немного измененный способ gord1402, который работает чуть побыстрее (проверял на N = 1000):

@functools.lru_cache(maxsize=None)
def recurs(cycle, num):
    return 1 if num == 0 else sum(recurs(i, num - i) for i in range(1, min(cycle, num + 1)))

вот так еще чуть-чуть побыстрее:

@functools.lru_cache(maxsize=None)
def recurs(cycle, num):
    if num == 0:
        return 1
    c = 0
    for i in range(1, min(cycle, num + 1)):
        c += recurs(i, num - i)
    return c
1
4

Вы можете использовать functools для этого:

import functools

with open('input.txt', 'r') as y:
    num = int(y.readline())
    @functools.lru_cache(maxsize=None)
    def recurs(cycle, num):
        if num == 0:
            return 1
        c = 0
        for i in range(1, cycle):
            if num - i < 0:
                break
            c += recurs(i, num - i)
        return c
with open('output.txt', 'w') as f:
    f.write(str(recurs(num + 1, num)))
1
  • Помогло, теперь буду знать. Спасибо большое
    – The dark
    20 мая в 17:01
3

Не то, чтобы это было принципиально для данной задачи, у нее достаточно демократичное ограничение аргумента, но решение можно еще значительно ускорить, избавившись от лишнего цикла подсчета суммы.

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

введите сюда описание изображения

Например, имея 9 кубиков можно построить 5 разных лесенок шириной не более 6. Для этого возьмем все лесенки, которые можно построить из этих кубиков, но с меньшей шириной (не более 5)

введите сюда описание изображения

А после отложим 6 кубиков для основания, и из оставшихся сложим все возможные лесенки, опять же с меньшей шириной

введите сюда описание изображения

и положим их на это основание

введите сюда описание изображения

Получим 5 лесенок из 9 кубиков с шириной основания не больше 6

введите сюда описание изображения

И для этого достаточно будет сложить всего два значения - количество лесенок из 9 кубиков с шириной не больше 5 и количество лесенок из 3 кубиков шириной не больше 5

Делать это рекурсивно с кешированием или таблично – решайте сами.

Тонкий момент: да, из нуля кубиков можно построить одну лесенку нулевой ширины – пустую лесенку.

2

немного считирил чтоб написать более быстрый алгоритм:

  1. сгенерировал первые несколько членов последовательности

     1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54, 64, 76, 89, 104, 122, 142, 165, 192, 222, 256, 296, 340, 390, 448, 512, 585, 668, 760, 864, 982, 1113,
    

и отправил их в wolfram alpha, чтоб посмотреть, будет ли найдена аналитическая формула

  1. была найдена к сожалению только рекурентная:

https://www.wolframalpha.com/input?i2d=true&i=1%5C%2844%29+1%5C%2844%29+2%5C%2844%29+2%5C%2844%29+3%5C%2844%29+4%5C%2844%29+5%5C%2844%29+6%5C%2844%29+8%5C%2844%29+10%5C%2844%29+12%5C%2844%29+15%5C%2844%29+18%5C%2844%29+22%5C%2844%29+27%5C%2844%29+32%5C%2844%29+38%5C%2844%29+46%5C%2844%29+54%5C%2844%29+64%5C%2844%29+76%5C%2844%29+89%5C%2844%29+104%5C%2844%29+122%5C%2844%29+142%5C%2844%29+165%5C%2844%29+192%5C%2844%29+222%5C%2844%29+256%5C%2844%29+296%5C%2844%29+340%5C%2844%29+390%5C%2844%29+448%5C%2844%29+512%5C%2844%29+585%5C%2844%29+668%5C%2844%29+760%5C%2844%29+864%5C%2844%29+982%5C%2844%29+1113%5C%2844%29

введите сюда описание изображения

  1. которую я и закодил

код:

import sys
sys.setrecursionlimit(10000)

import functools
@functools.cache
def a(n):
    if n == 0:
        return 1
    else:
        a_sum = sum([sigma(k) * a(n - k) for k in range(1, n + 1)])
        b_sum = 2 * sum([sigma(k) * a(n - 2 * k) for k in range(1, n // 2 + 1)])
        return (a_sum - b_sum) // n


@functools.cache
def sigma(n):
    return sum([i for i in range(1, n + 1) if n % i == 0])

В итоге для N = 1000 скорость возросла в 25 раз и время выполнения уменьшилось с 6,4 сек, до 0,25 сек :)

Ну и главный недостаток - требование к длине рекурсий увеличенное - так что пришлось повышать предел через sys.setrecursionlimit(10000)

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

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