задачки про взлом замков
Mar. 24th, 2007 02:04 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
jayrandomЧитаю тут про последовательность де Брайна и с каждой строчкой всё отчётливее и отчётливее соображаю, что я это уже изобретал :)
Задача совершенно естественно вырастает из необходимости подобрать кодовый замок со сдвигом: нужно построить кратчайшую последовательность из символов алфавита размера k, чтобы перебрать в ней всевозможные подстроки длины n.
Меня интересовал двоичный вариант, и как-то уж так получалось, что последовательность была длины 2^n (если последовательность циклическая, и с хвостиком - если нет). Просто получалось, и всё - поэтому я как-то про себя решил, что это очевидно. А если алфавит не двоичный? "Задумайся, читатель, и тебе станет не по себе" (c).
Кстати, а вот "родственная" задача: дан велосипедный (мне тут подсказывают: "чемоданный" - objection, чемоданный открывают фомкой) замок с 4 крутящимися колёсиками, на которых цифры 0-9. Автосдвига у него, понятное дело, нет. Как его быстрее всего перебрать?
Задача совершенно естественно вырастает из необходимости подобрать кодовый замок со сдвигом: нужно построить кратчайшую последовательность из символов алфавита размера k, чтобы перебрать в ней всевозможные подстроки длины n.
Меня интересовал двоичный вариант, и как-то уж так получалось, что последовательность была длины 2^n (если последовательность циклическая, и с хвостиком - если нет). Просто получалось, и всё - поэтому я как-то про себя решил, что это очевидно. А если алфавит не двоичный? "Задумайся, читатель, и тебе станет не по себе" (c).
Кстати, а вот "родственная" задача: дан велосипедный (мне тут подсказывают: "чемоданный" - objection, чемоданный открывают фомкой) замок с 4 крутящимися колёсиками, на которых цифры 0-9. Автосдвига у него, понятное дело, нет. Как его быстрее всего перебрать?
