投硬币的问题

周瑜 · 发表于 2010-5-1 04:42:47

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

连续投掷N次硬币，其中任意连续m次出现正面朝上次数最大值为x的概率是多少？

如果x=m，那么就转化为N次中存在连续m次正面朝上的概率求解，本版已有答案。但是当x<m时怎么解，还请大家指教。

KeyTo9_Fans · 发表于 2012-1-15 16:21:07

想到了一个动态规划算法。

记录最近$(m-1)$次抛出的正反面序列。

一共有$2^(m-1)$种序列。

记录每种序列出现的概率，空间复杂度为$O(2^m)$。

于是就可以计算再抛$1$次后，每种序列出现的概率。

一共要计算$N$次，时间复杂度为$O(N*2^m)$

不知道有没有多项式时间复杂度的算法。

wayne · 发表于 2012-1-26 09:44:38

1# 周瑜
所谓的任意连续m次正面朝上，是指这个连续的m次的整体的前后都不是正面的吗

mathe · 发表于 2012-1-27 11:45:17

的确表达上有问题，感觉不就是投掷m次有正好最大x次朝上的概率吗？

账号		自动登录	找回密码
密码			欢迎注册

[提问] 投硬币的问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。