Euler Projesi 286. Soru

Puanlama Olasılıkları

Barbara bir matematikçi ve bir basketbol oyuncusu. x mesafesinden atış yaparken skor yapma olasılığının tam olarak (1 - x / q) olduğunu bulmuştur; burada q, 50'den büyük bir reel sabittir.

Her antrenman turu sırasında x = 1, x = 2, ..., x = 50 mesafelerinden atış yapıyor ve kayıtlarına göre toplamda tam olarak 20 skorunu yapmak için tam olarak %2 şansı var.

q'yu bulun ve cevabınızı 10 ondalık basamağa yuvarlayarak verin.

Cevap: 52,6494571953

Python: def probability(x,needed,q,d={}): try: return d[x,needed,q] except: pass if x<=0: if needed==0: return 1.0 else: return 0.0 p1 = probability(x-1,needed-1,q) d[x-1,needed-1,q]=p1 p1 *= (1.0-1.0*x/q) p2 = probability(x-1,needed,q) d[x-1,needed,q]=p2 p2 *= 1.0*x/q d[x,needed,q]=p1+p2 return p1+p2 def problem286(): qmin = 52.0 qmax = 53.0 loops = 0 while loops<100: loops+=1 m = (qmin+qmax)/2.0 p = probability(50,20,m) if p>=0.02: qmin, qmax = m, qmax else: qmin, qmax = qmin, m print qmin,qmax,p c/c++: double probThat20WereMade( double q ) { double p[51][51] = { 1 }; // [x][y] = given x shots (1,2,..,x), probability that y were made for ( int x = 1; x <= 50; x++ ) for ( int numMade = 0; numMade <= x ; numMade++ ) p[x][numMade] = (numMade>0?p[x-1][numMade-1]*(1-x/q):0) + p[x-1][numMade]*(x/q); return p[50][20]; } void main() { double lo = 50; double hi = 60; while ( hi - lo > 1e-13 ) { double mid = (lo+hi)/2; double prob = probThat20WereMade( mid ); if ( prob > .02 ) lo = mid; else hi = mid; } cout.precision( 13 ); cout << lo << endl; } Haskell: #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> using namespace std; const int MaxN = 51 ; const double eps = 1e-12; double dp[MaxN][MaxN]; int sign( double x ){ if( fabs(x) < 1e-13 ) return 0 ; return x>0.0?1:-1; } double doDp ( double p ){ memset(dp,0,sizeof(dp)); dp[0][0] =1 ; double tmp ; for( int i=1 ;i <=50 ; i ++ ){ tmp = i/p ; for( int j=0 ; j <=i ; j ++ ){ if( j > 0 ) dp[i][j] = dp[i-1][j-1]*(1.0-tmp)+ dp[i-1][j]*tmp; else dp[i][j] =dp[i-1][0]*tmp; } } return dp[50][20]; } int main ( ){ double tmp , l = 50.0 , r = 100.0 , mid ; while ( fabs(r- l) > eps ){ mid = ( l+ r ) * 0.5 ; tmp = doDp( mid ) ; if( sign( tmp-0.02) < 0 ) r = mid ; else l = mid ; } printf("%0.10lf\n",(l+r)*0.5); }