Открыть сейф

    Привет.

    Хочу рассказать вам об одной задаче, которая занимает меня уже очень продолжительное время. Сразу хочу сказать, что я не знаю ее решения (чтобы не превращать топик в очередной топик зла). Также я не встречал задач, подобной этой, в интернете, хотя вполне допускаю, что первый же коммент будет со ссылкой на решение.

    Итак, задача.

    Предположим, у нас есть сейф с цифровым замком. Чтобы открыть сейф, необходимо набрать на цифровой клавиатуре код, состоящий из n цифр (цифры могут повторяться). Сейф откроется, как только код будет набран — предыдущие неправильные цифры не учитываются. То есть, если код равен «1234», сейф откроется, даже если набрать «51234», «781234» или «11234». Задача заключается в том, чтобы найти такую последовательность цифр, которая со 100% вероятностью откроет сейф и которая будет минимальна по длине.
    Поделиться публикацией

    Комментарии 36

      0
      Условие не очень корректно.
      1. Для 100% открытия сейфа с любой на перед заданной комбинацией потребуется тупо брутфорс, например ввод последовательно всех чисел 01234567891011121314 и т.д. тут можно учесть что куча комбинаций уже встречалась ранее и их бы надо выкинуть. Но это уже оптимизация работаюего решения, а о ней чуть позже.
      2. Про оптимизацию: Если открывающая последовательность не ограничена условием, т.е. нет N такого что для любого n выполняется n<N, то о минимальности открывающей последовательности и говорить не приходится, иначе говоря любая подобная последовательность будет бесконечна.
      Т.е. приходится говорить либо о последовательности которая откроет данный сейф с любым кодом, что означает что она откроет любой такой сейф. Т.к. длина кода сейфа не ограничена длина отпирающей последовательности бесконечно. Либо нам надо открыть данный конкретный сейф с известным кодом, то сам код и будет наиболее короткой 100% отпирающей последовательностью.

      В данной задаче гораздо интереснее ввести время на ввод одного символа(для ограничения скорости брутфорса) и искать ожидаемое время открытия сейфа со случайным кодом, но вопрос о распределении вероятностей этих кодов надо тоже определять заранее.
      Немного сумбурно получилось, ну да ладно.
        +3
        Условие корректное, просто Вы его видимо не поняли.
        Надо составить такой алгоритм, который для любого n построит последовательность МИНИМАЛЬНОЙ длины, точно открывающую сейф.
        Алгоритм получает на вход n (любое натуральное число: 1,2,3,4...), а алгоритм для этого конкретного n выводит нужную последовательность.
        То есть для n=1 это будет что-то типа 1234567890
        Для n=2 =?..
          +3
          Ага, вот теперь понятнее. Сейчас изобрету.
        0
        Всего есть 10n вариантов шифра, для 100% вероятности открытия сейфа, необходимо перебрать все.
        Соответственно, минимальная длина вводимой последовательности: lmin = 10n + n — 1, все варианты и количество нажатий до первой проверки (например, для n = 3, lmin = 1002).
        Надо найти алгоритм, который перебирает все комбинации за lmin нажатий,— он и будет оптимальным.
          +2
          А Вы уверены, что всегда можно найти решение длины lmin?
          Меньше этой длины последовательность быть не может — это очевидно,
          но всегда ли она будет lmin? Возможно доказательство этого факта приблизит нас к решению.
          +2
          n=4 — длина кода полного перебора 40000 символов. 0000 0001 0002 0003 0004… 9998 9999 (пробелов там нет, я добавил чтобы наглядно было)
          Оптимизация — убрать из 0000 три символа 000 — получили 39997 символов. и т.д. можно убрать 3 символа из 1111, 2222, 3333… 9999.
          О дальнейшей оптимизации думаю. )
            0
            минусовщики, вы бы хоть поправили меня!
              0
              Тут ты не учел, что последовательность кодов тоже важно. С тем же успехом я могу выбрать последовательность 9999 9998… 0001 0000, а ее опитмизация уже отличается от твоей. А доказательство, что твоя строка лучше моей, нет.
            –2
            Ага изобретал тут всякие способы оптимизации, изобрел один хороший но доказать оптимальность не смог, а потом придумал такое.
            Итак оптимальное решение существует. Пусть длина открывающего кода равна n, тогда 10n вариантов его существует. Тогда если записать их все последовательно в одну строку получим строку длиной n*10n которое назовём N.
            Любые оптимизации сократят длину этой строки.
            Известна максимальная длина строки и известен набор кодов которые должны в неё войти, дальше просто перебор. Он завершится за конечное время.
            Т.е. берем строку длиной N/2 и перебираем всевозможные значения такой строки, причем на каждом шаге проверяем, все ли из 10n кодов там присутствуют. Если перебрав нашли такую строку в которой есть все коды, то запоминаем и берем строку длиной N/4 и делаем тоже самое. Короче бинарный поиск по длине строки с проверкой полным перебором существует ли удовлетворяющее условию задачи содержимое строки.
              0
              Это очевидный, но слишком уж долгий алгоритм, похоже даже больше факториального.
                –1
                Долгий то долгий, но гарантирует нахождение результата. Как только сообразил его весь интерес к задачке пропал.
                  +1
                  Простые но неосуществимые алгоритмы все придумать могут. Напишете решение так, чтобы для кода длиной 10 программа завершилась раньше нахождения нормального алгоритма (вариант: доказательства несуществования полиномиального решения)?
                  0
                  Чето я не понял алгоритма
                  n=2
                  берем последовательность 00 01 02 03 04 05 06 07… 96 97 98 99
                  Для того чтобы получить комбинацию 00 нам необходимо взять 1и2 или 2и3 символы (во всей остальной цепочке 00 больше нет)
                  Для того чтобы получить комбинацию 99 нам необходимо взять 2 последних символа или те, которые дают числа ...89 90…

                  В итоге получаем, что длина цепочки-ответа быть меньше 180 не может быть в принципе, иначе либо комбинации 00, либо 99 в ней не будет.
                  Но избыточность этой цепочки видна сразу, так как например 4и5 символы образуют 10 и 19и20 символы образуют тоже 10.

                  Может я не правильно понял Ваш алгоритм?
              +6
              Для n = 2:

              9
              0010203040506070809
              11213141516171819
              223242526272829
              3343536373839
              44546474849
              556575859
              6676869
              77879
              889
              9

              l = lmin = 101
                –2
                не вижу в строке таких вариантов как 0000 1111 2222 и т.п.
                а ещё не вижу 0001 0002 и т.п.
                  +2
                  Длинна 2, а не 4
                    0
                    ой. прошу прощения.
                  0
                  Интересно было бы увидеть для трех
                    0
                    по моим расчетам (ниже) минимальная длина строки может быть 102+22-2=102
                    так что почти попадание: )
                      0
                      ну в принципе так и для любой длины возможно. Я кстати тоже так начал решать эту задачу, но вот после первой строчки я не понял, куда можно потом припихнуть 9000, и на этом застопорился)
                      0
                      При длине кода n каждый символ в строке может участвовать n раз в подборе кода. Кроме первых и последних символов n-1. Так как всего вариантов кода 10n, то минимально возможная длина строки равняется 10n плюс недобор участий крайних символов, который будет равен n2-n. Это число я получил вычев из суммы количества участий в переборе первых и последних n-1 символов если бы они не были крайними: (2n2-n), количество их реальных участий в переборе (n2-n).
                      Итого получается, что минимальная длина цепочки равняется 10n+n2-n

                      Кто может — посчитайте на бумажке. Я сам давно таким не занимался, так что мог накосячить где-то.

                      Сам алгоритм этой цепочки я ещё не придумал.
                        0
                        Итого получается, что минимальная длина цепочки равняется 10n+n2-n

                        — ошибся — забыл тэг поставить. Правильно читать: 10n+n2-n
                          0
                          Опять-таки — это нижняя граница, но не решение, потому как доказательства нет.
                          +1
                          Взяв любые n символов мы получим один из вариантов кода.
                          Теперь в лучшем случае добавлением ещё одного символа мы должны получить новый код.
                          Этих новых кодов должно быть 10n-1 (минус один, потому что первый мы уже получили добавив сразу n первых символов)
                          То есть было n символов + 10n-1 = 10n+n-1
                            0
                            Спасибо, наконец-то понял как получилась нижняя оценка.
                          +3
                          Для любого n (n < 9) строиться лесенка (см. выше):

                          1. Первая строчка (n — 1) девяток.
                          2. Каждая строчка m (0...9), начинаеться с m. Далее идут числа вида m [m — 9] [(m + 1) — 9]… (длиной m)

                          Получилось, немного непонятно. Например для n = 3:

                          99				2
                          0 001 002 ... 009 011 ... 099	10 * (10 - 1) * 3 + 1
                          1 112 113 ... 119 122 ... 199	9 * (9 - 1) * 3 + 1
                          ..
                          7 778 779 788 789 798 799	9 * (9 - 1) * 3 + 1
                          8 889 899			2 * (2 - 1) * 3 + 1
                          9				1 * (1 - 1) * 3 + 1
                          


                          l = lmin = 1002

                            0
                            а 909 нету, или мне кажется?
                              0
                              Во втором ряду: 088 089 091 092
                                0
                                Да, поже на правильное решение, спасибо.
                                  0
                                  Только для n < 9!
                                  0
                                  А если цифры не должны повторяться? ;)
                                    0
                                    Точно также, только подходит для n < 8: lmin = 10! / (10 — n)! + n — 1.

                                    Строчки выглядят:
                                    1. Первая строчка 9, 8, 7… длины n
                                    2. В каждой строчке m, идут числа длиной n, вида
                                    a = m
                                    ai є [(m + i — 1); 9], ai<>ai-1, …, ai<>a

                                    Например для n = 3:

                                    98					2
                                    012 013 ... 019 021 023 ... 098		9 * (9 - 1) * 3
                                    123 124 ... 129 132 134 ... 198		8 * (8 - 1) * 3
                                    ...									
                                    789 798					2 * (2 - 1) * 3
                                    

                                    l = lmin = 722
                              –1
                              Задачи надо надкатом писать, чтобы подкатом не напоросься на коммент.
                              Это, знаете, странно выглядит, если человек закрывает глаза, отворачивается, и долго крутит колесо мыши.
                                0
                                Не так давно была на олимпиаде по программированию подобная задача.

                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                Самое читаемое