Комментарии 36
Условие не очень корректно.
1. Для 100% открытия сейфа с любой на перед заданной комбинацией потребуется тупо брутфорс, например ввод последовательно всех чисел 01234567891011121314 и т.д. тут можно учесть что куча комбинаций уже встречалась ранее и их бы надо выкинуть. Но это уже оптимизация работаюего решения, а о ней чуть позже.
2. Про оптимизацию: Если открывающая последовательность не ограничена условием, т.е. нет N такого что для любого n выполняется n<N, то о минимальности открывающей последовательности и говорить не приходится, иначе говоря любая подобная последовательность будет бесконечна.
Т.е. приходится говорить либо о последовательности которая откроет данный сейф с любым кодом, что означает что она откроет любой такой сейф. Т.к. длина кода сейфа не ограничена длина отпирающей последовательности бесконечно. Либо нам надо открыть данный конкретный сейф с известным кодом, то сам код и будет наиболее короткой 100% отпирающей последовательностью.
В данной задаче гораздо интереснее ввести время на ввод одного символа(для ограничения скорости брутфорса) и искать ожидаемое время открытия сейфа со случайным кодом, но вопрос о распределении вероятностей этих кодов надо тоже определять заранее.
Немного сумбурно получилось, ну да ладно.
1. Для 100% открытия сейфа с любой на перед заданной комбинацией потребуется тупо брутфорс, например ввод последовательно всех чисел 01234567891011121314 и т.д. тут можно учесть что куча комбинаций уже встречалась ранее и их бы надо выкинуть. Но это уже оптимизация работаюего решения, а о ней чуть позже.
2. Про оптимизацию: Если открывающая последовательность не ограничена условием, т.е. нет N такого что для любого n выполняется n<N, то о минимальности открывающей последовательности и говорить не приходится, иначе говоря любая подобная последовательность будет бесконечна.
Т.е. приходится говорить либо о последовательности которая откроет данный сейф с любым кодом, что означает что она откроет любой такой сейф. Т.к. длина кода сейфа не ограничена длина отпирающей последовательности бесконечно. Либо нам надо открыть данный конкретный сейф с известным кодом, то сам код и будет наиболее короткой 100% отпирающей последовательностью.
В данной задаче гораздо интереснее ввести время на ввод одного символа(для ограничения скорости брутфорса) и искать ожидаемое время открытия сейфа со случайным кодом, но вопрос о распределении вероятностей этих кодов надо тоже определять заранее.
Немного сумбурно получилось, ну да ладно.
Условие корректное, просто Вы его видимо не поняли.
Надо составить такой алгоритм, который для любого n построит последовательность МИНИМАЛЬНОЙ длины, точно открывающую сейф.
Алгоритм получает на вход n (любое натуральное число: 1,2,3,4...), а алгоритм для этого конкретного n выводит нужную последовательность.
То есть для n=1 это будет что-то типа 1234567890
Для n=2 =?..
Надо составить такой алгоритм, который для любого n построит последовательность МИНИМАЛЬНОЙ длины, точно открывающую сейф.
Алгоритм получает на вход n (любое натуральное число: 1,2,3,4...), а алгоритм для этого конкретного n выводит нужную последовательность.
То есть для n=1 это будет что-то типа 1234567890
Для n=2 =?..
Всего есть 10n вариантов шифра, для 100% вероятности открытия сейфа, необходимо перебрать все.
Соответственно, минимальная длина вводимой последовательности: lmin = 10n + n — 1, все варианты и количество нажатий до первой проверки (например, для n = 3, lmin = 1002).
Надо найти алгоритм, который перебирает все комбинации за lmin нажатий,— он и будет оптимальным.
Соответственно, минимальная длина вводимой последовательности: lmin = 10n + n — 1, все варианты и количество нажатий до первой проверки (например, для n = 3, lmin = 1002).
Надо найти алгоритм, который перебирает все комбинации за lmin нажатий,— он и будет оптимальным.
n=4 — длина кода полного перебора 40000 символов. 0000 0001 0002 0003 0004… 9998 9999 (пробелов там нет, я добавил чтобы наглядно было)
Оптимизация — убрать из 0000 три символа 000 — получили 39997 символов. и т.д. можно убрать 3 символа из 1111, 2222, 3333… 9999.
О дальнейшей оптимизации думаю. )
Оптимизация — убрать из 0000 три символа 000 — получили 39997 символов. и т.д. можно убрать 3 символа из 1111, 2222, 3333… 9999.
О дальнейшей оптимизации думаю. )
Ага изобретал тут всякие способы оптимизации, изобрел один хороший но доказать оптимальность не смог, а потом придумал такое.
Итак оптимальное решение существует. Пусть длина открывающего кода равна n, тогда 10n вариантов его существует. Тогда если записать их все последовательно в одну строку получим строку длиной n*10n которое назовём N.
Любые оптимизации сократят длину этой строки.
Известна максимальная длина строки и известен набор кодов которые должны в неё войти, дальше просто перебор. Он завершится за конечное время.
Т.е. берем строку длиной N/2 и перебираем всевозможные значения такой строки, причем на каждом шаге проверяем, все ли из 10n кодов там присутствуют. Если перебрав нашли такую строку в которой есть все коды, то запоминаем и берем строку длиной N/4 и делаем тоже самое. Короче бинарный поиск по длине строки с проверкой полным перебором существует ли удовлетворяющее условию задачи содержимое строки.
Итак оптимальное решение существует. Пусть длина открывающего кода равна n, тогда 10n вариантов его существует. Тогда если записать их все последовательно в одну строку получим строку длиной n*10n которое назовём N.
Любые оптимизации сократят длину этой строки.
Известна максимальная длина строки и известен набор кодов которые должны в неё войти, дальше просто перебор. Он завершится за конечное время.
Т.е. берем строку длиной N/2 и перебираем всевозможные значения такой строки, причем на каждом шаге проверяем, все ли из 10n кодов там присутствуют. Если перебрав нашли такую строку в которой есть все коды, то запоминаем и берем строку длиной N/4 и делаем тоже самое. Короче бинарный поиск по длине строки с проверкой полным перебором существует ли удовлетворяющее условию задачи содержимое строки.
Это очевидный, но слишком уж долгий алгоритм, похоже даже больше факториального.
Долгий то долгий, но гарантирует нахождение результата. Как только сообразил его весь интерес к задачке пропал.
Простые но неосуществимые алгоритмы все придумать могут. Напишете решение так, чтобы для кода длиной 10 программа завершилась раньше нахождения нормального алгоритма (вариант: доказательства несуществования полиномиального решения)?
Хе-хе. Равенство_классов_P_и_NP
Чето я не понял алгоритма
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.
Может я не правильно понял Ваш алгоритм?
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.
Может я не правильно понял Ваш алгоритм?
Для n = 2:
l = lmin = 101
9 0010203040506070809 11213141516171819 223242526272829 3343536373839 44546474849 556575859 6676869 77879 889 9
l = lmin = 101
не вижу в строке таких вариантов как 0000 1111 2222 и т.п.
а ещё не вижу 0001 0002 и т.п.
а ещё не вижу 0001 0002 и т.п.
Интересно было бы увидеть для трех
по моим расчетам (ниже) минимальная длина строки может быть 102+22-2=102
так что почти попадание: )
так что почти попадание: )
ну в принципе так и для любой длины возможно. Я кстати тоже так начал решать эту задачу, но вот после первой строчки я не понял, куда можно потом припихнуть 9000, и на этом застопорился)
При длине кода n каждый символ в строке может участвовать n раз в подборе кода. Кроме первых и последних символов n-1. Так как всего вариантов кода 10n, то минимально возможная длина строки равняется 10n плюс недобор участий крайних символов, который будет равен n2-n. Это число я получил вычев из суммы количества участий в переборе первых и последних n-1 символов если бы они не были крайними: (2n2-n), количество их реальных участий в переборе (n2-n).
Итого получается, что минимальная длина цепочки равняется 10n+n2-n
Кто может — посчитайте на бумажке. Я сам давно таким не занимался, так что мог накосячить где-то.
Сам алгоритм этой цепочки я ещё не придумал.
Итого получается, что минимальная длина цепочки равняется 10n+n2-n
Кто может — посчитайте на бумажке. Я сам давно таким не занимался, так что мог накосячить где-то.
Сам алгоритм этой цепочки я ещё не придумал.
Итого получается, что минимальная длина цепочки равняется 10n+n2-n
— ошибся — забыл тэг поставить. Правильно читать: 10n+n2-n
Взяв любые n символов мы получим один из вариантов кода.
Теперь в лучшем случае добавлением ещё одного символа мы должны получить новый код.
Этих новых кодов должно быть 10n-1 (минус один, потому что первый мы уже получили добавив сразу n первых символов)
То есть было n символов + 10n-1 = 10n+n-1
Теперь в лучшем случае добавлением ещё одного символа мы должны получить новый код.
Этих новых кодов должно быть 10n-1 (минус один, потому что первый мы уже получили добавив сразу n первых символов)
То есть было n символов + 10n-1 = 10n+n-1
Для любого n (n < 9) строиться лесенка (см. выше):
1. Первая строчка (n — 1) девяток.
2. Каждая строчка m (0...9), начинаеться с m. Далее идут числа вида m [m — 9] [(m + 1) — 9]… (длиной m)
Получилось, немного непонятно. Например для n = 3:
l = lmin = 1002
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
а 909 нету, или мне кажется?
Во втором ряду: 088 089 091 092
Да, поже на правильное решение, спасибо.
А если цифры не должны повторяться? ;)
Точно также, только подходит для 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:
l = lmin = 722
Строчки выглядят:
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
Задачи надо надкатом писать, чтобы подкатом не напоросься на коммент.
Это, знаете, странно выглядит, если человек закрывает глаза, отворачивается, и долго крутит колесо мыши.
Это, знаете, странно выглядит, если человек закрывает глаза, отворачивается, и долго крутит колесо мыши.
Не так давно была на олимпиаде по программированию подобная задача.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Открыть сейф