Due by 11:59pm on Wednesday, 10/2
Due date extended. This homework was originally due Tuesday, 10/1. Due to problems with the submission system, the deadline was extended a day.
Submission. See the online submission instructions. We have provided a hw3.py starter file for the questions below.
Readings. Section 1.7 of the online textbook.
Q1. A mathematical function G on positive integers is defined by two cases:
G(n) = n, if n <= 3
G(n) = G(n - 1) + 2 * G(n - 2) + 3 * G(n - 3), if n > 3
Write a recursive function g that computes G(n). Then, write an iterative function g_iter that also computes G(n):
def g(n):
"""Return the value of G(n), computed recursively.
>>> g(1)
1
>>> g(2)
2
>>> g(3)
3
>>> g(4)
10
>>> g(5)
22
"""
"*** YOUR CODE HERE ***"
def g_iter(n):
"""Return the value of G(n), computed iteratively.
>>> g_iter(1)
1
>>> g_iter(2)
2
>>> g_iter(3)
3
>>> g_iter(4)
10
>>> g_iter(5)
22
"""
"*** YOUR CODE HERE ***"
Q2. Write a function has_seven that takes a positive integer n and returns whether n contains the digit 7. Do not use any assignment statements:
def has_seven(k):
"""Has a has_seven
>>> has_seven(3)
False
>>> has_seven(7)
True
>>> has_seven(2734)
True
>>> has_seven(2634)
False
>>> has_seven(734)
True
>>> has_seven(7777)
True
"""
"*** YOUR CODE HERE ***"
Q3. The ping-pong sequence counts up starting from 1 and is always either counting up or counting down. At element k, the direction switches if k is a multiple of 7 or contains the digit 7. The first five direction changes are after . The first 30 elements of the ping-pong sequence are listed below, with direction swaps marked using brackets at the 7th, 14th, 17th, 21st, 27th, and 28th elements:
"1 2 3 4 5 6 [7] 6 5 4 3 2 1 [0] 1 2 [3] 2 1 0 [-1] 0 1 2 3 4 [5] [4] 5 6"
Implement a function pingpong that returns the nth element of the ping-pong sequence. Do not use any assignment statements.
Hint: If you're stuck, try implementing pingpong first using assignment and a while statement, then try a recursive implementation without assignment:
def pingpong(n):
"""Return the nth element of the ping-pong sequence.
>>> pingpong(7)
7
>>> pingpong(8)
6
>>> pingpong(15)
1
>>> pingpong(21)
-1
>>> pingpong(22)
0
>>> pingpong(30)
6
>>> pingpong(68)
2
>>> pingpong(69)
1
>>> pingpong(70)
0
>>> pingpong(71)
1
>>> pingpong(72)
0
>>> pingpong(100)
2
"""
"*** YOUR CODE HERE ***"
Q4. Write a function that takes a positive integer n and returns the number of ten-pairs it contains. A ten-pair is a pairs of digits within n that sum to 10. Do not use any assignment statements.
The number 7,823,952 has 3 ten-pairs. The first and fourth digits sum to 7+3=10, the second and third digits sum to 8+2=10, and the second and last digit sum to 8+2=10:
def ten_pairs(n):
"""Return the number of ten-pairs within positive integer n.
>>> ten_pairs(7823952)
3
>>> ten_pairs(55055)
6
>>> ten_pairs(9641469)
6
"""
"*** YOUR CODE HERE ***"
Q5. Once the machines take over, the denomination of every coin will be a power of two: 1-cent, 2-cent, 4-cent, 8-cent, 16-cent, etc. There will be no limit to how much a coin can be worth.
A set of coins makes change for n if the sum of the values of the coins is n. For example, the following sets make change for 7:
Thus, there are 6 ways to make change for 7. Write a function count_change that takes a positive integer n and returns the number of ways to make change for n using these coins of the future:
def count_change(amount):
"""Return the number of ways to make change for amount.
>>> count_change(7)
6
>>> count_change(10)
14
>>> count_change(20)
60
>>> count_change(100)
9828
"""
"*** YOUR CODE HERE ***"
Q6. (Extra for experts) The recursive factorial function can be written as a single expression by using a conditional expression.
>>> fact = lambda n: 1 if n == 1 else mul(n, fact(sub(n, 1))) >>> fact(5) 120
However, this implementation relies on the fact (no pun intended) that fact has a name, to which we refer in the body of fact. To write a recursive function, we have always given it a name using a def or assignment statement so that we can refer to the function within its own body. In this question, your job is to define fact recursively without giving it a name!
Write an expression that computes n factorial using only call expressions, conditional expressions, and lambda expressions (no assignment or def statements). The sub and mul functons from the operator module are the only built-in function required to solve this problem:
from operator import sub, mul
def make_anonymous_factorial():
"""Return the value of an expression that computes factorial.
>>> make_anonymous_factorial()(5)
120
"""
return YOUR_EXPRESSION_HERE