Newb ??

[Alex Martelli]

Norman Silverstone <norman at littletank.org> wrote:
   ...
> challenging. What I am thinking about at the moment is how to program for
> the computer to guess the number which I select. I know it can be done but
> I suspect it requires an approach which I have not yet learnt. I would
> welcome suggestions on the best way to approach this problem.

I assume the way the computer is going to guess is by trying some
number, and you respond either that it's guessed right, or to go lower,
or to go higher.

In that case, think of "bisection".  Originally, all the computer knows
is that the number is in some range, say 0 to 100.  It can then guess
the midpoint, 50.  If it's right, yay!  Otherwise: if it's told to go
lower, then the range is now 0 to 49 -- if higher, it's 51 to 100; in
each case the range was just halved (actually, a bit more than halved).

It does not take many halvings to squeeze even a pretty large original
range down to a range which only includes one possible number... that's
because "2 to the power of N" grows VERY fast with N, as the old story
about the inventor of chess shows (the king told him to ask for a
reward, and all he wanted was some rice -- one grain on the first cell
of the chessboard, two on the next, then four, eight... all the way
through the 64 squares of the board; the kind thought the inventor was
being very moderate in his request, and granted it... to soon find out
that not enough rice existed in the world to satisfy the request...;-).

Well, repeated halving is just like repeated doubling "backwards", so it
squeezes vast ranges of possibilities down to tiny ones just as fast as
repeated doubling produces oceans of rice from a small chessboard;-).


Alex