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=1;
    cin>>N;
    for(i=2;i<=N;++i)
        s=s*(2*((double)i-1)/((double)i*2-1));
    printf("%.6f
",s);
    return 0;
}