mirror of
https://github.com/TheAlgorithms/Python.git
synced 2026-09-28 21:45:27 +08:00
92af64afcd
* Added function that calculates Pell numbers * Fixed ruff error * Renamed input argument to be more descriptive * updating DIRECTORY.md --------- Co-authored-by: Christian Clauss <cclauss@me.com> Co-authored-by: cclauss <cclauss@users.noreply.github.com>
80 lines
2.2 KiB
Python
80 lines
2.2 KiB
Python
def pell_number_iterative(subscript: int) -> int:
|
|
"""
|
|
This function returns the `subscript`-th Pell number iteratively, where
|
|
`subscript` is a non-negative integer. Pell numbers are defined by the
|
|
recurrence relation:
|
|
|
|
P_0 = 0, P_1 = 1, P_n = 2 * P_(n-1) + P_(n-2)
|
|
|
|
https://en.wikipedia.org/wiki/Pell_number
|
|
https://oeis.org/A000129
|
|
|
|
>>> pell_number_iterative(0)
|
|
0
|
|
>>> pell_number_iterative(1)
|
|
1
|
|
>>> pell_number_iterative(12)
|
|
13860
|
|
>>> pell_number_iterative("1")
|
|
Traceback (most recent call last):
|
|
...
|
|
ValueError: The input must be an integer.
|
|
>>> pell_number_iterative(-1)
|
|
Traceback (most recent call last):
|
|
...
|
|
ValueError: The input number must be non-negative.
|
|
"""
|
|
if not isinstance(subscript, int):
|
|
raise ValueError("The input must be an integer.")
|
|
|
|
if subscript < 0:
|
|
raise ValueError("The input number must be non-negative.")
|
|
|
|
if subscript in (0, 1):
|
|
return subscript
|
|
|
|
prev_prev_num = 0
|
|
prev_num = 1
|
|
|
|
for _ in range(2, subscript + 1):
|
|
temp = 2 * prev_num + prev_prev_num
|
|
prev_prev_num = prev_num
|
|
prev_num = temp
|
|
|
|
return prev_num
|
|
|
|
|
|
def pell_number_recursive(subscript: int) -> int:
|
|
"""
|
|
This function calculates the `subscript`-th Pell number recursively. Due to
|
|
its recursive nature, this function grows exponentially with `subscript`.
|
|
For large values of `subscript`, use pell_number_iterative instead.
|
|
|
|
>>> pell_number_recursive(0)
|
|
0
|
|
>>> pell_number_recursive(1)
|
|
1
|
|
>>> pell_number_recursive(12)
|
|
13860
|
|
>>> pell_number_recursive("1")
|
|
Traceback (most recent call last):
|
|
...
|
|
ValueError: The input must be an integer.
|
|
>>> pell_number_recursive(-1)
|
|
Traceback (most recent call last):
|
|
...
|
|
ValueError: The input number must be non-negative.
|
|
"""
|
|
if not isinstance(subscript, int):
|
|
raise ValueError("The input must be an integer.")
|
|
|
|
if subscript < 0:
|
|
raise ValueError("The input number must be non-negative.")
|
|
|
|
if subscript in (0, 1):
|
|
return subscript
|
|
|
|
return 2 * pell_number_recursive(subscript - 1) + pell_number_recursive(
|
|
subscript - 2
|
|
)
|