


"""simple docstring"""







import functools
from math import sqrt
from time import time






def        a__			(							_UpperCamelCase						,      *_UpperCamelCase						,      **_UpperCamelCase			):





						"""simple docstring"""

						UpperCAmelCase__												=     time()
						UpperCAmelCase__												=     func(*_UpperCamelCase						,      **_UpperCamelCase			)
						UpperCAmelCase__												=     time()
						if int(end - start			) > 0:
												print(F"""{func.__name__} runtime: {(end - start):0.4f} s"""			)
						else:
												print(F"""{func.__name__} runtime: {(end - start) * 1000:0.4f} ms"""			)
						return output






def        a__			(							_UpperCamelCase			):





						"""simple docstring"""

						if n < 0:
												raise Exception('''n is negative'''			)
						if n == 0:
												return [0]
						UpperCAmelCase__												=     [0, 1]
						for _ in range(n - 1			):
												fib.append(fib[-1] + fib[-2]			)
						return fib






def        a__			(							_UpperCamelCase			):





						"""simple docstring"""

						def fib_recursive_term(_UpperCamelCase			) -> int:
												if i < 0:
																		raise Exception('''n is negative'''			)
												if i < 2:
																		return i
												return fib_recursive_term(i - 1			) + fib_recursive_term(i - 2			)

						if n < 0:
												raise Exception('''n is negative'''			)
						return [fib_recursive_term(_UpperCamelCase			) for i in range(n + 1			)]






def        a__			(							_UpperCamelCase			):





						"""simple docstring"""

						@functools.cache
						def fib_recursive_term(_UpperCamelCase			) -> int:
												if i < 0:
																		raise Exception('''n is negative'''			)
												if i < 2:
																		return i
												return fib_recursive_term(i - 1			) + fib_recursive_term(i - 2			)

						if n < 0:
												raise Exception('''n is negative'''			)
						return [fib_recursive_term(_UpperCamelCase			) for i in range(n + 1			)]






def        a__			(							_UpperCamelCase			):





						"""simple docstring"""

						if n < 0:
												raise Exception('''n is negative'''			)
						# Cache must be outside recursuive function
						# other it will reset every time it calls itself.
						UpperCAmelCase__												=     {0: 0, 1: 1, 2: 1}  # Prefilled cache

						def rec_fn_memoized(_UpperCamelCase			) -> int:
												if num in cache:
																		return cache[num]

												UpperCAmelCase__												=     rec_fn_memoized(num - 1			) + rec_fn_memoized(num - 2			)
												UpperCAmelCase__												=     value
												return value

						return [rec_fn_memoized(_UpperCamelCase			) for i in range(n + 1			)]






def        a__			(							_UpperCamelCase			):





						"""simple docstring"""

						if n < 0:
												raise Exception('''n is negative'''			)
						if n >= 1475:
												raise Exception('''n is too large'''			)
						UpperCAmelCase__												=     sqrt(5			)
						UpperCAmelCase__												=     (1 + sqrt_a) / 2
						return [round(phi**i / sqrt_a			) for i in range(n + 1			)]


if __name__ == "__main__":
						__a      			= 30
						time_func(fib_iterative, num)
						time_func(fib_recursive, num)  # Around 3s runtime
						time_func(fib_recursive_cached, num)  # Around 0ms runtime
						time_func(fib_memoization, num)
						time_func(fib_binet, num)



"""simple docstring"""







from __future__ import annotations






def        a__			(							_UpperCamelCase			):





						"""simple docstring"""

						UpperCAmelCase__												=     sorted(_UpperCamelCase			)
						UpperCAmelCase__												=     len(_UpperCamelCase			)
						UpperCAmelCase__												=     length >> 1
						return (
						    (sorted_list[mid_index] + sorted_list[mid_index - 1]) / 2
						    if length % 2 == 0
						    else sorted_list[mid_index]
						)






def        a__			(							):





						"""simple docstring"""

						import doctest

						doctest.testmod()


if __name__ == "__main__":
						main()