[Tutor] new to prog. question

[Jeff Shannon]

alan.gauld@bt.com wrote:

>>I create a list containing numbers. list1=[1,2,4,8,16,32,64,128,512]
>>If I wanted to find if a given number, 12 for example, is
>>in the list would be easy. But, how about if x+y in the list equals
>>the number (12) ?
>>    
>>
>
>[...]
>Something like this:
>
>for A in list
>    for B in the remaining numbers
>       if X == A + B: return True
>else: return False
>

Alan's right -- there's no way to do this other than adding pairs of 
numbers and seeing if they match your target.  There's one optimization 
you *can* make, providing that your list is sorted.  In that case, as 
you march through your inner loop, you know that the value of B will 
only get bigger, so once A + B is greater than X, you know that none of 
the later values of B can possibly work.  At this point, you can skip 
the rest of the list and move on to the next value of A.  Similarly, 
once the value of A is greater than X, then (assuming no negative values 
for B) you know that there's nothing that can be added to A that'll sum 
to X.  In fact, since values of B will always be greater than A (because 
B is "the remaining numbers" in the list), if A + B[0] is greater than X 
then no further values of A or B can possibly equal X.

Jeff Shannon
Technician/Programmer
Credit International