这是某公司的笔试题,大家有空可以做做看。
另外一个变形是,硬币铸造时有差错,抛出字和花的概率分别是p和1-p (0<=p<=1),问平均要抛多少次才能结束这个游戏。
On May 13, 9:49 am, sagasw <sag...@gmail.com> wrote:
> 1/4 + 1/4 * 1/4 * 1/2
> 不知道算的对不对,
> 字为1,花为0,组合为00,01,10,11,
> 出现11的可能性为1/4,
> 出现01后面跟着10的情况为1/4 * 1/4 * 1/2
>
> 2009/5/13 Shuo Chen <giantc...@gmail.com>
假设刚好抛n次就结束游戏的概率为p(n),那么p(1) = 0, p(2) = 1/4, p(3) = 1/8, p(4) = 1/8, p
(5) = 3/32
刚好抛3次结束游戏,那么抛法只有一种:'011',所以p(3) = 1/8
刚好抛4次结束游戏,那么抛法有2种:'0011'和'1011',所以p(4) = 2/16 = 1/8
刚好抛5次结束游戏,抛法有3种:'00011', '01011', '10011',所以p(5) = 3/32
那么平均抛的次数x = 2*p(2) + 3*p(3) + 4*p(4) + 5*p(5) + ... + n*p(n),n 趋近无穷
问题转换为怎么求p(n),先歇口气,待会儿说。可以看出,如果刚好抛n次结束(n > 3),那么最后三次一定是'011',而且前面n-3次里没有
包含'11',否则就提前结束了。
On May 13, 10:10 am, supern lee <supern....@gmail.com> wrote:
> 任意连续两个出现的概率是1/4,
> 那么n次中的连续两次有(n-1),
> 则1/4*(n-1)=1
> 所以需要5次
>
> 2009/5/13 sagasw <sag...@gmail.com>
>
> > 概率是0.28
> > 相当于抛四次吧。
>
> > 2009/5/13 Shuo Chen <giantc...@gmail.com>
On May 13, 10:57 am, 吴彧文 <atyu...@gmail.com> wrote:
> 像这种硬币游戏求概率或者平均投掷次数一般都可以用递归的。
> T = 1 + 0.5T + 0.5( 1 + 0.5 * 0 + 0.5T)
> T = 6.
> 很容易推广到出字概率为p的情况。
> 2009/5/13 Shuo Chen <giantc...@gmail.com>
具体级数计算公式不记得了,哈哈。
解方程.
设所求期望为 e, 在上次是字/花的情况下期望分别是 h, t:
e = p(1+h) + (1-p)(1+t)
h = p + (1-p)(1+t)
t = p(1+h) + (1-p)(1+t)
易得 h = 1/p^2, e = t = (p+1)/p^2
p = 0.5 时, h = 1/0.25 = 4, e = t = (0.5+1)/0.25 = 6
--
Alecs King
用向量 [A B] 表示 [尾为A的组合数 尾为B的组合数],
因为A后面只能接B,而B后面可以接A或B,所以状态转移矩阵 M 是
0 1
1 1
一次结果:A、B
[A1 B1] = [1 1]
两次结果:AB、BA、 BB
[A2 B2] = M*[A1 B1] = = [1 2]
三次结果:
[A3 B3] = M*[A2 B2] = = [2 3]
四次结果:
[A4 B4] = M*[A3 B3] = [3 5]
A1,A2,A3....An 这个数列的意义是,抛n 次,得到*非终止*序列的 而且最后一次为 A 的组合数。
只要在这些组合后面再抛一次 A 即可得到终止序列。
从上面可以看出 An 正是斐波那契数 F(n),可以直接代入通项公式。
所以抛 n 次得到终止序列的概率为 F(n-1)/2^n
得到终止序列的抛硬币次数期望为:2*F(1)/2^2 + 3*F(2)/2^3 + 4*F(3)/2^4 + ....
对于期望的计算, 可以考虑生成函数.
设
G(x) = F(1)/2^2 * x^2 + F(2)/2^3 * x^3 + F(3)/2^4 * x^4 + ...
将递归关系带入得到
G(x) = x/(4-2x-x^2)
于是那个无限求和的期望就等于 G'(1)=4.
注意这个期望是最后两次A之前的试验次数, 故加上最后两次A就是期望6了.
On 5月14日, 上午9时50分, chaoyan ma <chaoyan...@gmail.com> wrote:
> 好像状态转移图也可以哦,在0101......序列中匹配11字符串
> A B C Z状态分别代表匹配了0个1 1个1 和2个1的状态
> 初始化进入A或B状态 A匹配到1转移到B A匹配到0转移到A B匹配到1转移到C B匹配到0转移到A
> 是不是能这样说?在图中转移次数总共是6次 转移到A的次数是3次 占1/2 转移到B的次数是2次 占1/3 转移到C的次数是1次
> 占1/6
> 所以 平均抛6次能到11状态??
> 2009/5/13 Shuo Chen <giantc...@gmail.com>
> 离你越近的地方,路途越远;最简单的音调,需要最艰苦的练习- 隐藏被引用文字 -
>
> - 显示引用的文字 -
我觉得应该是:
E[X] = 2p^2 + 3p^2(1-p) + 4p^2(1-p)^2 + ... + np^2(1-p)^(n-2)
就是求级数忘记了 :(