Created
March 21, 2021 17:18
-
-
Save jdahlin/d76cde701a1a0ff6aa70ff6eb0d079a2 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def fibonacci(n: int) -> int: | |
# The n:th Fibonacci number F(n) with the value of n provided by the user. | |
# https://en.wikipedia.org/wiki/Fibonacci_number | |
# https://en.wikipedia.org/wiki/Fibonacci_number#Sequence_properties | |
match n: | |
case n if not isinstance(n, int): | |
raise TypeError(f"n must be an int, not {type(n).__name__}") | |
case n if 1 >= n >= 0: | |
# F(0) = 0, F(1) = 1 | |
return n | |
case n if n > 1: | |
# F(n) = F(n-1) + F(n-2) | |
return fibonacci(n - 1) + fibonacci(n - 2) | |
case n if n < 0: | |
# F(-n) = (-1)^(n+1)F(n) | |
return int((-1) ** (n + 1) * fibonacci(-n)) | |
def ackermann(m: int, n: int) -> int: | |
# The Ackermann function A(m,n) with values of m and n provided by the user. | |
# The factorial n! of a non-negative integer n provided by the user. | |
# https://en.wikipedia.org/wiki/Ackermann_function | |
match (m, n): | |
case (m, _) if not isinstance(m, int): | |
raise TypeError(f"m must be an int, not {type(m).__name__}") | |
case (_, n) if not isinstance(n, int): | |
raise TypeError(f"n must be an int, not {type(n).__name__}") | |
case (m, _) if m < 0: | |
raise ValueError(f"m must be a non-negative number, got {m!r}") | |
case (_, n) if n < 0: | |
raise ValueError(f"n must be a non-negative number, got {n!r}") | |
case (0, n): | |
# A(0, n) = n + 1 | |
return n + 1 | |
case (m, 0) if m > 0: | |
# A(m,0) = A(m - 1,1) | |
return ackermann(m - 1, 1) | |
case (m, n) if m > 0 and n > 0: | |
# A(m,n) = A(m - 1,A(m, n - 1) | |
return ackermann(m - 1, ackermann(m, n - 1)) | |
def factorial(n: int) -> int: | |
# The factorial n! of a non-negative integer n provided by the user. | |
# https://en.wikipedia.org/wiki/Factorial | |
match n: | |
case n if not isinstance(n, int): | |
raise TypeError(f"n must be an int, not {type(n).__name__}") | |
case n if n < 0: | |
raise ValueError(f"n must be a non-negative number, got {n!r}") | |
case 0: | |
# F(0) = 1 | |
return 1 | |
case n: | |
# F(n) = n * f(n-1) * f(n-2) ... | |
return n * factorial(n - 1) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment