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 的大作中提到】
: 就怕那种不懂解法什么意思的
: 那张答案纸等着你解答的了
|
