---

Coin Change Problem

Given a list of coin denominations, c, and a desired amount of money, M, find the fewest number of coins, n, necessary to generate M.

def Change(amount, denominations):
    n = 0
    for coinValue in denominations:
        count = amount//coinValue
        amount -= count*coinValue
        print "   %d x %d," % (count, coinValue),
        n += count
    print
    return n

Change(40, [25,10,5,1])

   1 x 25,    1 x 10,    1 x 5,    0 x 1,

3

Change(40, [25,20,10,5,1])

   1 x 25,    0 x 20,    1 x 10,    1 x 5,    0 x 1,

3

---

Sorting

Given a list of numbers, N, reorder them into a strictly non-decreasing order.

def indexOfMin(N,first,last):
    """ finds the smallest element of N between indices first and last """
    index = first
    for k in xrange(index+1,last): 
        if (N[k] < N[index]): 
            index = k 
    return index 

def selectionSortRecursive(N,first,last): 
    if (first < last): 
        index = indexOfMin(N,first,last) 
        N[first], N[index] = N[index], N[first]
        print N[:first+1], N[first+1:]
        N = selectionSortRecursive(N,first+1,last)
    return N

def selectionSort(N):
    return selectionSortRecursive(N,0,len(N))

selectionSort([27, 12, 3, 18, 11, 7])

[3] [12, 27, 18, 11, 7]
[3, 7] [27, 18, 11, 12]
[3, 7, 11] [18, 27, 12]
[3, 7, 11, 12] [27, 18]
[3, 7, 11, 12, 18] [27]
[3, 7, 11, 12, 18, 27] []

[3, 7, 11, 12, 18, 27]

---

The n^th Fibonacci Number

Produce the n^th number from the sequence F_n = F_n-1 + F_n-2 where F₁ = F₂ = 1.

import math

def fibonacciDirect(n):
    sqrt5 = math.sqrt(5.0)
    return (((1.0 + sqrt5)/2.0)**n - ((1.0 - sqrt5)/2.0)**n)/sqrt5

k = 20   # try 10, 20, 50

%timeit fibonacciDirect(k)
fibonacciDirect(k)

1000000 loops, best of 3: 726 ns per loop

6765.000000000005

def fibonacciRecursive(n):
    if (n <= 2): 
        return 1 
    else: 
        a = fibonacciRecursive(n-1) 
        b = fibonacciRecursive(n-2)
	return a+b

%timeit fibonacciRecursive(k)
fibonacciRecursive(k)

100 loops, best of 3: 2.23 ms per loop

6765

def fibonacciIterative(n): 
    f0, f1 = 0, 1
    for i in xrange(n):
        f0, f1 =f1, f0 + f1
    return f0

%timeit fibonacciIterative(k)
fibonacciIterative(k)

100000 loops, best of 3: 1.99 µs per loop

6765