Логическая задача
Модераторы: Азарапетыч, Администрация
Логическая задача
Последний раз редактировалось deric 12 июл 2007, 20:18, всего редактировалось 1 раз.
-
Азарапетыч
- Модератор
- Сообщения: 10801
- Зарегистрирован: 14 мар 2006, 21:45
- Пол: Мужской
- Откуда: Москва
- Контактная информация:
-
Азарапетыч
- Модератор
- Сообщения: 10801
- Зарегистрирован: 14 мар 2006, 21:45
- Пол: Мужской
- Откуда: Москва
- Контактная информация:
Я всегда отгадывал, просто подставляя очередное число, подходящее под все предыдущие варианты. Начинал обычно с 1234Atson писал(а):Давайте превратим в задачку. Найти оптимальный алгоритм отгадывания в числовом варианте.
(или 1230 в варианте с запретом нуля в начале числа).IMHO подробный оптимальный алгоритм отгадывания довольно разветвлён и сильно зависит от ответов.
Интересен другой вопрос: сколько максимум ходов может понадобиться для отгадывания по оптимальному алгоритму? Я только что угадал за 8 ходов. Можно ли гарантированно потратить меньше?
-
Dendr
- Акула пера
- Сообщения: 5717
- Зарегистрирован: 06 май 2005, 15:11
- Пол: Мужской
- Откуда: Раменское, Мос.обл.
- Контактная информация:
Если повезет, то можно и быстрее. Но это уж как карта ляжет.
Вот "распечатка" угадывания за 5 ходов, только что.
1) 1234 - 1Б1К
2) 5678 - 0Б2К
Значит, две цифры из первой четверки, и две из второй. Причем в первой уже угадал цифру на своем месте.
Допустил, что это 1. Остальные - рандомом.
3) 1863 - 1Б0К
Вот это повезло... единственный бык.
Допустим, что это тройка. Значит, единицы в ответе нет. Либо 2, либо 4. Но - смотрим в первую комбинацию: тройка - "корова". Значит, "бык" - двойка. Следовательно, *2*3, причем на местах звездочек - 5 и 7. Во второй комбинации они - "коровы". Следовательно, ответ в этом допущении - 7253.
Допустим теперь, что шестерка, **6*. Тогда - из первой комбинации - в ответе 2 и 4. И либо это 426*, либо 2*64. На месте звездочек - либо 5, либо 7. Всего - 4 варианта. 4265, 4267, 2564, 2764.
Допустим, что восьмерка, *8**. Двойка, значит, в первой комбинации, может быть только "коровой". А четверка - "быком". Либо 28*4, либо *824. Учитывая вторую комбинацию - 5 или 7 - "коров", получим, 2854 или 7824.
Допустим, единица, 1***. Тройка - не "корова". Т.е. в первой комбинации - корова либо 2, либо 4. Т.е. 1*2*, 1**2, 14**, 1*4*. На месте звездочек - 5 или 7. Т.е. 1527, 1725, 1752, 1457, 1547, 1745.
Нетрудно сосчитать, что после трех запросов осталось 13 вариантов. Можно попробовать перебрать их, а можно поинтуичить... Всю эту логику я написал сейчас, при разгадывании я просто вводил следующее число по наитию. Но можно это "наитие" подвести под логику. Во всех вариантах есть хотя бы две цифры (а то и все 3) из "триплета" 2-5-7. Вот и воспользуемся этим. Четвертой цифрой хорошо бы взять единицу - тогда очень хорошее "обрезание" выйдет.
4) 1752 - 2Б2К
Надо же, угадал. Случайно.
Надо выбрать из вариантов 1527 и 1725. Надо поменять две цифры местами, а 1 и "какую-то" - не трогать.
Ну, тут только один вариант:
5) 1725 - 4Б0К.
Вот "распечатка" угадывания за 5 ходов, только что.
1) 1234 - 1Б1К
2) 5678 - 0Б2К
Значит, две цифры из первой четверки, и две из второй. Причем в первой уже угадал цифру на своем месте.
Допустил, что это 1. Остальные - рандомом.
3) 1863 - 1Б0К
Вот это повезло... единственный бык.
Допустим, что это тройка. Значит, единицы в ответе нет. Либо 2, либо 4. Но - смотрим в первую комбинацию: тройка - "корова". Значит, "бык" - двойка. Следовательно, *2*3, причем на местах звездочек - 5 и 7. Во второй комбинации они - "коровы". Следовательно, ответ в этом допущении - 7253.
Допустим теперь, что шестерка, **6*. Тогда - из первой комбинации - в ответе 2 и 4. И либо это 426*, либо 2*64. На месте звездочек - либо 5, либо 7. Всего - 4 варианта. 4265, 4267, 2564, 2764.
Допустим, что восьмерка, *8**. Двойка, значит, в первой комбинации, может быть только "коровой". А четверка - "быком". Либо 28*4, либо *824. Учитывая вторую комбинацию - 5 или 7 - "коров", получим, 2854 или 7824.
Допустим, единица, 1***. Тройка - не "корова". Т.е. в первой комбинации - корова либо 2, либо 4. Т.е. 1*2*, 1**2, 14**, 1*4*. На месте звездочек - 5 или 7. Т.е. 1527, 1725, 1752, 1457, 1547, 1745.
Нетрудно сосчитать, что после трех запросов осталось 13 вариантов. Можно попробовать перебрать их, а можно поинтуичить... Всю эту логику я написал сейчас, при разгадывании я просто вводил следующее число по наитию. Но можно это "наитие" подвести под логику. Во всех вариантах есть хотя бы две цифры (а то и все 3) из "триплета" 2-5-7. Вот и воспользуемся этим. Четвертой цифрой хорошо бы взять единицу - тогда очень хорошее "обрезание" выйдет.
4) 1752 - 2Б2К
Надо же, угадал. Случайно.
Надо выбрать из вариантов 1527 и 1725. Надо поменять две цифры местами, а 1 и "какую-то" - не трогать.
Ну, тут только один вариант:
5) 1725 - 4Б0К.
-
Dendr
- Акула пера
- Сообщения: 5717
- Зарегистрирован: 06 май 2005, 15:11
- Пол: Мужской
- Откуда: Раменское, Мос.обл.
- Контактная информация:
Можно ли единый алгоритм придумать? Наверное, можно, но он слишком зависит от ответов...
Вообще, каждый ход "обрезает" количество вариантов. Изначально их 10*9*8*7=5040 (не берем в расчет версию игры с первой ненулевой). После первого хода происходит "обрезание".
Начинать надо, очевидно, с 1234. Потому что никакой разницы нет. Ну, только если случайно угадаешь с первого хода - но это лотерея.
Исходов может быть несколько, возьму и выпишу их:
4б0к,
3б0к, 3б1к,
2б0к, 2б1к, 2б2к,
1б0к, 1б1к, 1б2к, 1б3к,
0б0к, 0б1к, 0б2к, 0б3к, 0б4к.
Всего - 15. В каждом нужно применять свою логику.
Например, 2б1к - 6 вариантов пар "быков", и в каждом случае 2 варианта одной "коровы", она встает на место "лишней" цифры, а на ее "коровье" место - встает одна из 6 оставшихся цифр (5..0).
6*2*6=72 варианта. Например, 1439, 2734 и т.д. А вот дальше...На второй ход можно задаться постулатом: предполагать "быками" наименьшие цифры, затем - "коровами" - наименьшие из оставшихся.
Т.е. в данном случае - (1234 - 2б1к): предположим вариант 12*3. Видимо, нужно ставить 1253 (опять - нет никакой разницы между другими вариантами). И опять - в общем случае, один из 15-ти вариантов исхода. Тогда нужно искать перекрывание тех (72) вариантов, и этих.
Ну, допустим, что тут вышло 1б2к.
Перебор вариантов - рассмотрим, какие возможны были пары "быков" в (1234):
12 - тогда в (1253) должно быть минимум 2 быка. Пр-речие.
13 - т.е. либо 2, либо 5 - "корова". (другая "корова" - 3). Во втором варианте - означает, что "корова" из (1234) - 4. Т.е.: 1*32, 1435. На месте звездочки - 6..0. Всего - 5 вариантов.
14 - тогда 5 - "корова" точно (из 2 и 3 - только 1 "корова"). Т.е. 15*4 (либо 2 либо 3 на месте звездочки), т.е. только 1524.
23 - Тогда в (1253): 2 - "бык", 3 - "корова". Еще одна корова - либо 1, либо 5. Во втором случае - 4 есть "корова" из (1234). Т.е. имеем 4235 или *231, на месте звездочки 6..0.
24 - тогда 5 - точно "корова". Т.е. 52*4, на месте звездочки либо 1, либо 3 (но надо помнить, что это "корова" из (1234)). Т.е. 5214.
34 - тогда в (1253) 1 и 2 - не "быки", 5 - аналогично, 3 - только "корова". Пр-речие.
Итог (в порядке возрастания): 1435, 1524, 1*32, 4235, 5214, *231 (на месте * - 6,7,8,9,0) Всего - 14 вариантов.
Аналогично можно провести такую же логику для остальных вариантов первого исхода, затем соответственно приведенного второго. Получается многоэтажное ветвление. 15 ветвей первого уровня, от каждой - не более чем 15 ветвей второго уровня, получаем около двухсот вариантов. В каждом - по (навскидку) паре десятков наборов.
Идем дальше - 14 вариантов (ну, 6, но в некоторых еще надо подставлять неизвестные доселе цифры)... это немало. Можно взять снова минимальное число, 1435.
Дальше - зависит от правильного ответа:
1435 - 4б0к
1524 - 1б2к
1*32 - 2б0к
4235 - 2б1к
5214 - 0б3к
*231 - 1б1к
Исходы - разные! Четвертым ходом мы просто называем нужное число... Кроме случаев №3 и №6. Ими и займемся.
Еще раз повторим наши ходы:
1) 1234 - 2б1к
2) 1253 - 1б2к
3) 1435 - 2б0к
Следовательно, ответ - вида 1*32, где на месте звездочки - одна из цифр 6, 7, 8, 9, 0. Для ее гарантированного выбора требуется 3 хода.
Поясню это: буду писать варианты ответов: для 6, 7, 8, 9, 0 соответственно:
4) 6782 - 2б1к, 3б1к, 2б1к, 2б0к, 2б0к
- имеем три варианта ответа. Во втором (3б1к) - пишем сразу ответ. В остальных - нужно еще 2 раза пробовать. Например, при 2б1к:
6 или 8
5) 1632 - 3б0к, 4б0к - либо закончено, либо - нет если нет - еще 1 ход:
6) 1832 - 4б0к.
То есть, гарантированно отгадали за 6 ходов. Это один вариант (первый ход 2б1к, второй - 1б2к). В других, может быть, будет иначе... Для этого надо полностью перебрать все комбинации. Или просто действовать по правилу, которое уже предложили выше - писать число, удовлетворяющее всем вышеупомянутым исходам. Для удобства можно добавить - минимальное.
Вообще, каждый ход "обрезает" количество вариантов. Изначально их 10*9*8*7=5040 (не берем в расчет версию игры с первой ненулевой). После первого хода происходит "обрезание".
Начинать надо, очевидно, с 1234. Потому что никакой разницы нет. Ну, только если случайно угадаешь с первого хода - но это лотерея.
Исходов может быть несколько, возьму и выпишу их:
4б0к,
3б0к, 3б1к,
2б0к, 2б1к, 2б2к,
1б0к, 1б1к, 1б2к, 1б3к,
0б0к, 0б1к, 0б2к, 0б3к, 0б4к.
Всего - 15. В каждом нужно применять свою логику.
Например, 2б1к - 6 вариантов пар "быков", и в каждом случае 2 варианта одной "коровы", она встает на место "лишней" цифры, а на ее "коровье" место - встает одна из 6 оставшихся цифр (5..0).
6*2*6=72 варианта. Например, 1439, 2734 и т.д. А вот дальше...На второй ход можно задаться постулатом: предполагать "быками" наименьшие цифры, затем - "коровами" - наименьшие из оставшихся.
Т.е. в данном случае - (1234 - 2б1к): предположим вариант 12*3. Видимо, нужно ставить 1253 (опять - нет никакой разницы между другими вариантами). И опять - в общем случае, один из 15-ти вариантов исхода. Тогда нужно искать перекрывание тех (72) вариантов, и этих.
Ну, допустим, что тут вышло 1б2к.
Перебор вариантов - рассмотрим, какие возможны были пары "быков" в (1234):
12 - тогда в (1253) должно быть минимум 2 быка. Пр-речие.
13 - т.е. либо 2, либо 5 - "корова". (другая "корова" - 3). Во втором варианте - означает, что "корова" из (1234) - 4. Т.е.: 1*32, 1435. На месте звездочки - 6..0. Всего - 5 вариантов.
14 - тогда 5 - "корова" точно (из 2 и 3 - только 1 "корова"). Т.е. 15*4 (либо 2 либо 3 на месте звездочки), т.е. только 1524.
23 - Тогда в (1253): 2 - "бык", 3 - "корова". Еще одна корова - либо 1, либо 5. Во втором случае - 4 есть "корова" из (1234). Т.е. имеем 4235 или *231, на месте звездочки 6..0.
24 - тогда 5 - точно "корова". Т.е. 52*4, на месте звездочки либо 1, либо 3 (но надо помнить, что это "корова" из (1234)). Т.е. 5214.
34 - тогда в (1253) 1 и 2 - не "быки", 5 - аналогично, 3 - только "корова". Пр-речие.
Итог (в порядке возрастания): 1435, 1524, 1*32, 4235, 5214, *231 (на месте * - 6,7,8,9,0) Всего - 14 вариантов.
Аналогично можно провести такую же логику для остальных вариантов первого исхода, затем соответственно приведенного второго. Получается многоэтажное ветвление. 15 ветвей первого уровня, от каждой - не более чем 15 ветвей второго уровня, получаем около двухсот вариантов. В каждом - по (навскидку) паре десятков наборов.
Идем дальше - 14 вариантов (ну, 6, но в некоторых еще надо подставлять неизвестные доселе цифры)... это немало. Можно взять снова минимальное число, 1435.
Дальше - зависит от правильного ответа:
1435 - 4б0к
1524 - 1б2к
1*32 - 2б0к
4235 - 2б1к
5214 - 0б3к
*231 - 1б1к
Исходы - разные! Четвертым ходом мы просто называем нужное число... Кроме случаев №3 и №6. Ими и займемся.
Еще раз повторим наши ходы:
1) 1234 - 2б1к
2) 1253 - 1б2к
3) 1435 - 2б0к
Следовательно, ответ - вида 1*32, где на месте звездочки - одна из цифр 6, 7, 8, 9, 0. Для ее гарантированного выбора требуется 3 хода.
Поясню это: буду писать варианты ответов: для 6, 7, 8, 9, 0 соответственно:
4) 6782 - 2б1к, 3б1к, 2б1к, 2б0к, 2б0к
- имеем три варианта ответа. Во втором (3б1к) - пишем сразу ответ. В остальных - нужно еще 2 раза пробовать. Например, при 2б1к:
6 или 8
5) 1632 - 3б0к, 4б0к - либо закончено, либо - нет если нет - еще 1 ход:
6) 1832 - 4б0к.
То есть, гарантированно отгадали за 6 ходов. Это один вариант (первый ход 2б1к, второй - 1б2к). В других, может быть, будет иначе... Для этого надо полностью перебрать все комбинации. Или просто действовать по правилу, которое уже предложили выше - писать число, удовлетворяющее всем вышеупомянутым исходам. Для удобства можно добавить - минимальное.
Ни разу не встречал. Тяжело решать, наверноDendr писал(а): 3б1к
IMHO даже если с 1го хода получаешь ответ 3Б0К, оптимальный алгоритм найти непросто.
И, кстати, 2Atson: что такое "оптимальный"? Допустим, есть выбор:
1)гарантированно отгадать за 8 ходов или
2)отгадать за 6 ходов с вероятностью 90% и за 9 ходов с вероятностью 10%. Что подразумеваем под оптимумом?
-
Dendr
- Акула пера
- Сообщения: 5717
- Зарегистрирован: 06 май 2005, 15:11
- Пол: Мужской
- Откуда: Раменское, Мос.обл.
- Контактная информация:
Ну, накинулись... Стормозил сначала)))team55 писал(а):Ни разу не встречал. Тяжело решать, наверноDendr писал(а): 3б1к
Алгоритм тут несложный. Дело в том, что комбинирование цифр делает их равнозначными. В 3б0к - имеем один из 4-х вариантов:team55 писал(а):IMHO даже если с 1го хода получаешь ответ 3Б0К, оптимальный алгоритм найти непросто.
123*
12*4
1*34
*234
и на месте * стоит одна из цифр 5..0
Варианты - равноценны (с точностью до перестановки цифр и переобозначения их), все из 6 цифр - тоже.
Поэтому вариант следующего хода - на самом деле один-единственный:
1235
Если в ответе нет четверки, то мы получим 3бк0, как минимум. Или, если попали, 4б0к.
Если есть, то у нас только 2 "быка" (пятерка может быть в лучшем случае коровой) Т.е. 2бк0 или 2бк1.
Итак:
1) 1234 3бк0
2) 1235 - а) 4бк0 (победа) б) 3бк0 в) 2бк0 г) 2бк1
случай (г) - означает один из вариантов 1254, 1534, 5234. Перебором находим ответ. 5 ходов максимум.
случай (б) - у нас ответ вида 123*, на месте * - 6, 7, 8, 9 или 0. Делаем так: 3) 1678. Заведомо 1-"бык". 6 и 7 могут быть только коровами (1б1к), 8 - может быть "быком" (2б0к). Если же в ответе 9 или 0, то исход будет 1б0к. Двумя ходами находим ответ.
случай (в) - распишем отдельно
1) 1234 3бк0
2) 1235 2бк0
Варианты: 12*4, 1*34, *234. На месте * - 6..0
Пишем: 3) 1264.
Если тройка - в ответе, то 4 - "бык", 1 или 2 - бык, 6 - только "корова" в лучшем случае. Т.е. будет а1) 2б0к или б1) 2б1к.
Если тройки нет в ответе, то в1) 3б0к или г1) 4б0к (победа)
(в1): ответ вида 12*4, на месте * - 7,8,9,0. Тремя ходами выясняем это (докажите сами в качестве домашнего задания
). Итого - 6 максимум.(б1): либо 1634, либо 6234. два хода (итого - 5)
(а1): 1*34 или *234, на месте * - 7,8,9,0
4) 1734 - если тип 1*34, то исход либо 4бк0 (победа), либо 3бк0 - 1834, 1934, 1034. За два хода выясним ответ (докажете это сами?
).- если *234, то либо 2бк1 (ответ - 7234), либо 2бк0 (ответ - 8234, 9234, 0234). Аналогично - плюс два хода.
Итого - при исходе первого хода 3бк0 можно решить задачу за 6 ходов максимум. (последним ходом считается ход с ответом 4бк0)
Также я уже (вроде, брал только самые "жесткие" варианты) доказал, что при двух "быках" при первом ходе, можно найти ответ за 7 ходов.
При меньшем числе "быков" число вариантов резко растет, не так-то просто разобрать их все.
Самый тяжелый - когда ответ будет 0б1к - остается 1440 вариантов (из 5040 первоначальных). А если второй ход делать 5678, то при 0б2к получится 504. Не многим лучше (может, надо другой вариант - к примеру, 1567 или 2567). Самый длинный путь, скорее всего, будет именно тут, его и надо анализировать. Пока в процессе....
