Time: Wed 9/13/17 2 pm
IMPORTANT In this question, assume that all of
h are functions that take one non-negative integer argument and return a non-negative integer. You do not need to consider negative or fractional numbers.
Implement the higher-order function
decompose1, which takes two functions
h as arguments. It returns a function
g that relates
h in the following way: For any non-negative integer
f(g(x)). Assume that
decompose1 will be called only on arguments for which such a function
g exists. Furthermore, assume that there is no recursion depth limit in Python.
def decompose1(f, h): """ Return g such that h(x) equals f(g(x)) for any non-negative integer x. >>> add_one = lambda x: x + 1 >>> square_then_add_one = lambda x: x * x + 1 >>> g = decompose1(add_one, square_then_add_one) >>> g(5) 25 >>> g(10) 100 """ def g(x): def r(y): if : return else: return return r(0)
Write a number in the blank so that the final expression below evaluates to
decompose1 is implemented correctly.
def make_adder(a): def add_to_a(b): return a + b return add_to_a def compose1(f, g): def h(x): return f(g(x)) return h e, square = make_adder(1), lambda x: x*x decompose1(e, compose1(square, e))(3) +
Suppose we have a sequence of quantities that we want to multiply together, but can only multiply two at a time. We can express the various ways of doing so by counting the number of different ways to parenthesize the sequence. For example, here are the possibilities for products of 1, 2, 3 and 4 elements:
Assume, as in the table above, that we don’t want to reorder elements.
Define a function
count_groupings that takes a positive integer
n and returns the number of ways of parenthesizing the product of
n numbers. (You might not need to use all lines.)
def count_groupings(n): """ For N >= 1, the number of distinct parenthesizations of a product of N items. >>> count_groupings(1) 1 >>> count_groupings(2) 1 >>> count_groupings(3) 2 >>> count_groupings(4) 5 >>> count_groupings(5) 14 """ if n == 1: return i = while : i += 1 return
IMPORTANT DEFINITION Each digit in a non-negative integer
n has a digit position. Digit positions begin at
0 and count from the right-most digit of
n. For example, in
568789, the digit
9 is at position
0 and digit
7 is at position
2. The digit
8 appears at both positions
Implement the find_digit function, which takes a non-negative integer
n and a digit
d greater than
0 and less than
10. It returns the largest (left-most) position in
n at which digit
d appears. If
d does not appear in
False. You may not use recursive calls.
def find_digit(n, d): """ Return the largest digit position in n for which d is the digit. >>> find_digit(567, 7) 0 >>> find_digit(567, 5) 2 >>> find_digit(567, 9) False >>> find_digit(568789, 8) # 8 appears at positions 1 and 3 3 """ i, k = 0, while n: n, last = n // 10, n % 10 if last == : i = i + 1 return
Find all values of
y between 1 and 9 (inclusive) for which the final expression below evaluates to
True. Assume that
find_digit is implemented correctly.
def compose1(f, g): def h(x): return f(g(x)) return h f = lambda x: find_digit(234567, x) compose1(f, f)(y) == y