本文主要是介绍【51nod 1639】【概率与期望】绑鞋带,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
绑鞋带
- 题目
- 解题思路
- Code
51nod 1639 绑鞋带
题目
有n根鞋带混在一起,现在重复n次以下操作:随机抽出两个鞋带头,把它们绑在一起。可以想象,这n次之后將不再有单独的鞋带头,n条鞋带系成了一些环。那么有多大概率刚好所有这些鞋带只形成了一个环?
输入
仅一行,包含一个整数n (2<=n<=1000)。
输出
输出一行,为刚好成环的概率。
输入样例
2
输出样例
0.666667
解题思路
一根鞋带两个头,n个鞋带有 2n 个鞋带头
设当前已经打了 i 个结了,那么表示有 2i 个鞋带头绑在一起了
剩余 2n - 2i 个鞋带头
在剩余鞋带头中随便选定一个鞋带头,没有限制,那么剩余鞋带头有 2n - 2i - 1
最后变成一个环,那最后一个打结是 刚刚选出的鞋带头 和 这个鞋带头所在的集合 的 一个鞋带头 绑在一起
其实就是最后两个鞋带头绑在一个
但是,显而易见,在之前的打结中一定不能和自己的集合打结
同样显而易见,选中的鞋带头所在的集合 也只会有两个头,一个已选,另一个不能选
那么能选的就只有 2n - 2i - 2 个鞋带头
概率为 2 n − 2 i − 2 2 n − 2 i − 1 \frac{2n - 2i - 2}{2n - 2i - 1} 2n−2i−12n−2i−2,累乘即可
很快会发现这个公式实现上有问题,当 i = n - 1 时概率为0,所以不管怎么样最后概率都会变为0
当 i = n - 1 时只需要打最后一个结了,上面已经提到这种情况,最后只剩两个鞋头,如果保证前面一直是合法的,那么其实可以把问题转换为把鞋带绑成一条链。换言之,当前面都是合法时,绑最后一个结使鞋带变环是必然事件,概率为1
Code
#include <bits/stdc++.h>
#define ldb long doubleusing namespace std;int n;
ldb a, b, ans = 1.0;int main() {scanf("%d", &n);for(int i = 1; i < n; i ++) { // 记得去掉最后一个结a = 2 * n - 2 * (i - 1) - 2;b = 2 * n - 2 * (i - 1) - 1;ans = ans * a / b;}cout << ans;
}
这篇关于【51nod 1639】【概率与期望】绑鞋带的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!