Time: Mon 9/11/17 3 pm
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
Draw the the environment diagram that results from executing the code below until the entire program is finished or an error occurs.
y = 3 def out(h, m): y = 5 * m def inner(): return y if m == 0: return h else: return out(inner, m - 1) v = out(None, 1)()
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
Add parentheses and single-digit integers in the blanks below so that the expression on the second line evaluates to
2015. You may only add parentheses and single-digit integers. You may leave some blanks empty.
lamb = lambda lamb: lambda: lamb + lamb lamb(1000)__________ + (lambda b, c: b__________ * b__________ - c__________)(lamb(__________), 1)__________