f(x, y)
f(x, y) — сколько программ ведут из x в y. Внутри три строки:
x == y → 1: дошли до цели;x > y → 0: перескочили, назад дороги нет;- иначе сумма: одно слагаемое на каждую команду.
Команда → слагаемое
| прибавить 1 | f(x + 1, y) |
|---|
| умножить на 2 | f(x * 2, y) |
|---|
| вычесть 2 | f(x - 2, y) |
|---|
| целая часть от деления на 2 | f(x // 2, y) |
|---|
В таблице K(4) = 2 — это пути из 2 в 4. А f(4, 7) = 3 — пути из 4 в 7. Ответ на главный вопрос совпадает: f(2, 7) = K(7) = 8.
Запусти программу. Под ней — что она выводит.