有1,2,3,......无穷个格子，你从1号格子出发，每次_

推荐

AndyJee

E

跳一格跳两格都算一步；

dp(i,j)表示从格子i到格子j的期望步数：

dp(1,4)=1+0.5*dp(2,4)+0.5*dp(3,4)；

dp(2,4)=1+0.5*dp(3,4)+0.5*dp(4,4);

dp(3,4)=1+0.5*dp(4,4)+0.5*dp(1,4);

dp(4,4)=0;

求解上述方程得到dp(1,4)=18/5;

也可以通过MonteCarlo模拟试验来验证一下，结果证明是正确的，代码如下：

// MonteCarlo Simulation

double ExpectedSteps(){

const int MAX_TRY=100000000;

double expected=0;

int total=0;

int times=0;

int steps=0;

for(int i=0;i<MAX_TRY;i++){

times=0;

steps=1;

while(steps%4!=0){

if(rndJump(0.5))

steps+=1;

else

steps+=2;

times++;

}

total+=times;

}

expected=(double)total/MAX_TRY;

return expected;

}

编辑于 2015-08-25 09:55:44 回复(17)

SunburstRun

4, 概率题

f[i]: 目前在点i，期望再走多少步结束

f[0] = 0.5 f[1] + 0.5 f[2] + 1

f[1] = 0.5 f[2] + 0.5 f[3] + 1

f[2] = 0.5 f[3] + 1

f[3] = 0.5 f[1] + 1+0.5f[0]

解的f[0] =18/5;

编辑于 2015-08-25 09:55:27 回复(6)

c_memory

1->4的情况：

1->2->3->4 3步概率1/8；

1->2->4或1->3->4 2步概率1/4；

所以在4处停止的期望为：E0=3*1/8+2*2*1/4=11/8；

1->5的情况：

1->2->3->5 3步概率1/8；

1->3->5 2步概率1/4；

1->5的期望步数为：E1=3*1/8+2*1/4=7/8；

有1/8+1/4=3/8的情况到5，而5之后跟在1时的情况一样，故可列如下等式：

3/8*E+E1+E0=E 即 5/8*E=E0+E1=18/8

所以求得期望为：E=18/5

发表于 2016-06-29 17:07:45 回复(0)

希望ing

http://blog.csdn.net/u011680348/article/details/47973185

发表于 2015-08-28 18:17:30 回复(0)

董洪信

到4期望11/8，到5期望7/8，然后以5为起点，截留3/8概率继续进行。以此类推，所以期望＝18/8×（1＋5/8+5/8×5/8+....）＝18/5

发表于 2015-08-29 00:24:32 回复(3)

鸭嘴兽

@sunburstRun 的解析很明白了，我再写的详细一些

还是设f(i)表示在第i号格子上时，期望再走多少步结束。

则从1号开始走，我们的目标是求f(1)

f(1) = 0.5 * ( 1 + f(2) ) + 0.5 * ( 1 + f(3) ) 即有0.5概率走一步到2号，0.5概率走两步到3号

f(2) = 0.5 * ( 1 + f(3) ) + 0.5 * ( 1 + f(4) ) 即有0.5概率走一步到3号，0.5概率走两步到4号(结束)

f(3) = 0.5 * ( 1 + f(4) ) + 0.5 * ( 1 + f(1) ) 即有0.5概率走一步到4号，0.5概率走两步到5号(5号即可看做1号)

f(4) = 0 走到4号就结束了，故为0

可以解上述方程，得f(1) = 18/5.

发表于 2015-09-04 15:56:27 回复(11)

雪山飞狐hbc

这个问题，很显然考察的是递归问题：

定义step(i,j)为第i号格子带第j号格子的期望值；

step(1,4)为从第一格跳到第四格的期望，要到第四格，则只能先到第二格（期望0.5*（step(1,2)+1)）或者是第三格（期望0.5*（step(1,3)+1)）；其中1表示到达第2格或者第3个之后，跳到第4格还需要1步。

故有

step(1,4)=0.5*（step(1,2)+1)+0.5*（step(1,3)+1)=1+0.5*(step(1,2)+step(1,3))

同理有

step(1,3)=1+0.5*step(1,1)+0.5*step(1,2)

step(1,2)=1+0.5*step(1,1)+0.5*step(1,4)

step(1,1)=0

联立方程，得到

step(1,4)期望为18/5，选E。

发表于 2015-08-29 00:25:48 回复(1)

椎名深夏

图解法，每次记下格子除以4的余数。0则表示结束，1则表示从头开始一个新循环。

一共五条路径，三条到0，两条到1，分别算出每条路径的步数和对应概率，有递归方程

x=1/4*2+1/4*2+1/4*(x+2)+1/8*3+1/8*(x+3)

解之即得x=3.6

发表于 2018-06-18 16:19:57 回复(2)

给个offer糊口养家

想了一天，这些解析都直接列式子，根本无法理解，其实是这样，因为趋于无穷大，所以根据大数定律，f(1)的期望=f(5)的期望，因此才能列出大部分解析所列出的式子，即其实列出的式子是将f(5)换成了f(1)，从而求解出的

发表于 2018-07-05 14:33:38 回复(1)

米兰的小铁匠114

这道题的关键是：步数和格数不一样，要分开累计。

发表于 2016-08-04 11:50:12 回复(0)

氷_临

算出4.2直接陷入迷茫，根本没有答案，结果发现走两格算一步

编辑于 2024-03-22 15:27:00 回复(0)

牛客180732706号

只有我觉得这个题说的是把到四倍步数的概率全算出来然后再算期望吗？😂

发表于 2022-03-16 15:50:33 回复(0)

在泡澡的秋田犬很爱交友

利用python模拟

import random
n=100000

step = 0
for i in range(n):
    sum = 1
    while sum != 0:
        sum += random.randint(1,2)
        sum = sum%4
        step += 1
print(step/n)

发表于 2020-05-02 18:25:42 回复(0)

露小凤

设f(i)表示在第i号格子上时，期望再走多少步结束。

则f(1)=1/2*2+1/8*3+1/8*(3+f(1))+1/4*(2+f(1))

这是比较直接的方法主要是理解从1出发和从5出发是一样的，因为格子有无数个

发表于 2018-08-28 11:56:22 回复(0)

寒😊

四个位置1234，设f（i）是到第几个位置还需要多少步可以到4
一步可以是1，也可以是2，1、2是步长
则：
f(1)=0.5*(1+f(2))+0.5(1+f(3)) 此处加的1是一步的意思，两种情况，先一步到2，再看2到4多少步，或者先一步到3，再看3到4多少步
f(2)=0.5*(1+f(3))+0.5(1+f(4))
f(3)=0.5(1+f(4))+0.5(1+f(5)) f(5)相当于f(1)
f(4)=0
解方程即可

发表于 2018-08-10 13:58:38 回复(0)

MDP

Markov Chain, P= [[0, 0.5, 0.5, 0], [0, 0, 0.5, 0.5], [0.5, 0, 0, 0.5], [0, 0, 0,1]]

然后用Markov Chain的性质，计算(I-T)的inverse,取第一行就是答案，3.6

import numpy as np
a = np.array([[0,1/2, 1/2],
[0, 0, 1/2],
[1/2, 0, 0]])
b = np.array([[1,0,0],[0,1,0],[0,0,1]])
print(np.sum(np.linalg.inv(b-a),1)[0])

发表于 2018-03-11 11:32:17 回复(0)

♀琪寶、

跳1格跳2格都算1步。

E(Xi)表示在格子i上时，期望再走多少步结束：

在X1上，跳1格时走E(1+X2)步，跳2格时走E(1+X3)步，概率分别为0.5

E(X1)=0.5E(X1|Y=1)+0.5E(X1|Y=2)

=0.5E(1+X2)+0.5E(1+X3)

=1+0.5E(X2)+0.5E(X3)

以下同理：

E(X2)=0.5E(X2|Y=1)+0.5E(X2|Y=2)

=0.5E(1+X3)+0.5E(1+X4)

=1+0.5E(X3)+0.5E(X4)

E(X3)=0.5E(X3|Y=1)+0.5E(X3|Y=2)

=0.5E(1+X4)+0.5E(1+X1)

=1+0.5E(X1)+0.5E(X4)

E(X4)=0

得：

E(X3)=1+0.5E(X1)

E(X2)=3/2+1/4E(X1)

E(X1)=18/5