Счетные головки — динамическое программирование

Проблема:

При заданных целых числах n и k вместе с p1,p2,..., pn; where pi ε [0, 1] вы хотите определить вероятность того, что выпадет ровно k решка, когда n смещенных монет подбрасываются независимо случайным образом, где pi – это вероятность того, что i монета выпадает орлом. Приведите алгоритм O(n2) для этой задачи. Предположим, вы можете умножить и сложить два числа из [0, 1] за время O(1).

Может ли кто-нибудь помочь мне с разработкой рекуррентного отношения, чтобы я мог его закодировать. (Вопрос исходит из обратного упражнения главы «Динамическое программирование» в книге «Алгоритмы Дасгупты»)


recurrence algorithm dynamic-programming
person Gaurav    schedule 27.10.2012    source источник

Ответы (1)


arrow_upward
13
arrow_downward

Рассмотрим ситуацию, когда (n-1) монет подбрасывают вместе, а n-ю монету разбрасывают, и примите во внимание взаимную независимость.

Объедините вероятности более простых случаев, чтобы получить P (1.. n, k) (где P (1.. n, k) — вероятность получения ровно k решек при n монетах)

Затем примените это правило и заполните все ячейки в таблице NxK.

Изменить:

Есть два возможных способа получить ровно k решек с n монетами:

а) если у (n-1) монет k решка, а N-я монета решка, и

б) если (n-1) монет имеет k-1 решку, а N-я монета является решкой

so

P(n, k) = P(n-1, k) * (1 - p[n]) + P(n-1, k-1) * p[n]

person MBo    schedule 27.10.2012
comment
Итак, мы можем использовать это рекуррентное соотношение: P(N,K) = max {P(N-1,K), P(N-1,K-1)} + p‹sub›i‹/sub› И начнем с Р (п, к) - person Gaurav; 28.10.2012
comment
извините, я не знаю, как написать индекс здесь. p‹sub›i‹/sub› — это p с нижним индексом i - person Gaurav; 28.10.2012
comment
Нет, нам не нужно выбирать максимум. Вы должны вычислить вероятность, а не какой-то оптимум. - person MBo; 28.10.2012
comment
Так каким же тогда будет рекуррентное соотношение? - person Gaurav; 28.10.2012
comment
Я надеялся на ваше решение с некоторыми подсказками... Хорошо, добавлена ​​формула отношения - person MBo; 28.10.2012