51nod 1639 递推

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1639

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),递推就好了。

 #include<bits/stdc++.h>

 using namespace std;

 #define LL long long

 #define inf 0x3f3f3f3f

 int main()

 {

     int N,i,j;

     double s=;

     cin>>N;

     for(i=;i<=N;++i)

         s=s*(*((double)i-)/((double)i*-));

     printf("%.6f\n",s);

     return ;

 }