Newb ??

[Steve Holden]

Norman Silverstone wrote:
> On Fri, 11 Nov 2005 01:39:40 +1100, Steven D'Aprano wrote:
> 
> 
>>On Thu, 10 Nov 2005 13:30:05 +0000, Norman Silverstone wrote:
>>
>>
>>>>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).
>>>
>>>Thank you, I thought that might be the case. So, I will have to settle
>>>down and try to write some pseudo-code first. I hope to be back.
>>
>>Heh, you will find that Python is practically executable pseudo-code!
>>
>>Untested:
>>
>>
>>def guess_number():
>>    # please don't cheat the poor computer...
>>    print "Guess a number."
>>    lo = 0
>>    hi = 100
>>    while True:
>>        guess = (lo+hi)//2
>>        ans = raw_input("Is it %d? y/n " % guess)
>>        if ans in ('y', 'yes'):
>>            break
>>        ans = raw_input("Too high? y/n ")
>>        if ans in ("y", "yes"):
>>            hi = guess-1
>>        else:
>>            lo = guess+1
>>
>>This should run, and it will *almost* do what you want.
> 
> 
> Thanks for that but I think it is too simplistic. It appears OK for the
> first guess, which is 50 but, what about the next guess. If the guess is
> too high then the next guess has to be 50/2. However, if it is too low
> then the next guess must be first guess + (100-second guess)/2. In general
> terms, if guess is too high then next guess must (guess - lowest
> possible)/2 and if too  low then it is guess + (highest possible -
> guess)/2. 
> 
> Comments please.
> 
> Norman
> 
Effectively you want to start with a minposs and maxposs, which are set 
to 0 and 100 respectively. Your guess should bisect the range (as nearly 
as it can given that you are dealing with integers, and you have to be 
careful to get the awkward boundary conditions right). So your first 
guess will be 50. If your guess is too low then replace minposs with 
your guess (in this case 50); if too high, replace maxposs with your 
guess; loop to generate the next guess, and so on. In practice since 
log2(100) > 5 your five guesses won't always be enough (though seven 
should be).

Hope this helps.

regards
  Steve
-- 
Steve Holden       +44 150 684 7255  +1 800 494 3119
Holden Web LLC                     www.holdenweb.com
PyCon TX 2006                  www.python.org/pycon/