51NOD:1639-绑鞋带
2024-10-04 03:42:31
传送门:https://www.51nod.com/onlineJudge/submitDetail.html#!judgeId=475129
1639 绑鞋带
基准时间限制:1 秒
空间限制:131072 KB
分值: 20 难度:3级算法题
Problem Description
有n根鞋带混在一起,现在重复n次以下操作:随机抽出两个鞋带头,把它们绑在一起。可以想象,这n次之后將不再有单独的鞋带头,n条鞋带系成了一些环。那么有多大概率刚好所有这些鞋带只形成了一个环?
Input
仅一行,包含一个整数n (2<=n<=1000)。
Output
输出一行,为刚好成环的概率。
Example
Input示例
2
Output示例
0.666667
解题心得:
- 其实就是一个很简单的递归问题,n个鞋带要形成环先要变成n-1根鞋带,一直递归到1根鞋带形成环,先预处理,每减少一根鞋带不形成环的概率,然后乘起来就行了。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
double p[maxn];
int n;
void pre_deal(){
for(int i=2;i<maxn;i++)
p[i] = (double)((i*2-2)*i*2)/(double)(i*2*(i*2-1));
p[1] = 1.0;
}
int main(){
pre_deal();
scanf("%d",&n);
double ans = 1.0;
for(int i=1;i<=n;i++)
ans *= p[i];
printf("%lf",ans);
return 0;
}
最新文章
- Ubuntu 14.04 下安装wiznote客户端
- 【转】js 关键字 in 的使用方法
- 打造自己的视频会议系统 GGMeeting(附送源码)
- 6. Configure Compute services
- [HTML]JS添加表格
- HashMap原理详解
- 工作一直没有进步怎么办?试试PDCA法则吧!
- 【转】android 电容屏(三):驱动调试之驱动程序分析篇
- c语言,string库函数itoa实现:将int转换为char*
- python 学习 [day8]class成员
- Lumen框架-错误&;日志
- Django 2.0.4 微博第三方登录
- date(&#39;Y-m-d H:i:s&#39;,time()) 与 date(&#39;Y-m-d h:i:s&#39;,time())区别是什么
- bzoj1026: [SCOI2009]windy数(数位dp)
- openstack时间不同步问题
- 如何在安装node\npm\cnpm
- VS Code编辑器对git项目的支持
- NLayerAppV3-Distributed Service Layer(分布式服务层)
- AES 加密填充 PKCS #7
- P4027 [NOI2007]货币兑换