.py files containing your work. (If you upload a screenshot or other file format, you won't get credit.)This homework assignment must be submitted in Gradescope by 10am CST on Tuesday, November 9, 2021.
This homework assignment focuses on recursion and the additional aspects of object-oriented programming that were covered last week.
Collaboration is prohibited, and you may only access resources (books, online, etc.) listed below.
The main course materials to refer to for this homework are:
(Lecture videos are not linked on worksheets, but are also useful to review while working on worksheets. Video links can be found in the course course Blackboard site.)
This homework assignment has 2 problems, numbered 2 and 3. Thus the grading breakdown is:
| Points | Item |
|---|---|
| 2 | Autograder |
| 4 | Problem 2 |
| 4 | Problem 3 |
| 10 | Total |
Ask your instructor or TA a question by email, in office hours, or on discord.
Gradescope will show the results of the automated syntax check of all submitted files as the score for problem 1.
Consider the following definition of a sequence $K_n$ that is similar in spirit to the Fibonacci sequence studied on the last worksheet, but where the rule for computing the next term involves a decision:
$$ K_n = \begin{cases} n & \text{ if $n=0$, $1$, or $2$}\\ K_{n-1} + n - 1 & \text{ if $K_{n-1}$ is a multiple of $n$}\\ K_{n-1} + K_{n-3} & \text{otherwise} \end{cases} $$Write a recursive function k(n) that calculates and returns the value of $K_n$. Then, use it to make a program hwk11prob2.py that prints the values of k(n) for n=0, 1, ..., 25 in a table that uses the format shown below:
0 0
1 1
2 2
3 2
4 3
5 5
6 7
7 13
[... more lines here, continuing up to n=25 ...]In this table, the left column shows n and the right column shows k(n). The exact spacing of the table is not important.
If your function is working correctly, the last value in the table (i.e. k(25)) will be 8199.
The definition above tells you everything you need to know, but in case it is unclear, here's a more detailed explanation of a few values.
We're told $K_0=0$, $K_1=1$, and $K_2=2$.
For $K_3$, to apply the definition we need to check whether $K_2=2$ is a multiple of $3$. It is not, so we use the last row of the definition: $$K_3 = K_2 + K_0 = 2 + 0 = 2.$$
Moving ahead, if we use the definition we can determine that $K_3=2$, $K_4=3$, $K_5=5$, and $K_6=7$ as shown in the table above. Let's use that information to compute the next term.
For $K_7$, we need to check whether $K_6=7$ is a multiple of $7$. It is, so we use the middle row of the definition: $$K_7 = K_6 + 7 - 1 = 7 + 7 - 1 = 13$$
def k(n):
'''A recursive function to find the nth entry in the sequence k_n'''
# Base case where n is 0, 1, or 2
if n == 0 or n == 1 or n == 2:
return n
# Case where k(n-1) is a multiple of n
elif k(n-1) % n == 0:
return k(n-1) + n-1
# Final case where neither of the above cases hold
else:
return k(n-1) + k(n-3)
# This block of code goes directly together with the definition of k(n) above.
# Depending on one's computer/setup, it may take a while to run.
# Use range 26 so that we end on n=25
for n in range(26):
print(n, k(n))
In a file hwk11prob3.py, write a class called Pair in Python that stores a mutable pair of values, which we'll call x (the first value) and y (the second value). The constructor should accept x and y as its arguments, in that order.
Make it so that the constructor arguments x and y are stored as attributes of the object with the same names.
In addition, make it so that Pair supports the mutable sequence protocol as follows:
Pair object should be equal to 2xyIndexErrorxyIndexErrorThe code below shows some tests of how the class should behave. (These examples refer to the class as Pair alone, so if you put them in a test script that imports hwk11prob3, you might need to change Pair to hwk11prob3.Pair.)
__eq__, __str__, or __repr__class Pair:
'''Represents a pair of values x and y in the form [x,y]'''
def __init__(self, x, y):
'''Initialize an instance of Pair with attributes x and y'''
self.x = x
self.y = y
def __len__(self):
'''The length of any Pair is always 2.'''
return 2
def __getitem__(self, idx):
'''Overload __getitem__ so that the x is located at index 0
and y is located at index 1'''
if idx == 0:
return self.x
elif idx == 1:
return self.y
else:
raise IndexError("The class Pair only supports requesting indices 0 or 1.")
def __setitem__(self, idx, value):
'''Overload __setitem__ so that x is changed by changing
index 0, and y is changed by changing index 1'''
if idx == 0:
self.x = value
elif idx == 1:
self.y = value
else:
raise IndexError("The class Pair only supports assignment for indices 0 or 1.")