homework_3.py

import timeit

def fibonacci_while_loop(n):
	#compute the n-th fibonacci number. n > 2
	count = 2
	first, last = 1, 1
	while count < n:
		first, last = last, first + last
		count += 1
	return last

def fibonacci_for_loop(n):
	first, last = 1, 1
	for _ in range(n-2):
		tmp = first
		first = last
		last = first + tmp
	return last		

def fibonacci_recursive(n):
	if n == 1:
		return 1
	elif n == 2:
		return 1
	else:
		return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

def fibonacci_recursive_cache(n, cache):
	if n == 1:
		return 1
	elif n == 2:
		return 1
	if n in cache:
		return cache[n]
	cache[n] = fibonacci_recursive_cache(n-1, cache) + fibonacci_recursive_cache(n-2, cache)
	return cache[n]

def baskin_robins_kato(n, k, cur):
	canWin = False
	if cur >= n:
		return canWin

	for i in range(1, k+1):
		if not baskin_robins_kato(n, k, cur+i):
			canWin = True
	return canWin

def baskin_robins_kato_cache(n, k, cur, cache):
	if (n,k,cur) in cache:
		return cache[(n,k,cur)]

	canWin = False
	if cur >= n:
		return canWin
	
	for i in range(1, k+1):
		if not baskin_robins_kato_cache(n,k,cur+i, cache):
			canWin = True
	cache[(n,k,cur)] = canWin
	return cache[(n,k,cur)]

def baskin_robins_analytics(n, k):
	for i in range(1, k+1):
		if (n-i) % (k+1) == 0:
			return True
	return False

def wrapper(func, *args, **kwargs):
	def wrapped():
		return func(*args, **kwargs)
	return wrapped

if __name__ == "__main__":
	print "5th fibonacci number computed using while loop is ={0}".format(fibonacci_while_loop(5))
	#print "11th fibonacci number computed using while loop is = {0}".format(fibonacci_while_loop(11))
	#print "11th fibonacci number computed using FOR loop is = {0}".format(fibonacci_for_loop(11))
	#print "11th fibonacci number computed RESURIVELY is = {0}".format(fibonacci_recursive(11))
	#print timeit.timeit(wrapper(fibonacci_while_loop, 20), number=1000)
	#print timeit.timeit(wrapper(fibonacci_for_loop, 20), number=1000)
	#print timeit.timeit(wrapper(fibonacci_recursive, 20), number=1000)
	#print timeit.timeit(wrapper(fibonacci_recursive_cache, 20, {}), number=1000)