| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
贴代码……只是加了点注释In Reply To:我表示很蛋疼 Posted by:lisency at 2012-04-28 20:49:12 #include<cstdio>
#include<cmath>
int C[21][21];
void init()
{
for (int i=0;i<21;i++)
C[i][i]=C[i][0]=1;
for (int i=2;i<21;i++)
{
for (int j=1;j<i;j++)
{
C[i][j]=C[i-1][j]+C[i-1][j-1];//杨辉三角形
}
}
}
int main()
{
double dp[21],_dp[21],p;//dp[i] i个点联通的概率,_dp[i]不连通的概率
//p 是两点有边联通的概率
int n,i,j;
init();
while(~scanf("%d%lf",&n,&p))
{
for (i=1;i<=n;i++)
{
_dp[i]=0;
for(j=1;j<i;j++)
{
_dp[i]+=C[i-1][j-1]*dp[j]*pow(1-p,j*(i-j));
//C(i-1,j-1) 其实是 C(i-1,i-j) ,是 i - j 个点不连通有多少种情况
//dp[j]是 j 个点联通的概率
//(1 - p)^ j 不连通的点跟 j 个联通的点不相连的概率
//((1-p)^j)^(i-j) 因为有i-j个不连通的点要同时成立
}
dp[i]=1-_dp[i];
}
printf("%.8lf\n",dp[n]);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator