mw 发帖数: 525 | 1 ant sitting on one corner of a cube and can walk on edges of the cube. it
takes one unit of time to go from one corner to a neighboring corner. it
may go in any direction randomly each time. what is the expected time that
the ant reaches the opposite corner?
到现在还是no clue,怎么办咧? |
l*****8 发帖数: 16 | 2 菜鸟尝试解答:
设出发点是Z0
距离出发点一步的3个顶点是z1
距离终点一步的3个顶点是z2
终点是z3
可以认为3个z1和3个z2是一样的。
从z0出发,一定到达任何一个z1
z1有2/3机会到达z2,1/3回到z0
z2有1/3机会到达z3,2/3回到z1
所以从z1出发,2/9机会到达终点,7/9的浪费两步
E(X)=xp(x)=2/9*3+2/9*(7/9)*5+2/9*(7/9)^2*7+...+2/9*(7/9)^n*(2n+3)=10
it
it
that
【在 mw 的大作中提到】 : ant sitting on one corner of a cube and can walk on edges of the cube. it : takes one unit of time to go from one corner to a neighboring corner. it : may go in any direction randomly each time. what is the expected time that : the ant reaches the opposite corner? : 到现在还是no clue,怎么办咧?
|
x**y 发帖数: 10012 | 3 恩
markov chain 解法。。。
【在 l*****8 的大作中提到】 : 菜鸟尝试解答: : 设出发点是Z0 : 距离出发点一步的3个顶点是z1 : 距离终点一步的3个顶点是z2 : 终点是z3 : 可以认为3个z1和3个z2是一样的。 : 从z0出发,一定到达任何一个z1 : z1有2/3机会到达z2,1/3回到z0 : z2有1/3机会到达z3,2/3回到z1 : 所以从z1出发,2/9机会到达终点,7/9的浪费两步
|
B*********h 发帖数: 800 | 4 恩。是这样的。
我当时就先解了square版本(2D),问人家还要接着解cube么,他挥了挥手说不用了。
【在 x**y 的大作中提到】 : 恩 : markov chain 解法。。。
|
x**y 发帖数: 10012 | 5 就怕那种不懂解法什么意思的
那张答案纸等着你解答的了
【在 B*********h 的大作中提到】 : 恩。是这样的。 : 我当时就先解了square版本(2D),问人家还要接着解cube么,他挥了挥手说不用了。
|
B*********h 发帖数: 800 | 6 恩,还好。我碰到的哪种是拿着一整张问题挑着问的。看那张纸上一堆趣味图形,我就
知道一个小时后脑子要爆炸了。
【在 x**y 的大作中提到】 : 就怕那种不懂解法什么意思的 : 那张答案纸等着你解答的了
|
r*******y 发帖数: 290 | 7 z0 = 1 + z1;
z1 = 1/3z0 + 2/3z2 + 1;
z2 = 2/3z1 + 1;
solve the equations, get z0 = 10
this is essentially markov chain solution with transition matrix
z0 z1 z2 z3
z0 0 1 0 0
z1 1/3 0 2/3 0
z2 0 2/3 0 1/3
z3 0 0 0 1
z(i) = sum(p(i,j) * zj) + 1
【在 l*****8 的大作中提到】 : 菜鸟尝试解答: : 设出发点是Z0 : 距离出发点一步的3个顶点是z1 : 距离终点一步的3个顶点是z2 : 终点是z3 : 可以认为3个z1和3个z2是一样的。 : 从z0出发,一定到达任何一个z1 : z1有2/3机会到达z2,1/3回到z0 : z2有1/3机会到达z3,2/3回到z1 : 所以从z1出发,2/9机会到达终点,7/9的浪费两步
|
s***e 发帖数: 267 | 8 你是说interviewer自己不懂题目怎么解答吗?这样也行?
【在 x**y 的大作中提到】 : 就怕那种不懂解法什么意思的 : 那张答案纸等着你解答的了
|