概率方法
要求出和的期望,期望的基本定理, 和的期望 = 各部分期望的和。
E(sum) = E(1) + E(2) + ... + E(x) ;
每個數在b次中只有選到和沒選到兩種情況,在b次中被選到的概率p =1 - (1 - 1/x)^b ;
所以每個數的期望也是 i*( 1-(1-1/x)^b )
得到sum的期望。
#include#include #include 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#include #include 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) ; else c[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; }