Algorithms Tutorial

Guess the Number

Remember the "Guess the Number" game? Play it with the computer to guess a number from 1 to 100. Can you figure out an algorithm that will let you guess the right number with the fewest guesses? How many guesses do you need to make in the worst-cast scenario?

import random def guess_a_number(): number = random.randint(1, 100) guess = int(input("I am thinking of a number between 1 and 100. Enter your guess.")) tries = 1 while guess != number: if guess > number: guess = int(input("Your number is too high. Guess again.")) if guess < number: guess = int(input("Your number is too low. Guess again.")) tries = tries + 1 print "The number is", guess, "! You guessed it in", tries, "tries." return "You guessed the number in " + str(tries) + " tries!" msg = guess_a_number() again = input(msg + " Play again? (y/n)") while again == "y": msg = guess_a_number() again = input(msg + " Play again? (y/n)")

If you guess in accending order starting from number 1, your worst case is 100 guesses when the computer is thinking of 100. If you guess in decending order starting from number 100, you can get it in one try if the number is 100. However, what if the computer is thinking of number 1 this time? How many tries do you need?

You have probably figured out a better solution. If you guess the number right in the middle of the number range each time, you can eliminate half of the numbers. In this way you are guaranteed to guess the correct number in at most seven times.

1 of 8