CSC111 Lab 13 Solution Program 2014
--D. Thiebaut (talk) 10:17, 2 May 2014 (EDT)
Solution Program
# solution programs for Lab13
#
#
from random import randrange
def fact( n ):
print( "fact function started. Received n =", n )
print( "testing if %d is >= 1" % (n) )
if n<=1:
print( "n == 1. Returning 1" )
return 1
print( "n > 1. Calling fact( %d )" % (n-1) )
y = fact( n-1 )
print( "setting y to %d" % y )
result = n * y
print( "returning result = %d * %d = %d" % (n, y, n*y) )
return result
def fact2( n, indent ):
print( indent, "fact2(%d) started" % n )
print( indent, "comparing %d to 1" % n )
if n<=1:
print( indent, "%d is <= 1. Returning 1" % 1 )
return 1
print( indent, "%d is not <= 1. Calling fact2(%d) and storing it in y" % (n, n-1) )
y = fact2( n-1, indent + " " )
print( indent, "just received %d from fact2( %d )." % ( y, n-1 ) )
result = n * y
print( indent, "multiplied %d by %d. It's %d. Returning %d to caller" % ( n, y, result, result ) )
return result
def sum1( n ):
if n==1:
return 1
return n + sum1( n-1 )
def evenSum1( n ):
if n <= 1:
return 0
if n%2 == 0:
return n + evenSum1( n-2 )
if n%2 == 1:
return evenSum1( n-1 )
def recurseMax( L ):
N = len( L )
if N==1:
return L[0]
return max( L[0], recurseMax( L[1:] ) )
def divideConquerLargest( L ):
N = len( L )
if N==1:
return L[0]
return max( divideConquerLargest( L[0:N//2] ),
divideConquerLargest( L[N//2: ] ) )
def divideConquerMin( L ):
N = len( L )
if N==1:
return L[0]
return min( divideConquerMin( L[0:N//2] ),
divideConquerMin( L[N//2: ] ) )
def divideConquerSum( L ):
N = len( L )
if N==1:
return L[0]
return divideConquerSum( L[0:N//2] ) + divideConquerSum( L[N//2: ] )
def divideConquerAbs( L ):
N = len( L )
if N==1:
L[0] = abs( L[0] )
return L
return divideConquerAbs( L[0:N//2] ) + divideConquerAbs( L[N//2: ] )
#------------------------------------------------------------------
def createArray( n ):
"""Creates a list of n random numbers in sorted order"""
A= []
for i in range( n ):
A.append( randrange( n * 10 ) )
A.sort()
return A
#------------------------------------------------------------------
def binsearch( A, low, high, key ):
"""a recursive function that searches the list A to see if
it contains the item key between the indexes "low" and "high".
returns the index where the key was found, or -1 otherwise
"""
print( "low=%10d high=%10d key=%10d" % (low, high, key) )
if low>high:
return -1
mid = ( low + high )//2
if A[mid]==key:
return mid
if key < A[mid]:
return binsearch( A, low, mid-1, key )
else:
return binsearch( A, mid+1, high, key )
def main():
# fact
"""
n = int( input( "Enter a positive number: " ) )
x = fact( n )
print( "the factorial of %d is %d." % ( n , x ) )
"""
# fact2
"""
n = int( input( "Enter a positive number: " ) )
x = fact2( n, " " )
print( "the factorial of %d is %d." % ( n , x ) )
"""
# sum1
"""
n = int( input( "Enter a positive number: " ) )
print( "sum of all numbers from 1 to %d = %d" % (n, sum1(n) ) )
"""
# evenSum1
"""
for n in range( 12 ):
print( " n = %d sumEven(%d) returns %d" % (n, n, evenSum1(n) ) )
"""
# recursive max
"""
L = [1, 2, 3, 0, 10, 20, 30, 3, -3, 5, 1, 100, 1]
print( "recurseMax( %s ) = %d" % ( L, recurseMax( L ) ) )
"""
# divideConquerLargest
"""
L = [1, 2, 3, 0, 10, 20, 30, 3, -3, 5, 1, 100, 1]
print( "divideConquerLargest( %s ) = %d" % (L, divideConquerLargest(L ) ) )
"""
# divideConquerMin
"""
L = [1, 2, 3, 0, 10, 20, 30, 3, -3, 5, 1, 100, 1]
print( "divideConquerMin( %s ) = %d" % (L, divideConquerMin(L ) ) )
"""
# divideConquerSum
"""
L = [1, 2, 3, 10, 101, 100, 100]
print( "divideConquerSum( %s ) = %d" % (L, divideConquerSum(L ) ) )
"""
# divideConquerAbs
"""
L = [1, 2, 3, -10, -101, 100, 100]
print( "divideConquerAbs( %s ) = %s" % (L, divideConquerAbs(L ) ) )
"""
# binSearch
#A = createArray( 20 )
#print( "A = ", A )
A = createArray( 1000000 )
print( A[100:110] )
while True:
print
key = int( input( "search for what number? " ) )
if key==-1: break
index = binsearch( A, 0, len( A )-1, key )
if index != -1:
print( "found %d at index %d" % ( key, index ) )
else:
print( "%d not in A" % key )
main()