A plate of n noodles. You want to connect 2 ends at a time. How many
cycles you can expect to make when you finish (i.e, do this for n times)
Pick one end, then there are 2n-1 ends in the plate
pick the 2nd end,
1. there is 1/2n-1 probability that these two ends will form a loop,
then there are n-1 noodles + 1 loop in the plate.
2, there is (2n-2)/(2n-1) probability the 2nd end is from a different noodle
In this case, we get a long noodle, and the problem is still a n-1
noodles
E[n]=(E[n-1]+1)/(2n-1) + E[n-1](2n-2)/(2n-1)
=E[n-1]+1/(2n-1)
阅读(1132) | 评论(0) | 转发(0) |
