Руины Бенареса стучат в их сердца
Nov. 16th, 2011 09:52 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
spamsinkЕсть такая задача: дано несколько строк одинаковой длины из алфавита "01X". Требуется ответить на вопрос, покрывают ли они в совокупности все возможные двоичные строки той же длины, если Х может соответствовать и нулю, и единице. Вот что делают злосчастные потомки жрецов бенаресского храма:
0. Если строки нулевой длины, вернем ИСТИНА.
1. Найдем позицию, в которой во всех строках реже всего встречается Х.
2. Если в этой позиции встречаются только нули или только единицы, вернем ЛОЖЬ.
3. Поделим все строки на два подмножества: в одном будут строки, в которых в этой позиции 0 или Х, в другом 1 или Х; и вырежем эту позицию из строк - тем самым все строки стали на один символ короче.
4. Если эта же процедура, запущенная на меньшем из подмножеств, вернула ЛОЖЬ, вернем ЛОЖЬ.
5. Запустим эту же процедуру на другом подмножестве и вернем ее результат.
Задание 1. Что нужно добавить к этому алгоритму, чтобы избавить его от бенаресского проклятия?
Задание 2. Какой наглостью нужно обладать, чтобы после сообщения о неприемлемой скорости работы алгоритма заявить "It's a very involved issue"?
Ответ на задание 1:
0. Если строки нулевой длины или нашлась строка, состоящая из одних Х, вернем ИСТИНА.
Это добавление ликвидирует экспоненциальную сложность анализа таких строк.
Ответ на задание 2 оставляется в качестве упражнения.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2011-11-17 08:33 am (UTC)Полез в википедию за словом Бенарес.
Пошел по алгоритму, споткнулся на пункте два, пошел к началу перечитывать условие.
Минуту свопился на слове "покрывают".
Минуту свопился на слове "несколько".
Ушел делать кофе.
no subject
Date: 2011-11-17 04:10 pm (UTC)"Реже всего" может означать и "ни разу", см. пример в комменте ниже.
"Покрывают" в смысле "можно установить сюръекцию". Надо было сразу сказать "сюръекция"?
"Несколько" в смысле "более одной".
В общем, правильно, что я не пошел в педагоги - утомил бы вконец и себя, и учеников мгновенно.
no subject
Date: 2011-11-17 04:19 pm (UTC)Сюръекцию не надо, лучше "в совокупности" куда-нибудь сдвинуть, но и то не обязательно.
no subject
Date: 2011-11-17 01:20 pm (UTC)no subject
Date: 2011-11-17 04:05 pm (UTC)0XXX
10XX
110X
111X
Х реже всего (а именно 0 раз) встречается в первой позиции, поэтому поделим строки на два подмножества в зависимости от символа в ней и удалим первую позицию. Получим (ХХХ) и (0XX, 10X, 11X). И т.п.
что-то торможу
Date: 2011-11-21 09:21 am (UTC)- что нам разрешает неглядя ни на что больше вырезать позицию из всех строк?
- что нам разрешает неглядя ни на что больше разбить список строк на два?
Re: что-то торможу
Date: 2011-11-21 09:25 am (UTC)Разбить список строк на два и сделать два рекурсивных вызова нужно, чтобы проверить, что и при нуле, и при единице в данной позиции все остальные позиции удовлетворяют условию.
Re: что-то торможу
Date: 2011-11-21 09:40 am (UTC)Re: что-то торможу
Date: 2011-11-21 03:42 pm (UTC)no subject
Date: 2011-11-17 04:24 pm (UTC)0. Завести два битовых массива той же длины, изначально заполненных нулями. Первый массив будет считать покрытость нулями, второй - единичками.
1. Для каждой строки из множества, проходим поэлементно, и если там содержится 0, устанавливаем соответствующий бит в 1-м массиве, если 1 - во 2-м массиве, если Х - то в обоих двух.
2. Смотрим, все ли биты в полученных массивах стали содержать "1". Если да, то все покрыто. Иначе будут "0" в непокрытых позициях.
no subject
Date: 2011-11-17 04:36 pm (UTC)000000
111111
устанавливают все биты в обоих массивах, но 64 комбинации никак не покрывают.
no subject
Date: 2011-11-17 07:16 pm (UTC)