Answer to Question #292430 in Python for eranna

Question

Problem 1: Write a program that takes a positive integer as input and prints its factorial. Write two separate functions, one that computes the factorial iteratively, and the other recursively. Problem 2: Write a program to print the first n Fibonacci numbers. Write separate iterative and recursive versions. Which version do you suspect is more efficient ? Why ? Problem 3: Write a program that tests if a number is prime or not. Input a number from the user. The output should be ‘True’ if the number is a prime, ‘False’ otherwise. Problem 4: Write a program to sort a list of integers using Insertion sort, Mergesort and Quicksort. First take as input the size ‘n’ of the array, then read in the ‘n’ input integers that need to be sorted. Problem 5: Devise an experiment to verify that the runtime of the list index operator is indeed O(1), You might want to read sections 3.5 and 3.6 of Miller and Ranum’s online book.

Answer 1

#Problem 1

# Python program to to print the factorial of a number.

# storing a number for Factorial in the variable 'num'

num = int(input("Enter a number for factorial - "))

fact = 1

# adding if-elif-else statements

if num < 0:

  print("Invalid")

elif num == 0:

   print("1")

else:

   for i in range(1, num + 1):

       fact = fact * i

print(f"Factorial of {num} is: ", fact)

#Problem 2

# change this value for a different result

nterms = 10

# uncomment to take input from the user

#nterms = int(input("How many terms? "))

# first two terms

n1 = 0

n2 = 1

count = 0

# check if the number of terms is valid

if nterms <= 0:

  print("Please enter a positive integer")

elif nterms == 1:

  print("Fibonacci sequence upto",nterms,":")

  print(n1)

else:

  print("Fibonacci sequence upto",nterms,":")

  while count < nterms:

      print(n1,end=' , ')

      nth = n1 + n2

      # update values

      n1 = n2

      n2 = nth

      count += 1

#Problem 3

# Program to check if a number is prime or not

# Take input from the user

num = int(input("Enter a number: "))

# define a flag variable

flag = False

# prime numbers are greater than 1

if num > 1:

   # check for factors

   for i in range(2, num):

       if (num % i) == 0:

           # if factor is found, set flag to True

           flag = True

           # break out of loop

           break

# check if flag is True

if flag is True:

   print(num, "is not a prime number")

else:

   print(num, "is a prime number")

#Problem 4

def insertion_sort(array):

   for i in range(len(array)):

       for j in range(0,i+1):

           if array[i] < array[j]:

               array[i],array[j] = array[j] ,array[i]   

       for val in array:

           print(val,end = " ")print("Enter elements into the array")

array = [int(n) for n in input().split()]

insertion_sort(array)

def quick_sort(arr,first_index,last_index):   

   if first_index < last_index:

        pivot = first_index

        i = first_index + 1

        j = last_index        while i < j:          #Incrementing i till element is greater than element at pivot

          while arr[i] < arr[pivot] and i < last_index:

                i+=1

          #Decrementing j till element is less than element at pivot

          while arr[j] > arr[pivot]:

                j-=1          if i < j:

                arr[i], arr[j] = arr[j],arr[i]        

                   arr[pivot], arr[j] = arr[j],arr[pivot]

        #Sorting Elements Before Swaping the pivot elements

        quick_sort(arr,first_index,j-1)

        quick_sort(arr,j+1,last_index)print("Enter size of array")

N = int(input())print("Enter Elements into the array")

arr = [int(n) for n in input().split()]quick_sort(arr,0,N-1)

print("Elements After Sorting")

for i in range(N):

   print(arr[i],end=" ")

# Python program for implementation of MergeSort

# Merges two subarrays of array[].

# First subarray is arr1[low..mid]

# Second subarray is arr2[mid+1..high]

def mergeSort(array, low, mid, high):

   n1 = mid - low + 1

   n2 = high - mid

   # create temp arrays

   arr1 = [0] * (n1)

   arr2 = [0] * (n2)

   # Copy data to temp arrays arr1[] and arr2[]

   for i in range(0 , n1):

       arr1[i] = array[low + i]

   for j in range(0 , n2):

       arr2[j] = array[mid + 1 + j]

   # Merge the temp arrays back into arr[l..r]

   i = 0    # Initial index of first subarray

   j = 0    # Initial index of second subarray

   k = low  # Initial index of merged subarray

   while i < n1 and j < n2 :

       if arr1[i] <= arr2[j]:

           array[k] = arr1[i]

           i += 1

       else:

           array[k] = arr2[j]

           j += 1

       k += 1

   # Copy the remaining elements of arr1[], if there are any

   while i < n1:

       array[k] = arr1[i]

       i += 1

       k += 1

   # Copy the remaining elements of arr2[], if there are any

   while j < n2:

       array[k] = arr2[j]

       j += 1

       k += 1def partition(array,low,high):

   if low < high:

      #Same as (low+high)//2, but avoids overflow for large low and high

      mid = (low+(high-1))//2

       # Sort first and second halves

       partition(array, low, mid)

       partition(array, mid+1, high)

       mergeSort(array, low, mid, high)

print("Enter Elements into array")

array = [int(n) for n input().split()]

n = len(array)

partition(array,0,n-1)

print ("\n\nSorted array is")

for i in range(n):

   print ("%d" %array[i])

#Problem 5

def memoize(func):
cache = dict()

def memoized_func(*args):
    if args in cache:
        return cache[args]
    result = func(*args)
    cache[args] = result
    return result

return memoized_func