Function Exercises
Prev Chapter 9. Functions Next

Function Exercises

  1. Fast Exponentiation. This is the fastest way to raise a number to an integer power. It requires the fewest multiplies, and does not use logarithms.

    Procedure 9.1. Fast Exponentiation of integers, raises n to the p power

    1. Base Case. If p = 0, return 1.0.

    2. Odd. If p is odd, return n × fastExp (n, p−1 ).

    3. Even. If p is even, compute t ← fastExp (n, p÷2 ); return t × t.

  2. Greatest Common Divisor. The greatest common divisor is the largest number which will evenly divide two other numbers. You use this when you reduce fractions. See Greatest Common Divisor in for an alternate example of this exercise's algorithm. This version can be slightly faster than the loop we looked at earlier.

    Procedure 9.2. Greatest Common Divisor of two integers, p and q

    1. Base Case. If p = q, return p.

    2. Swap. If p < q, return GCD (q, p).

    3. Subtract. If p > q, return GCD (p, p−q).

  3. Factorial Function. Factorial of a number n is the number of possible arrangements of 0 through n things. It is computed as the product of the numbers 1 through n. That is, 1×2×3×...×n. We touched on this in Computing e in the section called “Iteration Exercises”. This function defintion can simplify the program we wrote for that exercise.

    Procedure 9.3. Factorial of an integer, n

    1. Base Case. If n = 0, return 1.

    2. Multiply. If n > 0, return n × factorial (n−1).

  4. Fibonacci Series. Fibonacci numbers have a number of interesting mathematical properties. The ratio of adjacent Fibonacci numbers approximates the golden ratio ((1+ √5)/2, about 1.618), used widely in art and architecture.

    Procedure 9.4. The nth Fibonacci Number, Fn

    1. F0 Case. If n = 0, return 0.

    2. F1 Case. If n = 1, return 1.

    3. Fn = Fn−1 and Fn−2. If n > 2, return fibonacci (n−1) + fibonacci (n−2).

  5. Ackermann's Function. An especially complex algorithm that computes some really big results. This is a function which is specifically designed to be complex. It cannot easily be rewritten as a simple loop. Further, it produces extremely large results because it describes extremely large exponents.

    Procedure 9.5. Ackermann's Function of two numbers, m and n

    1. Base Case. If m = 0, return n+1.

    2. N Zero Case. If m ≠ 0 and n = 0, return ackerman (m−1, 1).

    3. N Non-Zero Case. If m ≠ 0 and n ≠ 0, return ackerman (m−1, ackerman (m, n−1)).

  6. Compute the Maximum Value of Some Function. Given some integer-valued function f(x), we want to know what value of x has the largest value for f(x) in some interval of values. For additional insight, see [Dijkstra76].

    Imagine we have an integer function of an integer, call it f(x). Here are some examples of this kind of function.

    • def f1(x): return x

    • def f2(x): return -5/3*x-3

    • def f3(x): return -5*x*x+2*x-3

    The question we want to answer is what value of x in some fixed interval returns the largest value for the given function? In the case of the first example, def f1(x): return x, the largest value of f1(x) in the interval 0 ≤ x < 10 occurs when x is 9. What about f3(x) in the range (-10 ≤ x ≤ 10)

    Procedure 9.6. Max of a Function in the interval low to high

    1. Initialize

      x ← low

      max ← x

      maxFx ← f(max)

    2. Loop. While low ≤ x < high.

      1. New Max? If f(x) > maxFx, then

        max ← x

        maxFx ← f(max)

      2. Next X. Increment x by 1.

    3. Return. Return x as the value at which f(x) had the largest value.

  7. Integration Approximation. This is a simple rectangular rule for finding the area under a curve which is continuous on some closed interval.

    We will define some function which we will integrate, call it f (x). Here are some examples.

    • def f1(x): return x*x
    • def f2(x): return 0.5 * x * x
    • def f3(x): return exp( x )
    • def f4(x): return 5 * sin( x )

    When we specify y=f(x), we are specifying two dimensions. The y is given by the function's values. The x dimension is given by some interval. If you draw the function's curve, you put two limits on the x axis, this is one set of boundaries. The space between the curve and the y axis is the other boundary.

    The x axis limits are a and b. We subdivide this interval into s rectangles, the width of each is h=(b−a)÷s. We take the function's value at the corner as the average height of the curve over that interval. If the interval is small enough, this is reasonably accurate.

    Procedure 9.7. Integration Function in the interval a to b in s steps

    1. Initialize

      x ← a

      h ← (b−a)÷s

      sum ← 0.0

    2. Loop. While a ≤ x < b.

      1. Update Sum. Increment sum by f(x) × h.

      2. Next X. Increment x by h.

    3. Return. Return sum as the area under the curve f(x) for a ≤ x < b.

  8. Field Bet Results. In the dice game of Craps, the Field bet in craps is a winner when any of the numbers 2, 3, 4, 9, 10, 11 or 12 are rolled. On 2 and 12 it pays 2:1, on the other number, it pays 1:1.

    Define a function win (dice, num, pays ). If the value of dice equals num, then the value of pays is returned, otherwise 0 is returned. Make the default for pays a 1, so we don't have to repeat this value over and over again.

    Define a function field (dice). This will call win 7 times: once with each of the values for which the field pays. If the value of dice is a 7, it returns -1 because the bet is a loss. Otherwise it returns 0 because the bet is unresolved. It would start with

    def field( dice ):
    win( dice, 2, pays=2 )
    win( dice, 3, pays=1 )
    ...

    Create a function roll that creates two dice values from 1 to 6 and returns their sum. The sum of two dice will be a value from 2 to 12.

    Create a main program that calls roll to get a dice value, then calls field with the value that is rolled to get the payout amount. Compute the average of several hundred experiments.

  9. range Function Keywords. Does the range function permit keywords for supplying argument values? What are the keywords?

  10. Optional First Argument. Optional parameters must come last, yet range fakes this out by appearing to have an optional parameter that comes first. The most common situation is range(5), and having to type range(0,5) seems rather silly. In this case, convenience trumps strict adherence to the rules. Is this a good thing? Is strict adherence to the rules more or less important than convenience?

Prev Up Next
More Features Home Object Method Functions