51Nod－1639－绑鞋带

ACM模版

描述

题解

组合数学，找出递推式即可。 考虑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; }