描述
题解
组合数学,找出递推式即可。
考虑n
根鞋带时的第一个操作,只要不选择同一根鞋带即可,变相等价于n-1
根时的情况。这样,我们可以递推求解。
假设已经有i-1
根鞋带组成一个环,用ans[i-1]
表示其概率,那么将第i
根鞋带插入前边的i-1
根鞋带的方案数为2*(i-1)
,这里乘以2是因为鞋带两头都可以插入,那么所有的情况(插成一环的情况+插成两环的情况)为2*(i-1)+1
,那么公式即为:
ans[i]=ans[i-1]2(i-1)/(2*(i-1)+1)
注意精度问题!!!
代码
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int n;
while(~scanf("%d", &n))
{
double ans = 1.0;
for (int i = 2; i <= n; i++)
{
ans = ans * (i - 1) * 2.0 / (2.0 * i - 1);
}
printf("%.8lf\n", ans);
}
return 0;
}