A Simple Recursive Proof
Implementing this example strengthened my grasp of recursion and proof by induction.
In the unlikely event you're a computer scientist or mathematician reading this, I apologize for any lapses in rigor (and welcome any gentle corrections).
def get_stamps(n): """ Suppose you have an unlimited supply of 5 cent and 8 cent stamps. This algorithm demonstrates by recursion that any postage amount of 28 cents or greater is possible, in 1 cent increments. Having a total of 8 basis cases (instead of 5) should ensure the smallest quantity of stamps (i.e. using as many 8 cent stamps as possible) but that is not proved formally here. Whether you'll have enough space on the package to apply the stamps, I can't say. Using 8 basis cases and +8 should ensure the stamp sequence is automatically sorted. This implementation is adapted from Jeff Erickson's excellent material: Algorithms: Appendix I, Proof by Induction, page 8 http://jeffe.cs.illinois.edu/teaching/algorithms/notes/98-induction.pdf Note: Requires python3 (because of .split(sep='+')) >>> result = get_stamps(28) >>> assert(result == '5+5+5+5+8') >>> result_list = result.split('+') >>> assert sum([int(r) for r in result_list]) == 28 >>> result = get_stamps(42) >>> assert(result == '5+5+8+8+8+8') >>> result_list = result.split('+') >>> assert sum([int(r) for r in result_list]) == 42 >>> result = get_stamps(100) >>> assert(result == '5+5+5+5+8+8+8+8+8+8+8+8+8+8') >>> result_list = result.split('+') >>> assert sum([int(r) for r in result_list]) == 100 """ # Populate the basis cases assert(n >= 28) if n == 28: return '5+5+5+5+8' elif n == 29: return '5+8+8+8' elif n == 30: return '5+5+5+5+5+5' elif n == 31: return '5+5+5+8+8' elif n == 32: return '8+8+8+8' elif n == 33: return '5+5+5+5+5+8' elif n == 34: return '5+5+8+8+8' elif n == 35: return '5+5+5+5+5+5+5' else: # By definition, we can recursively step down in decrements # of 8 and eventually land on one of the base cases # Each step "down" means that we must add 8 in order to # arrive eventually at the passed in value of n return get_stamps(n-8) + '+8' if __name__ == '__main__': from doctest import testmod testmod(verbose=True)
Contact: hello at escapefromsql.net