Problem
有n根鞋带混在一起,现在重复n次以下操作:随机抽出两个鞋带头,把它们绑在一起。可以想象,这n次之后將不再有单独的鞋带头,n条鞋带系成了一些环。那么有多大概率刚好所有这些鞋带只形成了一个环?
Solution
f(n)可以转化为f(n-1)。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
| #include<stdio.h> #include<algorithm> #include<map> #include<queue> #include<vector> #include<string.h> #include<stack>
#define mem(ss) memset(ss,0,sizeof(ss)) #define fo(d, s, t) for(int d=s;d<=t;d++) #define fo0(d, s, t) for(int d=s;d>=t;d--) typedef long long ll; typedef long double ld; typedef double db; const ll mod = 998244353; #define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
db fab(db x) { return x > 0 ? x : -x; } int n; double a[1020]={0,1}; int main() { scanf("%d",&n); for(int i=2;i<=n;i++){ a[i]=a[i-1]*(2*i-2)/(2*i-1); } printf("%.6f\n",a[n]); return 0; }
|