Форум » Обработка числовых последовательностей » №3922 (27.62) (два других решения) » Ответить
№3922 (27.62) (два других решения)
beep: Здравствуйте! Предлагаю 2 других решения с использованием динамического программирования. Первый вариант работает чуть быстрее, второй чуть медленнее и выглядит сложнее, но при этом меньше памяти расходует, поскольку не сохраняет ненужные цепочки. Идея примерно одна и та же. Среди решений есть: 1) безымянный вариант: используется что-то вроде перебора, мои варианты в 10 раз быстрее работают 2) Е. Джобс (1 вариант): перебор, мои варианты работают в 250+ раз быстрее 3) Е. Джобс (2 вариант): улучшенный перебор, мои варианты в ~25 раз быстрее 4) Д. Муфаззалов: используется динамическое программирование, но алгоритм очень медленно работает, мои варианты в ~225 раз быстрее. Замеры неточные, просто чтобы продемонстрировать порядок. Первый вариант: [pre2] n = -1 arr = [] with open("27-62b.txt", "r") as f: n = int(f.readline()) for i, x in enumerate(f): x = int(x) arr.append(x) arr.sort() res = {} lMax = -1 buff = [] stop = -1 for x in arr: for i, y in enumerate(buff): step = x - y if step > 100: stop = i continue seed = x % step if step not in res: res[step] = {} if seed not in res[step]: res[step][seed] = { "count" : 1, "nextX" : x } if res[step][seed]["nextX"] == x: res[step][seed]["count"] += 1 lMax = max(lMax, res[step][seed]["count"]) else: res[step][seed]["count"] = 2 res[step][seed]["nextX"] = x + step if stop != -1: buff = buff[stop + 1 : ] stop = -1 buff.append(x) print(lMax) [/pre2] Второй вариант: [pre2] n = -1 arr = [] with open("27-62b.txt", "r") as f: n = int(f.readline()) for i, x in enumerate(f): x = int(x) arr.append(x) arr.sort() res = {} lMax = -1 buff = [] stop = -1 for x in arr: resT = {} keys = sorted(res) for key in keys: if key < x: continue delta = 1 if key == x else 0 for seed in res[key]: for step, count in res[key][seed].items(): keyNew = key + step * delta if keyNew not in resT: resT[keyNew] = {} if seed not in resT[keyNew]: resT[keyNew][seed] = {} resT[keyNew][seed][step] = count + delta lMax = max(lMax, resT[keyNew][seed][step]) for i, y in enumerate(buff): step = x - y if step > 100: stop = i continue seed = x % step keyNew = x + step if keyNew not in resT: resT[keyNew] = {} if seed not in resT[keyNew]: resT[keyNew][seed] = {} if step not in resT[keyNew][seed]: resT[keyNew][seed][step] = 2 if stop != -1: buff = buff[stop + 1 : ] stop = -1 buff.append(x) res = resT print(lMax) [/pre2]
Ответов - 1
Поляков: Спасибо, решения добавлены.
полная версия страницы