51NOD:1639-绑鞋带

传送门：https://www.51nod.com/onlineJudge/submitDetail.html#!judgeId=475129

1639 绑鞋带

基准时间限制：1 秒

空间限制：131072 KB

分值: 20 难度：3级算法题

Problem Description

有n根鞋带混在一起，现在重复n次以下操作：随机抽出两个鞋带头，把它们绑在一起。可以想象，这n次之后將不再有单独的鞋带头，n条鞋带系成了一些环。那么有多大概率刚好所有这些鞋带只形成了一个环？

Input

仅一行，包含一个整数n (2<=n<=1000)。

Output

输出一行，为刚好成环的概率。

Example

Input示例

2

Output示例

0.666667

解题心得：

其实就是一个很简单的递归问题，n个鞋带要形成环先要变成n-1根鞋带，一直递归到1根鞋带形成环，先预处理，每减少一根鞋带不形成环的概率，然后乘起来就行了。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e3+10;

double p[maxn];

int n;

void pre_deal(){

    for(int i=2;i<maxn;i++)

        p[i] = (double)((i*2-2)*i*2)/(double)(i*2*(i*2-1));

    p[1] = 1.0;

}

int main(){

    pre_deal();

    scanf("%d",&n);

    double ans = 1.0;

    for(int i=1;i<=n;i++)

        ans *= p[i];

    printf("%lf",ans);

    return 0;

}