Анализ алгоритмов, рекурсия и исполнители
Обратный ход в задании 5, рекуррентные соотношения в задании 16 и перебор на Python вместо ручной трассировки.
Задания 5, 6, 11, 16 и 22 проверяют умение точно понимать чужой алгоритм. На экзамене выигрывает не тот, кто аккуратнее считает в уме, а тот, кто быстро переписывает условие в виде программы на Python и запускает перебор.
Рекурсивная функция состоит из базового случая (возвращает значение без вызова себя) и рекурсивного случая. Вычисление ведётся снизу вверх: сначала находят значения на базе, затем последовательно поднимаются. Значения удобно записывать в таблицу, чтобы не пересчитывать одно и то же.
Таблица значений F(n)
| n | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| F(n) | 0 | 1 | 2 | 4 | 8 | 16 |
| формула | база | база | база | F2+2F1 | F3+2F2 | F4+2F3 |
Условие: на вход алгоритма подаётся натуральное число N. Алгоритм строит новое число R: 1) строится двоичная запись N; 2) если сумма цифр этой записи чётна, справа дописываются два разряда 0 и 1, иначе — 1 и 0. Полученная запись — результат R. Укажите наименьшее число N, для которого R > 200. Решение. Дописывание двух разрядов равносильно умножению на 4 и прибавлению дописанного числа: R = 4N + 1 при чётной сумме цифр и R = 4N + 2 при нечётной. Значит R > 200 требует примерно N ≥ 50. Проверяем: N = 49 = 110001₂, сумма цифр 3 (нечётная), R = 4·49 + 2 = 198 — не подходит. N = 50 = 110010₂, сумма цифр 3 (нечётная), R = 4·50 + 2 = 202 > 200 — подходит. Перебор на Python: def R(n): b = bin(n)[2:] return int(b + ('01' if sum(map(int, b)) % 2 == 0 else '10'), 2) print(min(n for n in range(1, 1000) if R(n) > 200)) В бланк: 50
Условие: алгоритм вычисления функции F(n) задан соотношениями: F(n) = n при n < 3; F(n) = F(n − 1) + 2·F(n − 2) при n ≥ 3. Чему равно значение F(10)? Решение (снизу вверх): F(0) = 0, F(1) = 1, F(2) = 2 F(3) = 2 + 2·1 = 4 F(4) = 4 + 2·2 = 8 F(5) = 8 + 2·4 = 16 F(6) = 16 + 2·8 = 32 F(7) = 32 + 2·16 = 64 F(8) = 64 + 2·32 = 128 F(9) = 128 + 2·64 = 256 F(10) = 256 + 2·128 = 512 Проверка на Python: from functools import lru_cache @lru_cache(None) def F(n): if n < 3: return n return F(n-1) + 2*F(n-2) print(F(10)) В бланк: 512
При прямом переводе рекуррентного соотношения в код на больших n программа либо считает вечно, либо падает по глубине рекурсии — используйте @lru_cache(None) или цикл. Вторая ловушка: если перебор ничего не нашёл, чаще всего мал диапазон range — расширьте его. Третья: формулировки «наименьшее» и «наибольшее» задают min или max, и после ответа обязательно проверьте соседнее число — оно не должно удовлетворять условию.
- ✓Алгоритм из условия переписан кодом дословно, включая порядок шагов
- ✓Базовые случаи рекурсии выписаны отдельно и проверены
- ✓Использован кэш или цикл, если n велико
- ✓Диапазон перебора заведомо шире требуемого
- ✓Выбрано min или max в соответствии с формулировкой
- ✓Соседнее к ответу число проверено и не подходит
- ✓В бланке одно целое число