The copy of lab 11

 

The copy of lab 11:

import numpy as np
import time
#import matplotlib.pyplot to enble plotting histogram
import matplotlib.pyplot as plt

def getRandomInts(min, maxPlusOne, numInts):
   """Assumes the following:
       min is an int which specifies the smallest random int to generate
       maxPlusOne is an int which specifies one more than largest random int to generate
       numInts is an int which specifies how many random ints to generate
       Returns the list of random ints
   """
   
   #start with empty list of random ints
   randInts = []

   #use for loop to iterate to get required number of random ints
   for i in range(numInts):
       newInt = np.random.randint(min.maxPlusOne)
       #append newInt to randInts list
       randInts.append(newInt)
       
   return randInts

def gcdIterative(a, b):
   """
       Assumbes a and b are ints
       Implements loop to determine gcd of a and b
       Returns the gcd and numIterations required to determine this
   """
   #keep track of numIterations required
   numIterations = 0
   
   #initialize remainder to zero
   remainder = 0
   
   #implement loop to compute gcd
   while (b != 0):
       remainder = a % b
       a = b
       b = remainder
       numIterations += 1
       
   #after exiting loop return a and numIterations
   return a, numIterations

def displayListSubset(oneList, subsetSize):
   """
       Assumes oneList is a python list
       subsetSize is a positive int that specifies how many elements of the list to display
   """
   #set up a list to contain the subset
   listSubset = []
   for i in range(subsetSize + 1):
       listSubset.append((oneList[i]))
       
   print(listSubset)
   
def getGcdIterativeList(listA, listB):
   """
       Assumes listA and listB are equivalently sized python lists of ints
       Implements iteratitive gcd method to determine gcd of each pair
       Returns the following:
           execution time required
           list of gcd values
           list of num iterations required
   """
   #initialize list of gcd vals
   gcdList = []
   numIterations =[]
   
   #get start time
   startTime = time.time()
  #iterate through the lists and determine gcd of each pair
   for i in range(len(listA)):
       curGcd, numIt = gcdIterative(listA[i], listB[i])
       #append this gcd to gcdList
       gcdList.append(curGcd)
       #append this numIterations to the numIterations list
       numIterations.append(numIt)
       
   endTime = time.time()
   itExeTime = endTime - startTime
   #return exe time, gcdLIst and numIterations list
   return itExeTime, gcdList, numIterations

#plot the histogram for the number of iterations
plt.figure()
bins = 10
plt.hist(itNumIt, bins, facecolor='green', label = 'iterative')
plt.legend(loc = 'best')
plt.title("Number of iterations for iterative gcd function")
plt.xlabel('Number of iterations required')
plt.ylabel('Num occurrances of each iteration value')

 

Transcribed Image Text:

Project 3 Learning objectives Gain additional experience writing a recursive function Determine number of recursive calls required to solve the problem Write a recursive function to compute the gcd of two integers Gain additional experience determining execution time Compare the execution time required to execute the iterative function to compute the gcd and the recursive function to compute the gcd Project 3 Learning objectives Gain additional experience writing a recursive function Determine number of recursive calls required to solve the problem Write a recursive function to compute the gcd of two integers Gain additional experience determining execution time Compare the execution time required to execute the iterative function to compute the gcd and the recursive function to compute the gcd