На двери висит цифровой замок с последовательным нажатием кнопок.
Код состоит из 2-3-4 цифр (в общем случае — N, где N известно, N>=2).
Порядок цифр в коде может быть существенным или несущественным (123 = 231).
Цифры в коде могут повторяться либо не повторяться.
В замке — сдвиговый регистр, поэтому как только в последовательности нажатий встретится код, он отопрет дверь.
Очевидно, что оценка сверху — это (D^N)*N (D — число кнопок): вводим N-значные числа одно за другим.
оценка снизу — (D^N)+N-1: все N-значные числа накладываются друг на друга.
Задачи:
Написать программу, порождающую минимальную последовательность.
Или близкую к минимальной.
С учетом того, что длина последовательности растет экспоненциально, рожать последовательность с фиксированными затратами памяти
Еще несколько интересных вопросов:
Какова вероятность отпирания замка равномерно-случайной последовательностью? То есть — какова средняя длина такой последовательности? Как она соотносится с гарантированной?
Есть ли неравномерно случайные последовательности (например, марковские), которые более оптимальны?
Если N неизвестно, но лежит в диапазоне [N1..N2], и предполагается, что меньшие значения N вероятнее больших, то как оптимизировать гарантированную последовательность?
Вот, нагородил в ассортименте.
Такие замки (и эквивалентные им) вполне распространены. В том числе — сейфовые крутилки "20 влево, 20 вправо, шаг вперед и два назад".
К>На двери висит цифровой замок с последовательным нажатием кнопок...
Если это кнопки (не сейфовая крутилка, зависящая от направления поворота), то наилучший вариант — случайный перебор возможных вариантов. Он, к стати, и самый оптимальный. Доказано проверками криптограффических алгоритмов.
Здравствуйте, Real 3L0, Вы писали:
R3>Если это кнопки (не сейфовая крутилка, зависящая от направления поворота), то наилучший вариант — случайный перебор возможных вариантов. Он, к стати, и самый оптимальный. Доказано проверками криптограффических алгоритмов.
Сейфовая крутилка с D положениями не сильнее, чем мой замок с D^2 кнопками
Кстати, у Ричарда Фейнмана в его бессмертном "Вы конечно шутите, мистер Фейнман", рассказано, как он ковырял такие крутилки.
Насчет случайности — все же хотелось бы услышать нечто аргументированное.
Здравствуйте, Кодт, Вы писали:
К>Сейфовая крутилка с D положениями не сильнее, чем мой замок с D^2 кнопками
Если не трудно, опишите мне что он из себя представляет, как действует, а то я их только видел, но не использовал.
К>Насчет случайности — все же хотелось бы услышать нечто аргументированное.
На пальцах. Допустим искомое сочетание N1N2N3, а какое оно никто не знает. Тогда, если идти перебором с одного края возможных вариантов, мы найдем ответ за K шагов, если с другого — за ~K (все возможные варианты — K). Поменяем N1N2N3 на другое не известное => изменится K и ~K. И сколько бы мы не меняли N1N2N3, мы никогда не найдем зависимость между разными K и ~K. (*) Проводя же перебор случайным способом, по вероятности, мы быстрее попадем в искомое сочетание N1N2N3.
(*) Конечно, это только на словах. Но, всё таки, где-то есть более математическое обоснование, только я не помню где.
Привет, Real 3L0!
К>>Насчет случайности — все же хотелось бы услышать нечто аргументированное.
R3>На пальцах. Допустим искомое сочетание N1N2N3, а какое оно никто не знает. Тогда, если идти перебором с одного края возможных вариантов, мы найдем ответ за K шагов, если с другого — за ~K (все возможные варианты — K). Поменяем N1N2N3 на другое не известное => изменится K и ~K. И сколько бы мы не меняли N1N2N3, мы никогда не найдем зависимость между разными K и ~K. (*) Проводя же перебор случайным способом, по вероятности, мы быстрее попадем в искомое сочетание N1N2N3. R3> (*) Конечно, это только на словах. Но, всё таки, где-то есть более математическое обоснование, только я не помню где.
Из случайной последовательности надо убрать повтор уже рассмотренных комбинаций.
Здравствуйте, Apapa, Вы писали:
R3>>На пальцах. Допустим искомое сочетание N1N2N3, а какое оно никто не знает. Тогда, если идти перебором с одного края возможных вариантов, мы найдем ответ за K шагов, если с другого — за ~K (все возможные варианты — K). Поменяем N1N2N3 на другое не известное => изменится K и ~K. И сколько бы мы не меняли N1N2N3, мы никогда не найдем зависимость между разными K и ~K. (*) Проводя же перебор случайным способом, по вероятности, мы быстрее попадем в искомое сочетание N1N2N3. R3>> (*) Конечно, это только на словах. Но, всё таки, где-то есть более математическое обоснование, только я не помню где.
A>Из случайной последовательности надо убрать повтор уже рассмотренных комбинаций.
(Сильно извиняюсь)
Пусть m — количество кнопок, N — число значений цифр на кнопках и пусть N — простое, то существует поле GF(N).
Возьмём любой примитивный неприводимый многочлен F(m) степени m над полем GF(N).
Тогда множество всех многочленов по модулю F(m) будет полем GF(N^m), а коэффициенты в элементах этого поля будут давать все возможные комбинации m кнопок, причём, естественно, без повторений.
Для перебора всех значений поля, достаточно возвести в последовательные степени n = 0..N^m-1 любой примитивный его элемент, например многочлен X. Это легко реализуется программно.
...для замка с тремя цифрами: К>Порядок цифр в коде может быть существенным
— максимум 3 варианта
К>или несущественным (123 = 231).
— всего один вариант.
Теперь КАК:
— подходим к замку и смотрим какие кнопки более всего "потерты".
— пробуем их.
Я таким образом часто открываю "кодовые" замки на подьездах.
Код запоминать влом, а этот способ практически никогда не подводит.
____________________
God obviously didn't debug, hasn't done any maintenance, and no documentation can be found. Truly amateur work.
в ассортименте.
Перекуём баги на фичи!
Apapa.gif)
Евгений
