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])
Change(40, [25,20,10,5,1])
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])
Produce the nth number from the sequence Fn = Fn-1 + Fn-2 where F1 = F2 = 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)
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)
def fibonacciIterative(n):
f0, f1 = 0, 1
for i in xrange(n):
f0, f1 =f1, f0 + f1
return f0
%timeit fibonacciIterative(k)
fibonacciIterative(k)