Due by 11:59pm on Wednesday, 2/26
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