"Searching Algorithms / Binary Trees" for QB Express #24
Written by Dean Menezes
Let's say you have a guess the number program where
the computer tries to find the human's number
(pseudo-code):
FOR i = 1 TO 31
ask the user if their number is i
if their number is i,
print "I got it in"; i; "guesses";
end
end if
NEXT
Clearly, if the user's number is N, the program will
take N guesses to arrive at this result (max of 31
guesses).
See if you can make a more efficient algorithm.
16
8 24
4 12 20 28
/ \ / \ / \ / \
2 6 10 14 18 22 26 30
/\ /\ /\ /\ /\ /\ /\ /\
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31
More efficient algorithm using binary tree:
1. Start at the top of the binary tree
2. Ask the user if their number is (current number)
3. If their number is the current number then stop
4. Else, ask them if their number is higher or lower
than the current number
5. If higher, go right on the tree. If lower, go left
on the tree.
6. Go to step 2
This will need a maximum of 5 guesses, making it much
more efficent than the first method.
Here is an implementation of QBASIC:
DECLARE SUB logic (low!, high!, numturns!)
CLS
PRINT "Think of an integer x such that 1 "; CHR$(243);
" x "; CHR$(243); " 31"
PRINT "Press any key when ready."
WHILE INKEY$ = ""
'Dummy press any key routine
WEND
CALL logic(1, 31, 0)
SUB logic (low, high, numturns)
num = (low + high) / 2
DO
PRINT "Is your number"; num
INPUT answer$
IF UCASE$(LEFT$(answer$, 1)) = "Y" THEN PRINT "I
got it in"; numturns; "turns": EXIT SUB
IF UCASE$(LEFT$(answer$, 1)) = "N" THEN EXIT DO
PRINT "Please answer the question."
LOOP
DO
PRINT "Is your number higher or lower than"; num
INPUT answer$
IF UCASE$(LEFT$(answer$, 1)) = "H" THEN CALL
logic(num + 1, high, numturns + 1): EXIT SUB
IF UCASE$(LEFT$(answer$, 1)) = "L" THEN CALL
logic(low, num - 1, numturns + 1): EXIT SUB
PRINT "Please answer the question."
LOOP
END SUB
Here is another example of where a binary tree could
make a program more efficient.
INPUT "num? ", num
INPUT "accuracy? ", acc
FOR i = 0 TO num STEP acc
IF i * i >= num THEN PRINT i: END
NEXT
This is a program to find the square root of a number
to a certain accuracy. It does this by increminting a
variable until the varialbe squared is greater than
the number.
Can you write a faster version of this program?
Here is the fast version:
INPUT "num? ", num
INPUT "accuracy? ", acc
g1 = 1
DO
g2 = num / g1
IF ABS(g2 - g1) < acc THEN PRINT "val is between";
g1; "and"; g2: END
g1 = (g1 + g2) / 2
LOOP
Here's how the fast program works:
1. it starts out with this range:
0 ......... n
2. then is gets an initial guess (always picks 1 in
example). the range is now
g0 .... 1/g0
3. then it picks the average of the two bounds as the
new guess
g1 .. 1/g1
4. it repeats step 3 until the range is within the
desired accuracy (small range = more accurate).