QBasic, тест на интеллект.

geh · Сообщение **geh** » 29 дек 2013, 04:44

Очень интересно все то, о чем здесь было сказано. Но все гораздо проще и прозаичнее.
Вот описание алгоритма для решения этой задачи при n=10. Итак мы задаем компьютеру
число состоящее из 9-ти нулей и одной единицы. В самом неблагоприятном случае потребуется
девять ходов, чобы определить, где стоит 0 и 1. (0 определится если 1 встанет на его место, в
противном случае это будет последний непроверенный 0 (его можно и не проверять)). Далее
заменяя ненужные нули двойками и добавляя цифру 3 за 7 ходов определим и эти цифры.
итак, 9+7+5+3+1=25 ходов достаточно, чтобы знать число. ( это неинтересно). При n=9
число вариантов равно 21. Но для теста большие числа не годятся, поэтому все ограничивается n=6.

kiv · Сообщение **kiv** » 29 дек 2013, 08:08

geh писал(а):Source of the post
Очень интересно все то, о чем здесь было сказано. Но все гораздо проще и прозаичнее.
Вот описание алгоритма для решения этой задачи при n=10. Итак мы задаем компьютеру
число состоящее из 9-ти нулей и одной единицы.

Фи, как неспортивно - в запросе тоже не должно быть одинаковых цифр...
А теперь примените этот метод к трехзначному числу - чтоб считать поменьше - и найдите необходимое количество запросов...

Ian писал(а):Source of the post
Ответ = комбинации двух расстояний
...
А дальше есть у военных, алгоритмы "как эти штаты уж разбиты на квадраты"

Интересно подойти с точки зрения информации. Для четырехзначных чисел информация о конкретном числе - 12.3 бита. А вот как оценить информацию в ответе на один вопрос или хотя бы как, зная множество возможных ответов, найти вопрос, который даст наибольшую информацию?

Я тут попробовал несколько эвристик для трехзначных чисел (трехзначных, чтоб быстрее считалось) - но всегда находится частный случай с 8 запросами... Только рандомизация дала пару раз семерку, но это не наш метод

Ian · Сообщение **Ian** » 29 дек 2013, 09:26

kiv писал(а):Source of the post
Интересно подойти с точки зрения информации. Для четырехзначных чисел информация о конкретном числе - 12.3 бита. А вот как оценить информацию в ответе на один вопрос или хотя бы как, зная множество возможных ответов, найти вопрос, который даст наибольшую информацию?

Информация, содержащаяся в ответе на любой первый вопрос из 3х различных цифр, считается по определению. Находим распределение вероятностей ответов
Р(3,3)=0,001
P(3,1)=0,003
P(2,2)=0,008
P(2,1)=0,048
... и когда добьем это до суммы =1, берем $I=-\sum p\log_2p$
Только это быстрее сделать программой перебора
Дальше интересно посчитать информацию, содержащуюся в 2х ответах на 2 непересекающихся вопроса (не содержащих ни одной общей цифры).И тут сюрприз: она меньше, чем удвоенная посчитанная ранее. И как бы вопросы ни пересеклись, то же случится.Это теорема, якобы нарушение закона сложения информации. Так как один из этих вопросов уже не первый и относится к другому информационному множеству (условные вероятности пошли)

geh · Сообщение **geh** » 29 дек 2013, 11:10

Применение одинаковых цифр в трехзначном варианте не даст никакого
выигрыша. Максимальное число ходов в самом неблагоприятном случае
равно 10. Хуже того, до выявления всех цифр, а это происходит в самом
конце, выиграть невозможно. А если цифры разные, то и у первого хода
есть шанс выиграть. (с повторяющимися цифрами это не пройдет). В общем
не стоит запрещать вводит числа с одинаковыми цифрами - это верная
гарантия проиграть!

kiv · Сообщение **kiv** » 29 дек 2013, 11:18

geh писал(а):Source of the post
В общем
не стоит запрещать вводит числа с одинаковыми цифрами - это верная
гарантия проиграть!

Вызываю на дуэль
Можете играть как угодно нечестно (т.е. менять на ходу загаданное число, лишь бы ВСЕ ответы были корректны), я всегда использую в запросе только числа с разными цифрами. Трех, четырех, пятизначные числа - неважно, согласен на любые.

Не более чем после 8 вопросов-ответов говорю вам окончательный ответ.

Хотите?

geh · Сообщение **geh** » 29 дек 2013, 14:46

Вы выиграли! Я сражён вашим интеллектом, вашими знаниями, вашим
слогом и стилем излагать свои мысли. Но программу можно усовершенствовать
в смысле придать ей большую непредсказуемость. Например, разрешить программе
один раз в пять ходов солгать в ответе. И 8-ми ходов будет мало. И нам придется
ломать голову над вопросом где Истина, а где Ложь?!

kiv · Сообщение **kiv** » 29 дек 2013, 14:51

geh писал(а):Source of the post
один раз в пять ходов солгать в ответе. И 8-ми ходов будет мало. И нам придется
ломать голову над вопросом где Истина, а где Ложь?!

Неоднозначное решение.

Vacuumatic · Сообщение **Vacuumatic** » 29 дек 2013, 18:45

kiv писал(а):Source of the post
geh писал(а):Source of the post

Да это все понятно, просто я написал отгадывалку. Она отгадывает любое загаданное число максимум за 8 попыток. Это справедливо и для 3, и для 4, и для 5-значных чисел.

Вот меня и заинтересовало - это что, какой-то теоретический предел или нет?

Лет 20 назад я для интереса написал программу игры "Быки и Коровы"(4 цифры). Без мухляжа и подглядывания программа одгадывала мое число за 6 ходов.

kiv · Сообщение **kiv** » 29 дек 2013, 19:45

Vacuumatic писал(а):Source of the post
Лет 20 назад я для интереса написал программу игры "Быки и Коровы"(4 цифры). Без мухляжа и подглядывания программа одгадывала мое число за 6 ходов.

Опишите алгоритм, pls, если уж нет исходника...

Vacuumatic · Сообщение **Vacuumatic** » 29 дек 2013, 21:07

kiv писал(а):Source of the post
Vacuumatic писал(а):Source of the post
Лет 20 назад я для интереса написал программу игры "Быки и Коровы"(4 цифры). Без мухляжа и подглядывания программа одгадывала мое число за 6 ходов.

Опишите алгоритм, pls, если уж нет исходника...

Сейчас уже не вспомню. Сложного ничего не было - матрица 4х10, вычеркивание позиций в зависимости от ответа играющего...
Если быть точнее где то 90% было побед за 6 ходов, немного за 7, и редко за 8 ходов.
В этой игре думаю можно было бы применить анализ цифр, загадываемых играющим. При достаточно большом количестве сыгранных партий, программа сможет выявить наиболее часто подсознательно используемые играющим цифры и их комбинации. Тогда наверно за 5 ходов можно было бы отгадать.

yourdomain.com