/*** Guess a Secret Number ************************************* Luke is making a game for his little sister, to keep her busy. The program chooses a number between 1 and 500, and the user must try to guess the number. They are permitted to guess 10 times. ****************************************************************/ void setup() { int secret = (int)random(500)+1; for(int c = 1; c <= 10; c=c+1) { int guess = int( input("Your guess?") ); if(guess < secret) { output("too small"); } if(guess > secret) { output("too big"); } if(guess == secret) { output("RIGHT! That took " + c + " guesses."); System.exit(0); } } } public String input(String prompt) { return javax.swing.JOptionPane.showInputDialog(null,prompt); } public void output(String message) { javax.swing.JOptionPane.showMessageDialog(null,message); } |
It seems like 10 guesses would not be enough to guess a number chosen from
500 choices. But the divide-and-conquer
strategy, it is possible to win this game every time. You must guess
250 as the first guess. Then the program tells you
whether the secret number is higher or lower. This cuts the number
of possibilities in half. Then you need to guess the
middle number of the ones that are
left. At every guess, it cuts the number of remaining possibilities
in half, like this:
500
250
125
63
32
16
8
4
2
1
We see this takes 10 steps, so 10 guesses should be enough if we use the
divide-and-conquer strategy.
If we program and algorithm that
cutsthe problem in half over and over again, it is much faster than an exhaustive algorithm
that simply counts through all the possibilities. If we can divide
the problem in half over and over again, then the number
of steps is not N (the number of items), but rather log2N
, where log2N is
defined as "the number of times you must
divide a number by 2 until the result is 1 or smaller.
A typical example of divide-and-conquer as a binary
search, which is exactly what we are doing when we try
to guess the number by guessing in the middle each time.