CS 61A

Time: Wed 9/13/17 2 pm

Recursions

Zombies! (fa15-mt1-4)

IMPORTANT In this question, assume that all of f, g, and 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 f and h as arguments. It returns a function g that relates f to h in the following way: For any non-negative integer x, h(x) equals 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 2015. Assume 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) +

Your Father's Parentheses (sp16-mt1-1)

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:

1 element of 1 possibility
a
2 elements of 1 possibility
ab
3 elements of 2 possibilities
(ab)c
a(bc)
4 elements of 5 possibilities
a(b(cd))
a((bc)d)
(ab)(cd)
(a(bc))d
((ab)c)d

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

Higher Order Functions

Digit Fidget (fa15-mt1-3)

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 1 and 3.

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 n, then find_digit returns 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
```