In my booklet, Algorithms via C#, a way to make the computer guess the numbers more efficiently is presented (see pp. 12-13). Let’s quickly remind ourselves about the problem: we want to make the computer guess a number, between 0 to 100, with minimal amount of questions. It is concluded that we should start with 50, then 25, then 12, etc., that is, divide 100 by 2^k and depending on if the number is less than what computer guessed, we should either add or subtract this factor.
Everything is correct, but I would like to emphasize that this value can be computed without division.
⌊100/2^1⌋ = 50 = (110010)2
⌊100/2^2⌋ = 25 = (11001)2
⌊100/2^3⌋= 12 = (1100)2
⌊100/2^4⌋= 6 = (110)2
⌊100/2^5⌋= 3 = (11)2
⌊100/2^6⌋= 1 = (1)2
As you can see, in base 2, you simply remove the least significant bit each time. This might save time if you work in radix 2.
Leave a Reply