Задача состоит в следующем:
У игрока изначально есть приз размером 1 очко. Есть также последовательность вопросов n штук.
Для каждого вопроса у игрока есть два действия:
Забрать текущий приз и выйти из игры.
Попытаться ответить на вопрос. Если он отвечает правильно, то приз удваивается и игра продолжается, иначе игрок не получает ничего.
Если вопросы закончились, то игрок забирает текущий приз и уходит. Нужно выбрать такую стратегию для игрока, чтобы максимизировать математическое ожидание выигрыша. Для каждого вопроса вероятность правильно ответить на него равномерно распределяется между t и 1. Причем, перед тем как решить ответить или нет, мы заранее узнаем эту вероятность.
Примеры:
n = 1, t = 0.5
Ответ: 1.500
n = 1, t = 0.3
Ответ: 1.357
n = 2, t = 0.6
Ответ: 2.560
Объясните пожалуйста, как получаются подобные ответы к задаче.
P.S. Обновил условие, оказывается задача выглядит немного не так.
Например на 1-ый тест.
Ответ если мы не будем отвечать — 1. Если будем, то
это по определению. Это счастье равно как раз 1.5.
Для второго примера будет тоже самое вычисление.
Для третьего просто будет три варианта когда остановиться. Для каждого аналогично считается матожидание и выбирается лучший.
Видимо, я туплю.
. При t = 0.3 получается 1.3, а не 1.357.
UPD: а если t = 1, то вообще
непонятно, как получить 1.357
а так кажется, что ответ — это (t + 1)n
Хм. Может быть имеется ввиду, что сначала узнается сложность потом решается отвечать или нет?
Да, именно так, вероятность как бы узнается заранее.
Напиши явно в посте об этом, а то сейчас фиг догадаешься.
интуитивно чувствуется, что правильная стратегия — всегда отвечать на вопрос, потому что вероятность ответа в среднем не хуже 0.5, а приз удваивается, то есть матожидание не может уменьшаться
осталось посчитать искомую вероятность
А точно такое условие? Мне эта задча что-то напоминает, но в том условии было сказано, что мы узнаем вероятность, с которой мы ответим на вопрос, прямо перед тем, как мы решим, заберем деньги или не будем их забирать. Вроде чтобы ответ получить, нужно считать матожидания от одной игры до n. И там вроде до какой-то вероятности выгодно забирать деньги, а после какой-то отвечать. Точно не помню, что там были за формулы...
Вроде вспомнил, как я решал эту задачу. Пусть мы знаем, что получим матожидание 2*E, если продолжим отвечать. Разобьём отрезок [t,1] на мелкие отрезки одинаковой длины detla x . Вероятность, что случайная величина попадёт в этот интервал = delta x / (1 — t ). Во всем интервале будем считать, что вероятность равна x (координата левого конца). Матожидание будет равно в этом случае max ( 1 , 2 * x * E ) *delta x / (1-t) . Устремим delta x к 0 . Получим интеграл от t до 1 max(1, 2*x*E) / (1-t) dx . Вот. Если этот интеграл раскрыть, то получим формулу для рассчета ответа.
1.Если t>=0.5, то ответом будет являться выражение (1+t)^n, так как в этом случае нам невыгодно останавливаться.2.Иначе: для начала рассмотрим случай для n=1 — 1)если вероятность>=0.5, то нам выгоднее ответить на вопрос,2)иначе останавливаемся.Посчитали для одного, значит можно построить лёгкую динамику и за сложность O(n) вычислить ответ для n
UPD: Если возможно, хотелось бы ещё примеров для проверки формулы
Мне кажется, что равномерно распределённую вероятность от t до 1 можно заменить на вероятность правильного ответа
> = 
, т.е. лучше всегда пытаться отвечать, т.е. формула (t + 1)n работает всегда.
Проблема в том, что 1.357 из второго примера вообще непонятно как получать... :)
а по моей формуле получается — если вероятность находится в промежутке от 0.3 до 0.5, то есть в 2/7 от всех возможных случаев, то мы останавливаемся, а если вероятность находится в промежутке от 0.5 до 1.0 (5/7 от всех случаев) отвечаем на вопрос. В итоге мат. ожидание равно 2/7 + (5/7)*(0.5+1)/2 * 2 = 1.357142857..
Получается игрок знает какая вероятность от t до 1 ему выпала?
, то отвечать конечно не следует, иначе пробуем идти до конца! Всё довольно очевидно, кроме условия :-|
UPD: Я понял, под "этой" подразумевается уже полученная вероятность из [t;1], тогда, если она