Waste less time on Facebook — follow Brilliant.
×

Functions

Take a number and return its prime factors. Take a URL and return the text on the page. Take a code and output the hidden message. Functions make generalized tasks like these possible.

Recursive Functions

         

Suppose we have \(2n\) "silver" coins of the same weight. One of them is however fake and it weighs less. In other words we have \(2n - 1\) silver coins of equal weight and one fake of lesser weight. We also have a balance scale. We can put any number of coins on each side of the scale at the same time, and the scale will indicate whether the two sides are the same weight or which side is lighter.

Suppose we devise an algorithm that locates the fake coin using the balance scale as few times as possible. What is the maximum number of weighing operations necessary to find the odd coin out?

This strategy will require about \(O(f(n))\) iterations. Find the value of \(3^{f(11)} \)

image

image

Consider the task of drawing the markings on a ruler: there is a mark at the halfway point, slightly shorter marks at the quarter intervals and still shorter marks at the eighth intervals. If our desired precision is \(\frac{1}{2^n}\) (arbitrary units), we put a mark at every point between \(0\) and \(2^n\). The middle mark should be \(n\) units high the quarter marks should be \(n-1\) high, etc. Assuming we have a function mark(x, h) to make a mark \(h\) units high at position \(x\), the following program does the job of marking a ruler:

1
2
3
4
5
6
7
8
def rule(left, right, height):
    if height > 0:
        x = (left + right) / 2
        mark(x, height)
        rule(left, x, height - 1)
        rule(x, right, height - 1)
   else:
        pass

Since rule(left, right, height) is recursive we know that it will call itself. Suppose that we call rule(left=0, right=2**10, height=10). During recursive call number \(9\) to rule (do not include the initial user call), it will make a mark at position \(x\). What is the value of \(x\)?

The Pascal triangle, shown below, has an interesting property. Every entry is equal to the sum of the two entries above it, except along the left and right edges where the value is always equal to \(1\).

Write a recursive algorithm that outputs the sum of the numbers on each line. For example the sum of the numbers on the \(3\)rd line is \(1+2+1=4\). What is the sum of the numbers on the \(23\)rd line?

1
2
3
4
5
1  define recur(num):
2      if num > 100:
3          return num - 10
4      else:
5          return recur(recur(num + 11))

Consider the above recursive algorithm, predict what it will output when \(\text{num}=98\).

1
2
3
4
5
6
7
23 32 62 20 77 42 31
15 14 10 11 48 32 30
14 46 71 31 53 07 82
20 12 78 78 46 24 43
37 16 12 99 15 97 85
13 29 82 71 63 27 75
44 81 80 48 02 45 17

Consider the square grid above. Suppose a person wants to move from the top left corner towards the bottom right corner. To move, a person can go down, right or up. Let \(S\) be the path traversed such that the sum of the cells in the path is minimized. What is the value of \(S\)?

×

Problem Loading...

Note Loading...

Set Loading...