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()