/* You draw M cards from a deck of N numbered 1 .. N.
After each card, you can choose to stop on your card, or continue
playing. If you stop, you draw the remaining cards and see if
the card you stopped on is the highest of all cards drawn.
What are your chances with optimal strategy of stopping on the highest
card that you will draw?
Compute from the end back. Call the probability to win, when there
are m cards left to draw and the highest card drawn so far was t,
P_m(t). Then
P_1(t) = (N-t) / ( N + 1 - M )
P_m(t) = (1/(N+m-M)) sum{i=t+1..N} max( P_{m-1}(i) ,
Prod{j=1..m-1} (i+j-M)/(N+j-M) )
+ ((t+m-M)/(N+m-M)) P_{m-1}(t)
Here P_1(t) is just the chance that the last card will be higher
than the highest card so far. The last term in P_m(t) is the chance
that the card drawn is lower than t, in which case I do not hold and
I continue to the next card. The summation is over cases where the
card drawn is higher than t; the "max" function says, don't stop if the
first term is higher, do stop if the second term, representing the
chance that you won't draw a higher card in the remaining (m-1) tries,
is higher.
The final chance of winning is P_M(0).
*/
#include
#include
/* #define HECTORS_WAY */
int main ()
{
long N , M , m , t , i , j , k , l;
double *P , *P_old , *jprod;
printf ( "Enter the number of cards N.\n" );
scanf ( "%ld" , &N );
P = (double *) malloc ( (N+1) * sizeof ( double ) );
P_old = (double *) malloc ( (N+1) * sizeof ( double ) );
jprod = (double *) malloc ( (N+1) * sizeof ( double ) );
printf ( "Enter the number of cards drawn, M.\n" );
scanf ( "%ld" , &M );
for ( t = 0 ; t <= N ; t++ ) /* cases t<(M-1) don't make sense */
{ /* Establish chances to win on last card */
P[t] = ( N-t ) / ( (double) ( N + 1 - M ) );
jprod[t] = 1;
}
/* Those are P_1[t] */
for ( m = 2 ; m <= M ; m++ ) { /* Loop over cards left to pick */
for ( l = 0 ; l <= N ; l++ ) {
P_old[l] = P[l]; /* P_old = P(m-1,t) */
jprod[l] *= ( l + (m-1) - M ) / ( (double) ( N + (m-1) - M ) );
}
for ( t = M-m ; t <= N ; t++ ) { /* Loop over t */
P[t] = ( t+m-M ) * P_old[t]; /* cases where card is lower than t */
for ( i = t+1 ; i <= N ; i++ ) { /* Possible higher cards you can draw */
#ifdef HECTORS_WAY
if ( jprod[i] > 0.5 )
#else
if ( jprod[i] > P_old[i] ) /* Then we should stick with this card */
#endif
P[t] += jprod[i];
else
P[t] += P_old[i]; /* Don't stick with this card */
}
P[t] /= ( double) ( N + m - M ); /* P(m,t) evaluated */
} /* End loop over t */
} /* End loop over m, up to M. */
printf ( "Your final chances are %.9lf\n" , P[0] );
}