Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Solving and testing fast exponentiation
- Посмотрим на задачу глазами разработчика: сначала решение, затем убеждаемся в его корректности.
- Задача
- Вычислить base exp двумя способами: простым умножением и алгоритмом быстрого возведения в степень.
- Решение
- ``python
- def power(base: int, exp: int) -> int:
- result = 1
- for _ in range(exp):
- result *= base
- return result
- def fast_power(base: int, exp: int) -> int:
- result = 1
- while exp > 0:
- if exp % 2 == 1:
- result *= base
- base *= base
- exp //= 2
- return result
- print(power(2, 10), fast_power(2, 10))
- `
- Как это работает
- Быстрый метод использует двоичное представление показателя: показатель делится на два, а основание возводится в квадрат. Число умножений падает с exp до log2(exp).
- Пример работы
- `text
- 1024 1024
- `
- Сложность
- O(exp) против O(log exp).
- Проверка тестами
- Хорошая привычка — проверять решение сразу на нескольких примерах, включая крайние случаи.
- `python
- assert is_valid(True) is not None # базовая проверка вызова
- assert is_valid(False) is not None # и второй случай
- ``
- Такой минимум уже защищает от случайной ошибки при правках кода.
- Тесты вида assert удобны для учебных задач: они короткие, наглядные и не требуют фреймворков.
- View Full Gallery → https://go.cbrop.com/prse
- Related:
- https://radicle.network/nodes/seed.cielago.xyz/rad%3Az2M78kzSCbcdfqtC1uxNpk8MHdmbz/issues/96c6a369b78a929cbf613eb8fd1a225b7e8023dd
- https://gitlab.com/chuongnhuhoa/trusrewre/-/blob/main/articles/factorial-shagi-mwifdmig.md
- https://pastebin.com/8BY12efG
- https://blogfreely.net/catherine-vasilyev70/mo-nu-fu-chou-zhi-ye-cg
- https://workshoptests372558.vuodatus.net/lue/2026/11/23
Advertisement
Add Comment
Please, Sign In to add comment