ЕГЭ · ЗАДАНИЕ 16
Рекурсия без загадок · практика 14
F(n)=n при n≤2. При n>2: F(n)=F(n−1)+2·F(n−2). Найдите F(17).
Учебная модель Академии С для проверки приёма. Не выдаётся за задание реального экзамена.
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 65536
Решение по шагам
- Запишем базу: F(1)=1, F(2)=2. Для следующего значения нужны только два уже найденных.
- Последовательно вычислим F(3)=2+2·1=4, F(4)=4+2·2=8 и продолжим до нужного аргумента.
- F(17) = 65536. Здесь каждый следующий член удваивается, поэтому дополнительная проверка: F(n)=2ⁿ⁻¹ для n≥1.
| n | F(n) |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 4 |
| 4 | 8 |
| 5 | 16 |
| 6 | 32 |
| 7 | 64 |
| 8 | 128 |
| 9 | 256 |
| 10 | 512 |
| 11 | 1024 |
| 12 | 2048 |
| 13 | 4096 |
| 14 | 8192 |
| 15 | 16384 |
| 16 | 32768 |
| 17 | 65536 |
Проверка на Python
f = [0, 1, 2]
for n in range(3, 18):
f.append(f[n - 1] + 2 * f[n - 2])
print(f[17])