A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may ask for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.
The text file, keylog.txt, contains fifty successful login attempts.
Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length
Для безопасности банковских операций в интернете, пользователя просят ввести 3 случайных символа из пароля. Например, если пароль пользователя 531278, его могут попросить ввести 2ой, 3ий и 5ый символ; ожидаемый ответ 317. Текстовый файл projecteuler.net/project/keylog.txtkeylog.txt содержит 50 успешных попыток входа в систему. Зная, что символы всегда упорядочены в порядке возрастания, надо проанализировать файл и определить наикоротчайший возможный пароль неизвестной длины.
Кстати, я так понимаю, сложнее не получить ответ, а формализовать его так, чтобы заложиться на все возможные варианты - одинаковые цифры на разных позициях, недостаточно данных и т.д.
В предположении, что каждая цифра встречается в пароле только один раз, а в списке частичных паролей встречается как минимум один раз, надо фактически получить сортировку массива.
Хотя, как сейчас подумалось, для создания оптимального алгоритма есть резервы поработать.
Если убрать условие наикоротчайшести, то задачи станет супер сложной имхо. Так как понадобиться бороться с циклами итд. Можно подумать о переформулировке кстати и попробовать решить усложенный вариант.
Тогда е-рейтинг является полнейшей билебердой
Вот еще пример. Набор символов (х,р,и,с,т,о,с). Строка
отцвели уж давно. хризантемы в саду, но любовь все живет
Попробум тупо - создадим словарик 33 массивчик a. Запомним число букав в словарике.
Поставим там 1 для нужных символов
Поехали по строке - если a!=1 - игнор
Если 1, то ставим символ в итоговую строку, в словарике на a ставим ну 2
Доезжаем до конца. Если строка итоговая имеет достаточно букав, то получилось.
Не совсем понял Ваше решение, а как гарнтируется каратчайшесть? И что будет если некоторые символы повторяются? Например символы (а,б,а,с). Строка: Одна баба сказала слава богу. Или Вы предлагаете тупо найти все возможные решения, а потом выбрать самое короткое?
Не совсем понял Ваше решение, а как гарнтируется каратчайшесть?
Кратчайшесть?... Будет найдено ровно столько символов, сколько требуется.
PP написал(а):
И что будет если некоторые символы повторяются?
Да, надо немного поменять.
Изначально массив словаря содержит количество нужных букв
Например (а,б,а,с) - будет (2,1,............., 1, ............)
При нахождении нужной буквы делаем -- в нужной позиции.
Как только останутся все нули, значит все нашли
(2,1,............., 1, ............)
Одна баба сказала слава богу
(1,1,............., 1, ............)
Одна баба сказала слава богу
(1,0,............., 1, ............)
Одна баба сказала слава богу
(0,0,............., 1, ............)
Одна баба сказала слава богу
(0,0,............., 0, ............)
Все
Кратчайшесть?... Будет найдено ровно столько символов, сколько требуется.
Я наверное туплю, но мне кажется что если бы строка была слава богу одна баба сказала, то Вашим алгоритмом мы найдем слава б, а не баба с. Тоесть надо повторять процесс опять сдвинувшись в начальной позиции на следующую позицию из словарика?
Я наверное туплю, но мне кажется что если бы строка была слава богу одна баба сказала, то Вашим алгоритмом мы найдем слава б, а не баба с. Тоесть надо повторять процесс опять сдвинувшись в начальной позиции на следующую позицию из словарика?
Нет. Цикл идет по самой строке. O(N)
А из словарика мы берем точечно, по коду символа.
А я по-прежнему туплю. Мне кажется, что предложенный алгоритм найдет первое вхождение данных символов, да и то не обязательно самое короткое. Если та баба еще и заикается:\
ссслава богу одна баба сказала, то подстрока начнется с первой с, а не с третьей.
Навскидку, динамическое программирование должно находить решение за О(n^2). Ничего лучше с наскоку придумать не смог.
На симпозиуме по дискретным алгоритмам ACM на этой неделе группа исследователей из MIT представила новый алгоритм быстрого преобразования Фурье sFFT (Sparse Fast Fourier Transform), который на некоторых задачах может быть в десятки или сотни раз быстрее классического БПФ.
Преобразование Фурье предполагает получение коэффициентов («амплитуд») при разложении исходной функции на элементарные составляющие — гармонические колебания с разными частотами. Быстрое преобразование Фурье позволяет ускорить этот процесс за счёт разделения вектора коэффициентов на два вектора, рекурсивном вычислении ДПФ для них, и объединении результатов в одно БПФ. Считается, что метод БПФ предложен в 1805 году Гауссом и переоткрыт в 1965 году, после чего нашёл широкое применение с распространением современных компьютеров. В последние 50 лет предпринималось немало попыток повысить эффективность БПФ, например, FFTW.
Новый алгоритм MIT, как заявляется, работает быстрее FFTW. Сравнение приводится в научной работе, а также на странице проекта.
Алгоритм sFFT (Sparse Fast Fourier Transform) создан на основе двух существующих фильтров (фильтр Гаусса и фильтр Чебышева) и нацелен на то, чтобы быстро найти фрагменты с «разреженным» сигналом (sparse signal) и определить исходную амплитуду в каждом из них. Сигнал разбивается на фрагменты (rapid sampling) до тех пор, пока не останется разреженный сигнал с единственной амплитудой. А уже там новый алгоритм выявляет её в 10 тыс. раз быстрее классического БПФ.
Такой метод не является универсальным, и сейчас учёные пытаются определить, в каких конкретно приложениях он даст наибольшую прибавку в производительности.
Преобразование Фурье предполагает получение коэффициентов («амплитуд») при разложении исходной функции на элементарные составляющие — гармонические колебания с разными частотами. Быстрое преобразование Фурье позволяет ускорить этот процесс за счёт разделения вектора коэффициентов на два вектора, рекурсивном вычислении ...
да простит меня ГИ и все ув. Квантофорумчане, но м.б. это тот самый случай, когда при вычислениях (логарифмических, тригонометрических и т.п. функций, в т.ч. комплекснозначных с ТРЕБУЮЩЕЙСЯ точностью) всего-навсего достаточно определиться с требующейся точностью=дискретностью конечной Вселенной, и тогда сложения и умножения, например в ОДНОМЕРНЫХ координатах комплексной плоскости возможны с большей скоростью (не обязательно аппаратно или таблично, с использованием или без 100ричной системы счисления). З павагай
