Задача к ЕГЭ по информатике на тему «одна функция» №21

Просмотров 7 Комментарии 0

Алгоритм вычисления значения функции $F (n)$ , где $n$ – целое число, задан следующими соотношениями:

$F (n) = n$ , при $n ≤ 5$ ,

$F (n) = n+ F (n ∕2− 3)$ , когда 5 » class=»math» width=»auto»> и делится на 8,

$F (n) = n+ F (n + 4)$ , когда 5 » class=»math» width=»auto»> и не делится на 8.

Назовите максимальное значение n, для которого возможно вычислить F(n).

Если мы попробуем решать это через рекурсию перебором, то у нас будет бесконечная рекурсия. Значит значений где-то не существует.

Решим аналитически:

Рассмотрим числа кратные 8, значит получаем 8n. При этом исходе у нас будут числа кратные 8.

При некратных 8 числах: $8n + 1$ , $8n+ 2$ , $8n+ 3$ … мы попадем в $F (n+ 4)$ и некратность 8 будет навсегда зациклена.

Посмотрим теперь на $F (n∕2− 3)$ . При кратности 8 оно приведет нас в такое $n$ , которое будет нечетным, т.е. попадаем опять же в бесконечный цикл. Делаем вывод — при нечетных числах бесконечный цикл.

При каком максимальном числе мы можем попасть в число $≤$ 5 и также не быть зацикленным?

Рассмотрим 5. Сделаем обратную операцию при кратности 8.

$(5+ 3)⋅2 = 16$ .

При других числах, как 4 и меньше, у нас n будет уменьшаться.

Ответ: 16