Задачи с циклами и функциями
Задача №21 ЕГЭ по информатике относится к повышенному уровню сложности. В задании проверяются умения формально выполнить алгоритм, содержащий процедуры и функции
Рассмотрим задачу из демонстрационного варианта единого государственного экзамена по информатике 2015 года.
Задача №21. Напишите в ответе число различных значений входной переменной k, при которых программа выдаёт тот же ответ, что и при входном значении k = 64. Значение k = 64 также включается в подсчёт различных значений k.
Решение.
Программа состоит из двух частей – основной программы и вспомогательного алгоритма–функции с именем f:
- Функция f принимает единственный параметр n, вычисляет значение n * n и возвращает его в точку вызова.
- В основной программе выполняется цикл с предусловием, в условное выражение которого входит вызов функции f с фактическим параметром i (f(i) >= k). Работа цикла заканчивается, если функция возвратит значение меньшее k или переменная i станет равна 0 (i > 0). После окончания цикла выводится значение переменной i.
Рассмотрим работу программы с входным значением k = 64.
- Переменная i, получившая начальное значение 12, уменьшается на 1 при каждом шаге цикла.
- Последнее значение i, при котором истинно выражение f(i) >= k, равно 8.
Действительно, f(8) = 8 • 8 = 64. - При i = 8 тело цикла выполняется последний раз. В результате, имеем
i = i - 1 = 8 – 1 = 7. - Таким образом, для входного значения k = 64 программа выводит 7.
Определим число различных значений входной переменной k.
- k = 64 является наибольшим значением, для которого программа выведет 7.
Проверим, что при k = 65 будет выведено значение 8: выражение f(8) >= 65 ложно и цикл заканчивается. - Наименьшее значение k, при котором программа выведет такой же ответ k = 72 + 1 = 50.
Действительно, если k = 49, то выражение f(7) >= 49 истинно, значит после выполнения тела цикла
i = i - 1 = 7 – 1 = 6. - Таким образом, искомые значения входной переменной k лежат в пределах:
f(7) < k <= f(8), или 50 <= k <= 64.
Ответ. 15