HDU5159--BC--Card(概率写法，和组合写法)

本文主要是介绍HDU5159--BC--Card(概率写法，和组合写法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

概率方法

要求出和的期望，期望的基本定理， 和的期望 = 各部分期望的和。

E(sum) = E(1) + E(2) + ... + E(x) ;

每个数在b次中只有选到和没选到两种情况，在b次中被选到的概率p =1 -  (1 - 1/x)^b ;

所以每个数的期望也是 i*( 1-(1-1/x)^b )

得到sum的期望。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
double e[110000] ;
double f(double x,int d)
{double ans = 1.0 ;if( d == 0 ) return 1.0 ;ans = f(x,d/2) ;ans *= ans ;if( d%2 )ans *= x ;return ans ;
}
int main()
{int t , tt , x, d , i ;scanf("%d", &t) ;for(tt = 1 ; tt <= t ; tt++){scanf("%d %d", &x, &d) ;for(i = 1 ; i <= x ; i++)e[i] = 1.0 - f(1.0-1.0/x,d) ;for(e[0] = 0 , i = 1 ; i <= x ; i++)e[0] += e[i]*i ;printf("Case #%d: %.3lf\n", tt, e[0]) ;}return 0;
}

组合方法

和的所有结果可能出现的和除以总的种类。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
double c[10] ;
int a[10][10] ;
int main()
{int t , tt , x , b , n , i , j ;double ans , k ;a[0][0] = 1 ;for(i = 1 ; i <= 5 ; i++){a[i][1] = 1 ;a[i][i] = a[i-1][i-1] * i ;}a[3][2] = 6 ;a[4][2] = 14 ; a[4][3] = 36 ;a[5][2] = 30 ; a[5][3] = 150 ; a[5][4] = 240 ;scanf("%d", &t) ;for(tt = 1 ; tt <= t ; tt++){ans = 0 ;scanf("%d %d", &x, &b) ;n = min(x,b) ;c[0] = 1 ;for(i = 1 ; i <= n-1 ; i++){for(j = 1 , k = 1 ; j <= i ; j++){k *= ((x-1)-j+1)*1.0/j ;}if( i >= 2 )c[i] = k/(x*1.0*x) ;elsec[i] = k ;}for(i = 1 ; i <= n ; i++){//printf("c -- %lf %lf\n", c[i-1], ((x+1)*1.0*x/2.0) * a[b][i]) ;k = c[i-1] * 1.0 * ((x+1)*1.0*x/2.0) * a[b][i] ;//printf("%lf\n", k) ;int m = b ;if( i >= 3 )m = b-2 ;for(j = 1 ; j <= m ; j++)k /= (x*1.0) ;//printf("%lf\n", k) ;ans += k ;}printf("Case #%d: %.3lf\n", tt, ans) ;}return 0;
}

这篇关于HDU5159--BC--Card(概率写法，和组合写法)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---