For this assignment, you will create a Python source file (that is, a text file containing Python code) for each of the problems below. You should store all of these files in a folder named pa5, which you will zip up and submit.
As you will discover this semester, computer programs are rarely correct when they are first written. They often have bugs. In addition to writing the code, you should test your code on multiple inputs, for which you independently know the correct output (e.g., by plugging the inputs into a calculator).
Remember to comment your code, choose appropriate variable names, and use consistent spacing and indentation!
Note: You are responsible for protecting your solutions to these problems from being seen by other students, either physically (e.g., by looking over your shoulder) or electronically.
[2 points] Recall that n! (n factorial) is defined as follows:
n! = n × (n-1) × ... × 2 × 1
for n ≥ 1. When n = 0, 0! = 1 by definition.
The following recursive function computes the factorial of n, assuming n is a non-negative integer:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
In the file sum.py, write a recursive function sum_positive(n) for n ≥ 0 that computes the sum S of the first n positive integers:
S = n + (n-1) + ... + 2 + 1
If n = 0, then the sum is 0 by definition.
Your function must be recursive. It should not use a loop nor use lists. Hint: Your function will look very similar to the factorial function above!
Example:
>> python3 -i sum.py >>> sum_positive(1) 1 >>> sum_positive(5) 15
[2 points] Printing selected strings from a list:
In print_x.py, define an function print_x(lst) that takes a list of strings called lst and prints out each string that starts with the character "x" in list lst. Use the following recursive algorithm:
String Hint: a string s starts with "x" if and only if s >= "x" and s < "y". (Why?)
List Hint: The tail of the list is the list containing everything except the first element of the original list, in the same order. If L is a list, its tail can be specified using L[1:], (i.e., the list Lfrom index 1 to the end).
Example:
> python3 -i print_x.py >>> print_x(["xantis", "weasel", "yak", "xiphias", "dog", "xenopus"]) xantis xiphias xenopus
[2 points] Towers of Hanoi revisited
Recall the solution to the Towers of Hanoi problem given in class, which prints out all of the instructions for the required moves for a given number of discs, n:
def towers(n, from_peg, to_peg, using_peg):
if n >= 1:
towers(n-1, from_peg, using_peg, to_peg)
print("Move disc from " + from_peg + " to " + to_peg)
towers(n-1, using_peg, to_peg, from_peg)
We can modify this function so it also returns the total number
of moves made in the problem. Complete the following revised
function, so that it prints out the required moves, and also
returns the total number of moves made. Assume that n is always
greater than or equal to 0. Store your function in towers.py.
def towers(n, from_peg, to_peg, using_peg):
# prints moves for Towers of Hanoi with n disks
# and returns total number of moves required
if n >= 1:
nummoves1 = towers(n-1, from_peg, using_peg, to_peg)
print("Move disc from " + from_peg + " to " + to_peg)
nummoves2 = towers(n-1, using_peg, to_peg, from_peg)
return _________________________
else: # what must n be? how many moves does this n require?
return _________________________
Examples:
>> python3 -i towers.py >>> towers(4, "A", "C", "B") Move disc from A to B Move disc from A to C Move disc from B to C Move disc from A to B Move disc from C to A Move disc from C to B Move disc from A to B Move disc from A to C Move disc from B to C Move disc from B to A Move disc from C to A Move disc from B to C Move disc from A to B Move disc from A to C Move disc from B to C 15 >>> towers(2, "A", "C", "B") Move disc from A to B Move disc from A to C Move disc from B to C 3
[2 points] Shuffling lists:
In shuffle.py, you will write a Python function shuffle(list1, list2) that takes two lists list1 and list2 as parameters and returns a list where the elements from list1 and list2 are shuffled together into one list.
The elements in the output list must be drawn alternately from list1 and list2. If one list is longer than the other, the extra elements should appear at the end of the output list.
Write shuffle(list1, list2) as a recursive function. Here is the general algorithm:
List hint: To append a whole list to another list, use the + operator instead of the append function:
>>>L1 = [1,2,3] >>>L2 = [4,5,6] >>>L1 = L1 + L2 >>>L1 [1,2,3,4,5,6]
Example:
>> python3 -i shuffle.py >>> shuffle([1,2,3],[4,5,6]) [1, 4, 2, 5, 3, 6] >>> shuffle([],[4,5,6]) [4, 5, 6] >>> shuffle([1,2,3],[]) [1, 2, 3] >>> shuffle([1,3],[2,4,5,6,7]) [1, 2, 3, 4, 5, 6, 7] >>> shuffle([1,3,5,7],[2,4,6]) [1, 2, 3, 4, 5, 6, 7]
[2 points] Lists of lists!
In Python, you can test whether a variable references a list or not using the isinstance function. Here's an example:
>>> a = [1,2,3] >>> b = 4 >>> isinstance(a, list) True >>> isinstance(b, list) False
In this problem, we will see that elements of a list can also be lists. For example [[1,2], [3,4,[5]], 6] is a list whose first element is the list [1,2] and whose second element is the list [3,4,[5]], and whose third element is the number 6. The lists [1,2] and [3,4,[5]]] are said to be nested in the list [[1,2], [3,4,[5]], 6]. The list [5] is nested in [3,4,[5]].
In nested_sum.py, write a recursive function nested_sum(numlist) that returns the sum of all the numbers in the numlist, including all numbers nested inside of the numlist. You may assume this list does not contain strings. That is, all data in the list, or nested within, is numerical. Implement nested_sum(numlist) according to the following recursive algorithm:
Example:
python3 -i nested_sum.py >>> nested_sum([[1,2], [3,4,[5]], 6]) 21
You should now have a pa5 directory that contains the files sum.py, print_x.py, powers.py, shuffle.py and nested_sum.py each containing the corresponding function. Zip up your directory and hand it in.