Added (DP) Fibonacci example.
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/examples/fib.py Sat Mar 05 15:27:15 2011 +0100
1.3 @@ -0,0 +1,40 @@
1.4 +"""
1.5 +Name: fib - Fibonacci number machine
1.6 +Description: Recursive and DP-based calculation of Fibonacci numbers.
1.7 +
1.8 +Author: Eugen Sawin <sawine@me73.com>
1.9 +"""
1.10 +
1.11 +def main():
1.12 + args = parse_args()
1.13 + if args.d:
1.14 + fun = fib_dynamic
1.15 + else:
1.16 + fun = fib
1.17 + print fun(args.n)
1.18 +
1.19 +def fib(n):
1.20 + if n > 1:
1.21 + return fib(n-1) + fib(n-2)
1.22 + else:
1.23 + return n
1.24 +
1.25 +def fib_dynamic(n):
1.26 + f = (0, 1)
1.27 + for i in xrange(2, n + 1):
1.28 + f = (f[1], sum(f))
1.29 + if n < 1:
1.30 + return n
1.31 + else:
1.32 + return f[1]
1.33 +
1.34 +from argparse import ArgumentParser
1.35 +
1.36 +def parse_args():
1.37 + parser = ArgumentParser(description='Returns the Fibonacci number for a given number n.')
1.38 + parser.add_argument('n', type=int, help='Fib(n)')
1.39 + parser.add_argument('-d', action='store_true', help='dynamic programming')
1.40 + return parser.parse_args()
1.41 +
1.42 +if __name__ == "__main__":
1.43 + main()