0

Имеется задача. Во время шифрования алгоритм принимает символы шифруемого текста по одному и заменяет этот символ на один другой символ. Кодировка состоит из m символов, поэтому можно считать, что текст представляет собой последовательность натуральных чисел, не превосходящих. Во время работы алгоритм шифрования поддерживает перестановку натуральных чисел от 1 до m. В начале работы перестановка тождественна. Когда алгоритму на вход поступает символ x, алгоритм заменяет его на номер позиции в перестановке (в 1-индексации), на которой находится символ x, а также переносит x в начало перестановки. Например, если в некоторый момент работы алгоритма перестановка символов в нём равна [3, 1, 2], а на вход подаётся символ 1, то символ 1 будет заменён на символ 2, поскольку 1 стоит в перестановке на второй позиции, а перестановка примет вид [1, 3, 2].

Я написал код:

def encrypt(disp):
    res = []
    for i in input().split():
        pos = disp.index(int(i))
        res.append(pos + 1)
        disp = [disp[pos]] + disp[:pos] + disp[pos + 1:]
    return res

На вход поступает начальное состояние перестановки. Например [1, 2, 3, 4]. Пример работы алгоритма: 2 1 2 3 1 3 1 -> 2 2 2 3 3 2 2. Проблема в том, что мой алгоритм не укладывается в отведенный лимит времени. Может, есть способы ускорить работу? Работа алгоритма станет понятней если его показать таблицей. Зашифруем слово 2 3 1 2 1 1 1. Пусть x - входная буква, p - состояние перестановки на момент вхождения, y - результат.

c[

2
  • После неоднократного чтения условия понятнее не стало. Так и в задаче сформулировано?
    – rokitoker
    1 апр 2020 в 15:32
  • @rokitoker Добавил схему работы алгоритма
    – exeynod
    1 апр 2020 в 16:23

1 ответ 1

0

Ну, как минимум.

input().split() вынести за цикл, после ввода определять количество введенных знаков, порождать res сразу нужного размера а потом работать с ним не как с списком динамически изменяемого размера, а как с массивом.

3
  • Это незначительно ускорит работу
    – exeynod
    1 апр 2020 в 19:34
  • @exeynod значит вы не очень понимаете, на сколько ресурсоемкая процедура добавления элемента в динамический список и на сколько операции над массивами быстрее операций со списками.
    – passant
    2 апр 2020 в 12:37
  • что вы понимаете под статическим массивом в python тогда? Numpy использовать нельзя
    – exeynod
    2 апр 2020 в 16:20

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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