Игра что за слово? Ответы и решенияАлгоритмы, дающие ответы, что за слово загаданоВ этой статье я расскажу об игре "Угадай слово". В словесно-логических играх, в отличие от чисто логических игр, кроме умения рассуждать требуется хорошее знание языка и способность находить нужные слова в их большом разнообразии. "Выбирайте слова!" - говорят гражданину, который начинает говорить не те слова. Вот и мы тоже будем выбирать порой единственные и такие необходимые слова. Сопутствующие наши словесные игры и сервисы:
Прежде всего надо договориться, какие слова можно выбирать. Правило почти как в кроссворде: годятся нарицательные существительные в именительном падеже единственного (или множественного, если нет единственого) числа, не содержащие дефис, не являющиеся уменьшительными или наоборот, а также аббревиатурой (сокращением), которая пишется заглавными буквами. Уменьшительные слова, имеющие самостоятельное значение (например, лампочка, глазок) тоже подходят. Желательно, конечно, чтобы они были общеупотребительными или входили в заранее оговоренный словарь. "Угадай слово" относится к категории тестовых игр и напоминает "Быков и коров". Но в отличие от последней, которая является чисто логической игрой, "Угадай слово" - это скорее словесная, чем логическая игра. Итак, переходим к тому, как быстрее найти ответ, что за слово загадано соперником. Перед началом игры каждый из партнеров загадывает пятибуквенное слово, в котором все буквы различны. (Вначале можно потренироваться на четырёхбуквенных словах или даже поиграть в "Угадай букву"). Каждый игрок стремится угадать, что за слово задумано соперником. Для этого игроки поочередно называют друг другу слова произвольной длины, соответствующие правилам, установленным нами выше. В ответ на тестовое слово игрок сообщает, сколько букв из названного слова имеется в его задуманном. Если слово угадано, то игра заканчивается. Например, задумано слово ЖИЗНЬ, тестовое слово ПОДОКОННИК. Ответ - 3, буквы И, Н, Н содержатся в слове ЖИЗНЬ. В нем только одна буква Н, но при подсчете угаданные буквы из задуманного слова не вычеркиваются. По справедливости надо, конечно, считать, что вопросы игроки задают друг другу одновременно, и если оба игрока одновременно угадали слово, то надо зафиксировать ничью. Т.е. победитель игры определяется по числу заданных вопросов до того, как слово найдено. Кто назвал слово соперника с меньшего числа вопросов, тот выиграл, при равенстве вопросов ничья. Чтобы не усложнять игру, будем в нашем случае задумывать только слова, не имеющие анаграмм, т.е. слов, состоящих из тех же букв (клоун-колун-кулон-уклон). Какие же тестовые слова следует выбирать, чтобы получить ответ, что за слово загадано, с минимума вопросов? Существует алгоритм, которому требуется не более пяти вопросов для того, чтобы назвать задуманное слово. Идея этого алгоритма такова: первое тестовое слово фиксированное (например, ВЫСОКОПРЕВОСХОДИТЕЛЬСТВО), а остальные слова зависят от ответа. Каждое тестовое слово разбивает множество слов, которые могли быть загаданы, на несколько подмножеств. В каждом подмножестве собираются все слова, которые дают один и тот же ответ на тестовое слово. Следующее тестовое слово выбирается так, чтобы максимальное подмножество содержало как можно меньше слов. Хотя этот алгоритм и сильный, но, чтобы им воспользоваться в игре, нужно запомнить очень много вариантов проверочных слов. В поисках более простого алгоритма упростим игру. Пусть разрешается называть любые слова, а не только те, которые есть в словаре. Сколько тогда потребуется вопросов, чтобы ответить, что за слово загадано? Оказывается, достаточно одного: АББВВВВГГГГГГГГ... И в конце 2 в 32-й степени букв Я. Каждая следующая буква встречается в два раза чаще, чем предыдущая. Ответ надо представить суммой степеней двойки, и всё будет ясно. Аналогично можно было бы воспользоваться и десятичной системой. Идея алгоритмов этого типа состоит в проверке наличия некоторых фиксированных букв в задуманном слове. Подбирая вначале слова, которые состоят из трёх букв с частотами 2 и 1 и далее пользуясь уже протестированными буквами, получим, например, такую цепочку тестовых слов: МИМ, ДЕД, АСС (монета), БОБ, ПУП, ЛИЛИЯ, ТОРТ, ГОНГ, КИВОК, ЖЖЁНКА, ЗАЗИМЬЕ, ЧЕЧЕВИЦА, ФУФАЙКА, РОЗЫГРЫШ. После этих слов останется пять непроверенных букв: Х, Щ, Ъ, Э, Ю. На каждую из них придется потратить по одному слову, например, ХНА, ЩУР, ВЪЕЗД, ЭРА, ЮЛА. В худшем случае получается 18 шагов, после которых можно назвать задуманное слово. Назовём этот алгоритм методом 2-1. Для него среднее число вопросов до того, как слово будет названо, равно 10,8. (Я проводил проверку на словаре из 940 слов.) Разброс составляет от 4-х (ОБИДА) до 14-ти (АВЕНЮ) вопросов. Например, задумано слово ОБИДА. 1. МИМ - ответ 1 (буква И). 2. ДЕД - 1 (Д). 3. АСС - 1 (А). 4. БОБ - 3 (Б, О). А нет ли таких семибуквенных слов, состоящих из трех различных букв с частотами 4-2-1? Таких слов я не нашёл. Попробуем поискать слова с частотами 3-2-1. Это АНАНАС, ОКОРОК (РОКОКО), ГАГАРА. Дальше пошло несъедобное: БАОБАБ, ПАПАХА. И все? Вот ЗАРАЗА!.. Кстати! С помощью слова типа 3-2-1 можно проверить наличие в задуманном слове сразу трёх букв и сразу приблизиться к ответу, что за слово загадано. Например, АНАНАС. Возможны семь ответов. Для краткости будем ставить плюс перед угаданными буквами и минус перед теми буквами, которых в задуманном слове нет. Ответы: 0. -АНС 1. +С-АН 2. +Н-АС 3. +А-НС или +НС-А 4. +АС-Н 5. +АН-С 6. +АНС. Как видим, ответ 3 толкуется неоднозначно, т.к. сумму 3 можно набрать двумя путями. В этом случае придётся задать дополнительный вопрос, чтобы узнать, какой вариант имеет место. При этом надо постараться заодно проверить наличие ещё одной буквы. Алгоритм надо начинать с проверки букв, имеющих наибольшие частоты, это сократит среднее число вопросов. Привожу частоты букв в 5-буквенных словах, которые разрешается задумывать.
А 0,1042 П 0,0337 Ч 0,0130
О 0,0810 М 0,0310 Ж 0,0117
Р 0,0646 Б 0,0301 Ф 0,0112
К 0,0605 В 0,0279 Х 0,0103
Е 0,0598 Д 0,0279 Ё 0,0085
Т 0,0538 Ь 0,0263 Ц 0,0083
Л 0,0520 З 0,0223 Й 0,0065
И 0,0479 Я 0,0200 Ю 0,0047
Н 0,0466 Г 0,0191 Щ 0,0022
С 0,0450 Ш 0,0151 Э 0,0016
У 0,0387 Ы 0,0133 Ъ 0,0009
Как видим, буква А в этих словах каждая десятая. Теперь понятно, почему на "Поле чудес" отгадывание начинают с буквы А! Другой алгоритм получения ответа в игре что за словоДалее рассмотрим алгоритм типа 3-2-1, который на определение задуманного слова тратит в среднем 9,5 вопросов прежде, чем получит ответ, что за слово загадано. Вы можете придумать аналогичные алгоритмы, опираясь на приведённые выше слова. После некоторых ответов будут переходы к различным пунктам, в остальных случаях надо перейти к следующему пункту. Будут и условные пункты, которые выполняются только, если искомая буква еще не отмечена (т.е. не числится ни среди найденных, ни среди отброшенных). Не забудьте, что в последующих пунктах используется информация об отмеченных буквах, полученная ранее. При применении алгоритма надо выписать все 33 буквы алфавита и после каждого пункта обводить кружочком угаданные буквы и вычеркивать те буквы, которых в задуманном слове нет. Важное замечание: в описании алгоритма в ответах уже найденные буквы не считаются. Например, задумано слово АБРИС. После слова ОКОРОК получим ответ 1 (угадана буква Р). После слова ТЕТЕРЕВ надо смотреть ответ 0, т.к. буква Р уже угадана. Вот пример алгоритма типа 3-2-1:
Пункт Тестовое слово Ответ Выводы
1. ОКОРОК 0 -КОР
1 +Р-КО
2 +К-ОР
3 +О-КР или +КР-О. Переход к п. 1а.
4 +ОР-К
5 +КО-Р
6 +КОР
Переход к п. 2.
1а. ПОП 0 +КР-ОП
1 +О-КПР
2 +КПР-О
3 +ПО-КР
2. ТЕТЕРЕВ 0 -ВЕТ
1 +В-ЕТ
2 +Т-ВЕ
3 +Е-ВТ или +ВТ-Е. Переход к п. 2а.
4 +ВЕ-Т
5 +ЕТ-В
6 +ВЕТ
Переход к п. 3.
2а. ДЕД 0 +ВТ-ДЕ
1 +Е-ВДТ
2 +ВДТ-Е
3 +ДЕ-ВТ
3. АНАНАС 0 -АНС
1 +С-АН
2 +Н-АС
3 +А-НС или +НС-А. Переход к п. 3а.
4 +АС-Н
5 +АН-С
6 +АНС
Переход к п. 4.
3а. СНОП 0 +А-НСП
1 +АП-НС
2 +НС-АП
3 +НСП-А
4. МИНИМУМ 0 -ИМУ
1 +У-ИМ
2 +И-МУ
3 +М-ИУ или +ИУ-М. Переход к п. 4а.
4 +МУ-И
5 +ИМ-У
6 +ИМУ
Переход к п. 5.
4а. КУЛИК 0 +М-ИЛУ
1 +ЛМ-ИУ
2 +ИУ-ЛМ
3 +ИЛУ-М
5. Если отмечена хотя бы одна из букв Л, П, то переход к п. 6.
ЛИЛИПУТ 0 -ЛП
1 +П-Л
2 +Л-П
3 +ЛП
6. Если отмечена Д, то переход к п. 7.
ЖАЖДА 0 -ДЖ
1 +Д-Ж
2 +Ж-Д
3 +ДЖ
7. БАБУСЯ 0 -БЯ
1 +Я-Б
2 +Б-Я
3 +БЯ
8. Если отмечена Л, то переход к п. 9.
АЛЛЮР 0 -ЛЮ
1 +Ю-Л
2 +Л-Ю
3 +ЛЮ
9. ГАГАУЗ 0 -ГЗ
1 +З-Г
2 +Г-З
3 +ГЗ
10. Если отмечена П, то переход к п. 11.
ПОПЫТКА 0 -ПЫ
1 +Ы-П
2 +П-Ы
3 +ПЫ
11. ЧАШЕЧКА 0 -ЧШ
1 +Ш-Ч
2 +Ч-Ш
3 +ЧШ
12. ХАХАЛЬ 0 -ХЬ
1 +Ь-Х
2 +Х-Ь
3 +ХЬ
13. ФУФАЙКА 0 -ЙФ
1 +Й-Ф
2 +Ф-Й
3 +ЙФ
14. Если отмечена Ж, то переход к п. 15.
ЖУЖЕЛИЦА 0 -ЖЦ
1 +Ц-Ж
2 +Ж-Ц
3 +ЖЦ
15. Если отмечена Ц, то переход к п. 16.
ЭРЦГЕРЦОГ 0 -ЦЭ
1 +Э-Ц
2 +Ц-Э
3 +ЦЭ
16. Если отмечена Ы, то переход к п. 17.
СЫР 0 -Ы
1 +Ы
17. ЛЁН 0 -Ё
1 +Ё
18. ЩИТ 0 -Щ
1 +Щ
19. Если отмечена Ю, то переход к п. 21.
20. ЮЛА 0 -Ю
1 +Ю
21. ВЪЕЗД 0 -Ъ
1 +Ъ
Осталась непроверенной, возможно, только буква Э. Тому, кто следил за изложением этого алгоритма, можно сделать паузу. Скушайте "Твикс". Некоторые пункты алгоритма можно менять местами, но в любом случае для однозначности результатов в тестовом слове все буквы, кроме тестируемых, должны быть уже отмечены. Разброс числа вопросов составляет от 3-х (АРЕСТ) до 18-ти (ОБЪЁМ). Усовершенствование алгоритма в игре что за слово для быстрейшего получения ответаНередко может случаться, что первыми тремя-четырьмя вопросами вы угадаете четыре буквы в слове, что загадано. Чтобы сократить число вопросов, можно попытаться найти все слова, которые содержат все угаданные буквы, и далее вести отбор среди этих слов. Теперь усовершенствуем наш алгоритм: предположим, что, отыскав четыре буквы, мы находим все слова, их содержащие, и если их не более шести, то мы задает эти слова в качестве тестовых. Если таких слов больше шести, то будем действовать по ранее описанной схеме. Тогда среднее число вопросов для определения ответа, что за слово загадано, сократится до 6,9. Разброс от 2-х (ВАТЕР) до 15-ти (ОБЪЁМ). В этом случае для нахождения слова достаточно первых семнадцати пунктов алгоритма. Для вышеприведенного алгоритма типа 2-1 в этом случае среднее число вопросов равно 8,7. Разброс от 2-х (МЕДИК) до 15-ти (ШЕЙКА). Еще лучше, угадав четыре буквы и найдя все слова с ними, выписать оставшиеся буквы и пытаться найти такое слово, чтобы проверить наличие сразу двух из них. Например:
ОКОРОК - 2 +К-ОР
ТЕТЕРЕВ - 3 +Е-ВТ или +ВТ-Е
ДЕД - 1 +Е-ВДТ
АНАНАС - 5 +АН-С
Угаданы буквы А, Е, К, Н. С этими буквами есть только три слова: БАКЕН, КАШНЕ и ПЕНКА. Пятые буквы в них - это Б, Ш, П. Если теперь начать задавать эти три слова в качестве тестовых, то до конца игры понадобится один или два вопроса. Но стоит крикнуть: "ШАБАШ!", - и с этим словом игра заканчивается. Возможные ответы: 1. 2, +А-БШ. Задумано слово ПЕНКА. 2. 3, +АБ-Ш. Задумано слово БАКЕН. 3. 4, +АШ-Б. Задумано слово КАШНЕ. Среднее число вопросов, чтобы узнать ответ, что за слово загадано, по этому методу будет еще меньше. Читатели могут возразить, что найти все слова по четырем буквам не так-то просто. Это верно, но в этом и состоит искусство отгадывать слова. Для облегчения поиска слов по четырем буквам привожу наиболее часто встречающиеся слоги из слов-кандидатов на загадывание в порядке убывания частот: КА, РА, НА, ОК, АН, ЛЬ, СТ, ЕР, ОН, ОР, ПО, ЛО, АЛ, АР, ЕТ, ЗА, ЛИ, РО, ТА. Теперь перед нами, вооружёнными до зубов нужными словами, не устоит даже доктор филологических наук, если, конечно, он не знаком с алгоритмами, и поднимет свои докторские ручки кверху. А если что, мы за словом в карман не полезем! Алгоритмы получения ответа в игре что за слово © IQFun.ru, 1996 г. |