Ага изобретал тут всякие способы оптимизации, изобрел один хороший но доказать оптимальность не смог, а потом придумал такое.
Итак оптимальное решение существует. Пусть длина открывающего кода равна n, тогда 10n вариантов его существует. Тогда если записать их все последовательно в одну строку получим строку длиной n*10n которое назовём N.
Любые оптимизации сократят длину этой строки.
Известна максимальная длина строки и известен набор кодов которые должны в неё войти, дальше просто перебор. Он завершится за конечное время.
Т.е. берем строку длиной N/2 и перебираем всевозможные значения такой строки, причем на каждом шаге проверяем, все ли из 10n кодов там присутствуют. Если перебрав нашли такую строку в которой есть все коды, то запоминаем и берем строку длиной N/4 и делаем тоже самое. Короче бинарный поиск по длине строки с проверкой полным перебором существует ли удовлетворяющее условию задачи содержимое строки.
Условие не очень корректно.
1. Для 100% открытия сейфа с любой на перед заданной комбинацией потребуется тупо брутфорс, например ввод последовательно всех чисел 01234567891011121314 и т.д. тут можно учесть что куча комбинаций уже встречалась ранее и их бы надо выкинуть. Но это уже оптимизация работаюего решения, а о ней чуть позже.
2. Про оптимизацию: Если открывающая последовательность не ограничена условием, т.е. нет N такого что для любого n выполняется n<N, то о минимальности открывающей последовательности и говорить не приходится, иначе говоря любая подобная последовательность будет бесконечна.
Т.е. приходится говорить либо о последовательности которая откроет данный сейф с любым кодом, что означает что она откроет любой такой сейф. Т.к. длина кода сейфа не ограничена длина отпирающей последовательности бесконечно. Либо нам надо открыть данный конкретный сейф с известным кодом, то сам код и будет наиболее короткой 100% отпирающей последовательностью.
В данной задаче гораздо интереснее ввести время на ввод одного символа(для ограничения скорости брутфорса) и искать ожидаемое время открытия сейфа со случайным кодом, но вопрос о распределении вероятностей этих кодов надо тоже определять заранее.
Немного сумбурно получилось, ну да ладно.
Хорошие мысли, но есть одна странность — вирусные записи прорвутся. Много ссылок легальных, много комментов, много просмотров, полезности как правило ноль. С учетом постоянно сменяющих лидерство дико популярных вирусных роликов и прочих бяк о наличии в топе рейтинга хороших информативных записей можно забыть. Еще бы полезность контента как-то отследить.
Еще мыль интересная, Wi-fi точки без регистрации можно до 125 милливатт бытовые использовать. Так же введут и лицензии на колонки больше 2х ватт мощностью, чтоб не дай бог небыло слышно с улицы или соседям?
Блин, жесть конечно. А скоро интерено додумаются за татуировки сажать и кожу снимать? Такие явления действительно ужасны, но чем ужаснее они будут тем быстрее общество взбунтуется против этого и уничтожит эту паразитирующую на обществе систему.
Машинка хороша конечно, но цена ИМХО высоковата, можно 13" Мак бук про взять за чуть побольше, у него и аккумулятор держит дольше и корпус больше доверия внушает. А маконенавистники могут использовать тот же Windows.
Мозилла пропагандирует опен сорс. Вот программиста пишут код для мозиллы, а код открытый, кто хочет тот и берет. Вот для той же идеологии и этот формат сделан.
Зато теперь появятся возможности сделать еще более ужасные новогодние елки с использованием убогих шрифтов с диска 100000 шрифтов на одном диске. Web будет красивее только от благоразумности авторов.
Для этого есть криптованные, подписанные форматы шрифтов, которые не будут работать на доменах отличных от содержащихся в подписи, хотя стырить при желании можно. WOFF задумывали как открытый в противопоставление проприетарщине
Итак оптимальное решение существует. Пусть длина открывающего кода равна n, тогда 10n вариантов его существует. Тогда если записать их все последовательно в одну строку получим строку длиной n*10n которое назовём N.
Любые оптимизации сократят длину этой строки.
Известна максимальная длина строки и известен набор кодов которые должны в неё войти, дальше просто перебор. Он завершится за конечное время.
Т.е. берем строку длиной N/2 и перебираем всевозможные значения такой строки, причем на каждом шаге проверяем, все ли из 10n кодов там присутствуют. Если перебрав нашли такую строку в которой есть все коды, то запоминаем и берем строку длиной N/4 и делаем тоже самое. Короче бинарный поиск по длине строки с проверкой полным перебором существует ли удовлетворяющее условию задачи содержимое строки.
1. Для 100% открытия сейфа с любой на перед заданной комбинацией потребуется тупо брутфорс, например ввод последовательно всех чисел 01234567891011121314 и т.д. тут можно учесть что куча комбинаций уже встречалась ранее и их бы надо выкинуть. Но это уже оптимизация работаюего решения, а о ней чуть позже.
2. Про оптимизацию: Если открывающая последовательность не ограничена условием, т.е. нет N такого что для любого n выполняется n<N, то о минимальности открывающей последовательности и говорить не приходится, иначе говоря любая подобная последовательность будет бесконечна.
Т.е. приходится говорить либо о последовательности которая откроет данный сейф с любым кодом, что означает что она откроет любой такой сейф. Т.к. длина кода сейфа не ограничена длина отпирающей последовательности бесконечно. Либо нам надо открыть данный конкретный сейф с известным кодом, то сам код и будет наиболее короткой 100% отпирающей последовательностью.
В данной задаче гораздо интереснее ввести время на ввод одного символа(для ограничения скорости брутфорса) и искать ожидаемое время открытия сейфа со случайным кодом, но вопрос о распределении вероятностей этих кодов надо тоже определять заранее.
Немного сумбурно получилось, ну да ладно.