Есть простенькая компьютерная игра. Компьютер случайно генерирует любое число от 1 до 9(шансы равны), а игрок пытается его отгадать.

1.Если указанное игроком число больше загаданного, то компьютер выдает сообщение "Указанное Вами число больше загаданного"

2.Компьютер ничего не сообщает, если указанное число меньше загаданного.

3.Если игрок выбрал загаданное число, и все условия победы НЕ выполнены, то компьютер ничего НЕ сообщает(в противном случае, он сообщает об победе).

4.Победа происходит только в том случае, если выполнены ОБА условия(последовательность выполнения условий может быть любой):

а.В течении игры игрок называл загаданное число(или как вариант, хотя загаданное число и не было названно, после хода игрока его можно автоматически идентифицировать как таковое. Например, если компьютер загадал единицу, а игрок назвал двойку, то будет автоматически засчитана победа, так по имеющейся у игрока информации(двойка больше, чем загаданное число) можно однозначно сказать, какое число было загаданным).

b.Игрок назвал число, которое на единицу больше загаданного. Если такого числа нет(то есть было загаданно число 9), то для победы достаточно выполнения условия "а".

5.При победе компьютер сообщает, какое число было загаданным.

Задача в том, чтобы обеспечить себе победу за как можно меньшее количество ходов и с наибольшей вероятностью. Честно говоря, я не особо силен в математике, поэтому если это возможно, прошу все объяснить "на пальцах". В смысле, саму стратегию игры. Как это все расчитывалось, меня не особо волнует.

задан 16 Мар '13 0:27

изменен 16 Мар '13 1:02

Я вроде бы понял смысл игры, но одно из условий нужно слегка подкорректировать. Логично предположить, что победа мне присуждается тогда, когда у меня достаточно информации для однозначного определения того, что было загадано. Пока что в формулировке есть одна неувязка. Вы требуете выполнения обоих условий для присуждения победы, но что если компьютер загадал число 9? Тогда я не могу назвать число, на единицу большее (если правила не разрешают выходить за пределы от 1 до 9). По идее, если компьютер загадал 9, и я назвал 9, то я уже знаю, что я угадал, потому что компьютер ничего не ответил.

(16 Мар '13 0:51) falcao

"но что если компьютер загадал число 9?". Ах да, забыл про это написать. Да, тогда победа засчитывается. Просто я немного не учел этот нюанс.

" Логично предположить, что победа мне присуждается тогда, когда у меня достаточно информации для однозначного определения того, что было загадано" Из этого правила есть исключение, насколько я понимаю. Предположим компьютер загадал 5, а я назвал четверку, а потом пятерку. Победа будет засчитана, хотя в данной ситуации игрок самостоятельно не может определить загаданное число, ему об этом сообщит компьютер после победы.

(16 Мар '13 1:00) Tsukune

И да, если кому интересно, автор игры(вернее правил к ней, так как подобной игры я еще не видел) - я. Фактически сформулированные мною правила родились в результате творческого переосмысления обычного деления столбиком. =)

(16 Мар '13 1:05) Tsukune

Хотя нет, похоже вру насчет исключения. Ведь если 4 было бы загаданным числом, то компьютер сказал бы насчет того, что 5 больше

(16 Мар '13 1:17) Tsukune

Я еще зайду где-то через 7 часов.

(16 Мар '13 1:23) Tsukune
10|600 символов нужно символов осталось
1

Итак, я буду рассматривать задачу в такой постановке. Компьютер с равной вероятностью загадывает какое-то число от $%1$% до $%n$%. Игрок называет какое-то число, и компьютер отвечает на вопрос, верно ли, что названное число больше загаданного. То есть он отвечает "нет", если названное число меньше загаданного или равно ему. Игроку присуждается победа (не важно, кем именно) ровно в тот момент, когда по имеющейся у него информации загаданное число определяется однозначно.

Дадим ответ на вопрос, какая стратегия является оптимальной при каждом $%n$% от $%1$% до $%9$%, и сколько в среднем потребуется задать вопросов для победы. Это число вопросов обозначим через $%f(n)$%, и покажем, как эти числа последовательно найти.

Прежде всего, ясно, что $%f(1)=0$%. Далее, если $%n=2$%, то надо назвать число $%2$%, что позволит однозначно узнать, какое число загадано. Если компьютер скажет "да", то загадана единица, а если "нет", то загадана двойка.

Теперь пусть $%n=3$%. Ясно, что называть число $%1$% бессмысленно из-за предсказуемого ответа "нет". Если названо $%2$%, то с вероятностью $%1/3$% компьютер ответит "да", и тогда мы за один ход угадали число $%1$%. Но с вероятностью $%2/3$% ответ будет "нет", если загадано $%2$% или $%3$%. Тут нам потребуется ещё один ход, чтобы угадать, какое именно из этих двух чисел загадано. То есть всего здесь потребуется два хода. Среднее число ходов для угадывания будет равно $%(1/3)\cdot1+(2/3)\cdot2=5/3$%. Легко понять, что то же самое произойдёт, если мы назовём число $%3$%. С вероятностью $%1/3$% ответ будет "нет" (если загадано $%3$%), и с вероятностью $%2/3$% будет сказано "да" (если загадано $%1$% или $%2$%). Эта ситуация полностью симметрична предыдущей. Таким образом, $%f(3)=5/3$%, а стратегия состоит в том, что называть надо $%2$% или $%3$%.

Удобно далее каждое из чисел $%f(n)$% представить в виде дроби $%g(n)/n$% (она в каких-то случаях может оказаться сократимой, но это не важно). И далее мы будем следить не за дробями, а за числами вида $%g(n)$%. На данный момент мы знаем, что $%g(1)=0$%, $%g(2)=2$%, $%g(3)=5$%. Заметим также, что если мы знаем стратегию и среднее число ходов для угадывания числа от $%1$% до какого-то $%m$%, то мы знаем то же самое для любых $%m$% последовательных натуральных чисел. Это значит, что если компьютер загадывает число от $%6$% до $%8$% включительно (с той же равной вероятностью), то это ничем не отличается от задачи с числами $%1$%, $%2$%, $%3$%.

Найдём числа $%f(4)$% и $%g(4)$%, после чего станет ясна общая закономерность. Пусть игрок назвал число $%k+1$%. Тогда все числа можно разделить на те, которые меньше $%k+1$% -- их имеется ровно $%k$%, и все остальные, которых имеется $%n-k$%. Ясно, что с вероятностью $%k/n$% компьютер загадал одно из $%k$% чисел, и в этом случае ответ будет "да", а с вероятностью $%(n-k)/k$% он загадал одно из $%n-k$% чисел, и тогда ответ будет "нет". После ответа игроку надо будет угадать либо одно из $%k$% идущих подряд чисел, что в среднем требует $%f(k)$% ходов, либо одно из $%n-k$% последовательных чисел, что в среднем требует $%f(n-k)$% ходов. Во всех случаях сохраняется равная вероятность того, что загадано одно из последовательных чисел определённого диапазона. Таким образом, когда мы называем число $%k$%, то нам в среднем потребуется для угадывания сделать $%1+(k/n)f(k)+((n-k)/n)f(n-k)$% ходов (первое слагаемое учитывает тот ход, который мы только что сделали). Мы при этом должны подобрать такое $%k < n$% (напомним, что называемое игроком число мы обозначили через $%k+1$%), чтобы полученное среднее значение оказалось минимальным. Оно и будет равно $%f(n)$%, а число $%g(n)$% будет в $%n$% раз больше, и потому оно будет равно минимальному значению выражения $%n+kf(k)+(n-k)f(n-k)=n+g(k)+g(n-k)$%. Таким образом, имеет место следующая рекуррентная формула: $$g(n)=\min\limits_{k < n}\,(g(k)+g(n-k)),$$ и стратегия будет состоять в выборе числа $%k$%, на котором достигается этот минимум. (Вообще говоря, оно может принимать не единственное значение.)

Итак, при $%n=4$% мы рассматриваем найденные ранее числа $%g(1)=0$%, $%g(2)=2$%, $%g(3)=5$%, и далее сравниваем значения сумм $%g(1)+g(3)=5$%, $%g(2)+g(2)=4$%. Вот втором случае значение является наименьшим, и это значит, что называть надо число $%3$%, и при этом $%g(4)=4+g(2)+g(2)=8$%, а $%f(4)=8/4=2$%. Иными словами, одно из четырёх загаданных чисел в среднем будет угадываться два хода.

Далее действует по описанному алгоритму. Для нахождения $%g(5)$% выпишем уже найденные числа вида $%g(n)$%, то есть $%0,2,5,8$%. Суммы, которые надо сравнивать -- это $%0+8$% и $%2+5$%. Второе из значений меньше, и это значит, что надо называть или $%3$%, или $%4$%. После чего с вероятностью $%2/5$% нам надо будет угадать одно число из двух, и с вероятностью $%3/5$% одно число из трёх. Теперь надо не забыть прибавить $%n=5$%, и получить $%g(5)=5+2+5=12$%.

Далее этот способ приводит к таким равенствам: $%g(6)=6+2+8=6+5+5=16$% (здесь можно называть любое число от $%3$% до $%5$%); $%g(7)=7+5+8=20$% (называть надо $%4$% или $%5$%), $%g(8)=8+8+8=24$% (называем $%5$%), и, наконец, осталось найти $%g(9)$%. У нас к этому времени найдены числа $%0,2,5,8,12,16,20,24$%, и минимальная сумма чисел, равноотстоящих от концов, равна $%g(4)+g(5)=8+12=20$%, то есть называть надо число $%5$% или $%6$%, при котором $%9$% чисел разбиваются на две группы с количеством $%4$% и $%5$% (так, если мы назвали $%6$%, то в одной группе числа от $%1$% до $%5$%, а в другой -- от $%6$% до $%9$% в количестве $%4$% штук). Итого мы имеем здесь $%g(9)=9+20=29$%, и $%f(9)=29/9$%, то есть число от $%1$% до $%9$% угадывается в среднем за такое количество шагов, приблизительно равное $%3,222...$%.

Можно установить некую общую закономерность для этой последовательности, и найти её значения для каких угодно $%n$%.

Будет хорошо, если я решил именно ту задачу, которая имелась в виду. Мне она весьма понравилась.

ссылка

отвечен 16 Мар '13 3:30

Спасибо за ответ! Теперь будут разбираться в этом решении.

(16 Мар '13 9:42) Tsukune
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,001
×82

задан
16 Мар '13 0:27

показан
1645 раз

обновлен
16 Мар '13 9:42

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru