Wrox Programmer Forums
|
BOOK: Puzzles for Programmers and Pros BOOK ISBN: 978-0-470-12168-9
This is the forum to discuss the Wrox book Puzzles for Programmers and Pros by Dennis Shasha; ISBN: 9780470121689
Welcome to the p2p.wrox.com Forums.

You are currently viewing the BOOK: Puzzles for Programmers and Pros BOOK ISBN: 978-0-470-12168-9 section of the Wrox Programmer to Programmer discussions. This is a community of software programmers and website developers including Wrox book authors and readers. New member registration was closed in 2019. New posts were shut off and the site was archived into this static format as of October 1, 2020. If you require technical support for a Wrox book please contact http://hub.wiley.com
 
Old July 26th, 2010, 03:40 PM
Registered User
 
Join Date: Jul 2010
Posts: 1
Thanks: 0
Thanked 0 Times in 0 Posts
Default 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;
}







Similar Threads
Thread Thread Starter Forum Replies Last Post
TCP Communication block, maximum connections reach vin14976 Apache Tomcat 1 February 13th, 2007 04:35 PM
cant reach data in xml with namespaces TPP XSLT 3 March 25th, 2006 04:40 PM
cant reach data in xml with namespaces TPP XSLT 1 March 24th, 2006 11:47 AM
How to reach the second aspx page form the first? wufutureman BOOK: Beginning ASP.NET 1.0 0 July 21st, 2005 10:15 AM





Powered by vBulletin®
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.
Copyright (c) 2020 John Wiley & Sons, Inc.