Comments | jayrandom: задачки про взлом замков

jayrandom

задачки про взлом замков

Mar 24, 2007 14:04

Читаю тут про последовательность де Брайна и с каждой строчкой всё отчётливее и отчётливее соображаю, что я это уже изобреталЗадача совершенно естественно вырастает из необходимости подобрать кодовый замок со сдвигом: нужно построить кратчайшую последовательность из символов алфавита размера k, чтобы перебрать в ней всевозможные подстроки длины n ( Read more... )

какой я умный, interaction, экспериментальная математика, удивительное рядом, многомерность

Comments 4

faceted_jacinth March 25 2007, 00:29:16 UTC

Я тоже изобретал =)
Когда в Дюк Нюкема играл, там было несколько мест, где есть три или четыре кнопки и дверь или мост, которые открываются на специфическую комбинацию нажатых/ненажатых. Ну и как-то довольно быстро я придумал последовательность нажатий 121 3 121 4 121 3 121, которая проходит все состояния для четырёх кнопок. Почти то же самое, по-моему.

А задачка с велосипедным замком не очень интересная. Если считать за базовую операцию "сдвинуть одно из колёсиков (на любое значение)", то тупой перебор даёт 9 + 99 + 999 дополнительных сдвигов (из 9999) (когда ты за один шаг алгоритма двигаешь больше одного колёсика), а за такую маленькую величину (десять процентов) как-то беспонта бороться. Хотя подумаю ещё, даже интересно как-то.

jayrandom March 26 2007, 08:40:51 UTC

Комбинация нажатых-ненажатых в Дюке - эта задача скорее похожа на велозамок с бинарными колёсами. И ответ это подтверждает.

То, что я имел в виду - это именно циклическая последовательность. Когда вводится новая цифра, она встаёт в конец числа и "выталкивает" первую из кода. Тут решение другое.

В велозамке за базовую операцию нужно считать "сдвинуть одно колесо по часовой стрелке". Тогда экономическая ценность задачи возрастает :)

faceted_jacinth March 26 2007, 14:00:51 UTC

Дада, сейчас перечитал и понял, что тупил тогда нипадецки. Конечно, это одинаковые задачи, ответ получается либо рекуррентно (объединяя списки), либо непосредственно: запускаем счётчик в той же системе счисления и двигаем колёсико, соответствующее максимальному изменившемуся разряду счётчика. Наверное, несложно доказать, что так мы переберём всё. Это, в общем, практически очевидно =) Кстати, я даже подозреваю, что оно работает и в системах счисления с переменной базой.

jayrandom March 27 2007, 08:39:51 UTC

"Дюкозамок" и велозамок - одинаковые задачи.

А "замок с регистром сдвига" - совсем другая задача. Там думать надо :)