Guess the number
The computer thinks a number x from 1 to N and the human tries to guess it.
That random number x in the range from 1 to n is generated by the function draw_lots(n). We keep guessing that number as long as the condition guess != x is true. In our program we assign 100 to N.
The question is how many iteration do we need to guess the nunber x.
#Guss the number
import random
N = 100
counter = 0 #counts number of guesses
def draw_lots(n):
r = int(n*random.random()) + 1
return r
a = 1 # left edge of range
b = N # right edge of range
x = draw_lots(N) # computer draws a random numbenr
print("C: I thought a number. Guess it!\n")
guess = 0 # initianate our gues with 0 to enter the loop
while (guess != x):
guess = int(input("C: put a number from " + str(a) + " to " + str(b) +": " ))
counter += 1
if(guess < x):
print("C: too small")
a = guess
elif(guess > x):
print ("C: two big")
b = guess
else:
print ("C: you guessed my number. It was " + str(x))
print("\nC: you needed " + str(counter) + " moves.")
We need around $\log_{2}N$ moves to guess the computer number, so in our case it is $\log_{2}100$. It is around 7 times.
In python we can calculate it like this:
import math
value = math.log(100, 2)
print(value)
It gives us 6.643856189774725. The question is: why 7 moves (in this case) is enough or in general $\log_{2}N$ is enough to guess the number, where N is the original right edge.