N根面条两两打结成圈的数目
EMC笔试题目
碗里有n根面条，现在一次在碗中取任意两头（未必是同一根面条的）连在一起，直到没有面条的“头”剩下为止，问平均可以在碗里形成多少个圈？
回答列表
设n根面条得到的结果是f(n)，做一次“粘头”的操作其实可以分成两种情况：
1. 被粘的两头是同一根面条上的
这种情况的发生的概率是1/(2n-1)，此时平均圈数为1+f(n-1)
2. 被粘的两头是不同两根面条上的
这种情况的发生的概率是(2n-2)/(2n-1)，此时平均圈数为f(n-1)
于是有：
f(n)=1/(2n-1)*(1+f(n-1))+(2n-2)/(2n-1)*f(n-1)=1/(2n-1)+f(n-1)
而f(1)=1
于是f(n)=sum(1/(2*i-1), i=1..n)
1. 被粘的两头是同一根面条上的
这种情况的发生的概率是1/(2n-1)，此时平均圈数为1+f(n-1)
2. 被粘的两头是不同两根面条上的
这种情况的发生的概率是(2n-2)/(2n-1)，此时平均圈数为f(n-1)
于是有：
f(n)=1/(2n-1)*(1+f(n-1))+(2n-2)/(2n-1)*f(n-1)=1/(2n-1)+f(n-1)
而f(1)=1
于是f(n)=sum(1/(2*i-1), i=1..n)
三思网友QQ群：3535265