http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1639
基准时间限制：1 秒 空间限制：131072 KB 分值: 20 难度：3级算法题
收藏 
关注 有n根鞋带混在一起，现在重复n次以下操作：随机抽出两个鞋带头，把它们绑在一起。可以想象，这n次之后將不再有单独的鞋带头，n条鞋带系成了一些环。那么有多大概率刚好所有这些鞋带只形成了一个环？
Input
仅一行，包含一个整数n (2<=n<=1000)。
Output
输出一行，为刚好成环的概率。
Input示例
2
Output示例
0.666667
我们领n条鞋带时的答案是f(n),则进行第一步时先随机选一个节点，第二个节点只能有(n-1)*2个可选，剩下的问题规模就转移到了f(n-1),递推就好了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 #define inf 0x3f3f3f3f 5 int main() 6 { 7 int N,i,j; 8 double s=1; 9 cin>>N; 10 for(i=2;i<=N;++i) 11 s=s*(2*((double)i-1)/((double)i*2-1)); 12 printf("%.6f\n",s); 13 return 0; 14 }