Reach for the Sky
The answer in the book (68%) can be bettered.
My programme produced 72.5%
The secret is to set only n1 at about 18/19 and then replace your holding up to 3 times. Don't skip to some n2, n3 as the best can fall in the skipped areas. Surprisingly, it is rare that a fourth higher number arises.
Here is some code if you want it. It runs 1000000 trials 10 times. Define TRIPLE if you want Prof. Shasha's result.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
//#define TRIPLE // switch on to use Prof Shasha's method.
int main (int argc, const char * argv[]) {
int success = 0;
int failure=0;
srandom(time(NULL));
for (int k=0; k<10; k++) {
for (int j=0; j<100000; j++) {
int grade=0;
int bmark = 0;
int i = 0;
int ohoh = 0;
int found = 0;
int n1 = 19; // best values are 18/19
#ifdef TRIPLE
int n2 = 32;
int n3 = 64;
#endif TRIPLE
// first p numbers .... set the benchmark
for ( int i=0; i<n1; i++) {
if ((grade=random() % 100000)>bmark) {
bmark = grade;
}
}
// first chance: select higher number
for ( ; i<100; i++) {
if ((grade=random() % 100000)>bmark) {
found = grade;
break;
}
}
#ifdef TRIPLE
// skip if i < n2
for ( ; i<n2; i++) {
if ((grade=random() % 100000)>found) {
ohoh = grade;
}
}
#endif TRIPLE
// second chance: select higher number
for ( ; i<100; i++) {
if ((grade=random() % 100000)>found) {
found = grade;
break;
}
}
#ifdef TRIPLE
// skip if i < n3
for ( ; i<n3; i++) {
if ((grade=random() % 100000)>found) {
ohoh = grade;
}
}
#endif TRIPLE
// third chance: select higher number
for ( ; i<100; i++) {
if ((grade=random() % 100000)>found) {
found = grade;
break;
}
}
// skip if i < 100
for ( ; i<100; i++) {
if ((grade=random() % 100000)>found) {
ohoh = grade;
break;
}
}
if ((ohoh>found)(found<=bmark)) {
failure++;
}
else {
success++;
}
}
printf("success rate: %5.4f\n", success / (float) (success + failure));
}
return 0;
}
