Wrox Programmer Forums

Need to download code?

View our list of code downloads.

Register | FAQ | Members List | Calendar | Search | Today's Posts | Mark Forums Read
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 tens of thousands of software programmers and website developers including Wrox book authors and readers. As a guest, you can read any forum posting. By joining today you can post your own programming questions, respond to other developersí questions, and eliminate the ads that are displayed to guests. Registration is fast, simple and absolutely free .
DRM-free e-books 300x50
 
 
Thread Tools Display Modes
  #1 (permalink)  
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;
}


 


Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off
Trackbacks are Off
Pingbacks are On
Refbacks are Off

Similar Threads
Thread Thread Starter Forum Replies Last Post
TCP Communication block, maximum connections reach vin14976 Apache Tomcat 1 February 13th, 2007 03:35 PM
cant reach data in xml with namespaces TPP XSLT 3 March 25th, 2006 03:40 PM
cant reach data in xml with namespaces TPP XSLT 1 March 24th, 2006 10: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



All times are GMT -4. The time now is 08:36 PM.


Powered by vBulletin®
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
© 2013 John Wiley & Sons, Inc.