首页 > 代码库 > POJ 3071

POJ 3071

2024-08-02 10:24:16   219人阅读

求概率。其实跟枚举差不多，输入n即是要进行n轮比赛。对每一支球队，设求1的概率，首先1要与2比赛为p1，这是第一轮，第二轮时，1要与3（打败3为p2）,4（打败4为p3）中胜者比赛，由于是概率，则两者都要比，求出概率。所以，1要在第二轮胜的概率=p1*(p2*3第一轮胜出的概率+p3*4在第一轮胜出概率)。

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;double def[130][130];double p[8][130];int main(){	int n,ttp,bgn,ed,pos;	while(scanf("%d",&n)!=EOF){		if(n==-1) break;		for(int i=1;i<=(1<<n);i++)		for(int j=1;j<=(1<<n);j++)		scanf("%lf",&def[i][j]);		int tot=(1<<n);		for(int i=1;i<=tot;i++)		p[0][i]=1;		for(int i=1;i<=n;i++){			pos=1;			while(pos<=tot){				ttp=pos;				bgn=ttp+(1<<(i-1));				ed=bgn+(1<<(i-1))-1;				for(int k=ttp;k<ttp+(1<<(i-1));k++){					double sum=0;					for(int j=bgn;j<=ed;j++)					sum+=(p[i-1][j]*def[k][j]);					p[i][k]=sum*p[i-1][k];				}				ttp=pos+(1<<(i-1));				bgn=pos; ed=bgn+(1<<(i-1))-1;				for(int k=ttp;k<ttp+(1<<(i-1));k++){					double sum=0;					for(int j=bgn;j<=ed;j++)					sum+=(p[i-1][j]*def[k][j]);					p[i][k]=sum*p[i-1][k];				}				pos+=(1<<i);			}		}		int ans=1;		for(int i=1;i<=tot;i++)		if(p[n][i]>p[n][ans])		ans=i;		printf("%d\n",ans);	}	return 0;}

　　

POJ 3071


联系
我们