steve at holdenweb.com
Thu Nov 10 18:31:18 CET 2005
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!
>> # 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'):
>> ans = raw_input("Too high? y/n ")
>> if ans in ("y", "yes"):
>> hi = guess-1
>> 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 -
> Comments please.
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
Hope this helps.
Steve Holden +44 150 684 7255 +1 800 494 3119
Holden Web LLC www.holdenweb.com
PyCon TX 2006 www.python.org/pycon/
More information about the Python-list