51NOD 1639 绑鞋带 【水】

1639 绑鞋带 基准时间限制：1 秒 空间限制：131072 KB 分值: 20 难度：3级算法题 收藏 关注 有n根鞋带混在一起，现在重复n次以下操作：随机抽出两个鞋带头，把它们绑在一起。可以想象，这n次之后將不再有单独的鞋带头，n条鞋带系成了一些环。那么有多大概率刚好所有这些鞋带只形成了一个环？ Input 仅一行，包含一个整数n (2<=n<=1000)。 Output 输出一行，为刚好成环的概率。 Input示例 2 Output示例 0.666667 mostleg (题目提供者)

k[i]=i根鞋带 刚好系成一个环的概率

k[i]:考虑第i根鞋带的一头 可以系到第i根的另一头 和 其余i-1条的2头 显然 只有系到另外i-1条才可能成一个环 所以k[i] = k[i-1] * ( 2*(i-1) ) / ( 2*(i-1)+1 ) 递推下去就可以了 #include<iostream> #include<stdlib.h> #include<stdio.h> #include<string> #include<vector> #include<deque> #include<queue> #include<algorithm> #include<set> #include<map> #include<stack> #include<time.h> #include<math.h> #include<list> #include<cstring> #include<fstream> #include<queue> #include<sstream> //#include<memory.h> using namespace std; #define ll long long #define ull unsigned long long #define pii pair<int,int> #define INF 1000000007 #define pll pair<ll,ll> #define pid pair<int,double> int main() { //freopen("/home/lu/Documents/r.txt","r",stdin); //freopen("/home/lu/Documents/w.txt","w",stdout); int n; scanf("%d",&n); double ans =1; for(int i=2;i<=n;++i){ int k = 2*(i-1); ans = ans*k/(k+1); } printf("%f\n",ans); return 0; }