Информатика в школе

Задача №21 — одна из наиболее сложных задач экзамена по информатике. В одной из тренировочных работ 2017 г. встретилось задание, которое, как я считаю, достойно внимания. В данной статье попробую поподробнее объяснить как решать такую задачу.

Задача. 

Определите, количество чисел k, для которых следующая программа выведет такой же результат, что и для k = 13?

var k, i : longint;
function f(n: longint): longint;
begin
f:= n*n*n - 5*n;
end;
begin
readln(k);
i := 1;
while f(i) < k do
i := i + 1;
if 2*f(i)-k <= k-f(i-1) then
writeln(i)
else
writeln(i-1);
end.

 def f(n):
    return n*n*n - 5*n
k = int(input())
i = 1
while f(i) < k:
    i += 1
if 2*f(i)-k <= k-f(i-1):
    print(i)
else:
    print(i-1)

Коротко опишу программу:

1. Функция f(n) возвращает значение выражения n³-5*n
2. k — вводимое нами число
3. Начальное значение переменной i = 1
4. В цикле while (цикл с условием) увеличиваем значение переменной i на единицу, если значение функции f(i) < k  (или i³-5*i < k)
5. После того, как вышли из цикла проверяем, выполняется ли условие:

   2*f(i)-k <= k-f(i-1)

6. Если выполняется — выводим на экран  значение переменной i, иначе — i-1.

Решение данной задачи разобьем на несколько этапов, каждый из которых я подробно опишу.

1. Выясним, что выведет программа для k = 13. (Для того, чтобы ответить на главный вопрос задачи, необходимо знать результат программы для k = 13)

Определим значение переменной i при выходе из цикла While

При i = 4 мы выходим из цикла (со значением переменной i = 4).

Теперь обращаемся к условию

if 2*f(i)-k <= k-f(i-1) then
writeln(i)
else
writeln(i-1);

и выясняем, что будет выведено на экран: i или i-1 (4 или 3)

2*f(4)-13 <= 13-f(3)
2*44-13 <= 13 — 12
75 <= 1 (неверно)

Таким образом выполнится команда writeln(i-1). На экране мы увидим 3

2. Определим, для каких k цикл

while f(i) < k:
    i += 1

выдаст i = 4 и при этом условие

if 2*f(i)-k <= k-f(i-1) then
writeln(i)
else
writeln(i-1);

не будет выполняться.

Видно, что k должно быть больше 12. Теперь определим верхнюю границу значений k.

Ранее мы посчитали, что f(4) = 44. Т.е. при k > 44 мы получим значение i = 5. Нам этого не нужно.

Т.о. k  может принимать значения от 13 до 44 и значение переменной i останется равном 3.

Несложно проверить, что для любого числа из [13; 44] условие

if 2*f(i)-k <= k-f(i-1) then
writeln(i)
else
writeln(i-1);

не будет выполняться. На экране увидим значение i-1 (4-1 = 3) равное 3.

Количество значений k в этом случае равно 32.

3. Теперь рассмотрим такие значения k, при которых наше условие

if 2*f(i)-k <= k-f(i-1) then
writeln(i)
else
writeln(i-1);

выполнит команду writeln(i)?, а не writeln(i-1). При этом i должна быть равна 3. Это возможно, если цикл

while f(i) < k do
i := i + 1;

завершит свою работу на третьем шаге (а не на четвертом) (см. табличку «Таблица. Работа цикла While«), а значение переменной i = 3 (а не 4).  Это возможно при значениях k от -1 до 12 (-1 <= k < 13)

Теперь нам необходимо, чтобы условие

if 2*f(i)-k <= k-f(i-1) then
writeln(i)
else
writeln(i-1);

выполнялось при i = 3.

Составим неравенство и решим его.

2*f(3)-k <= k-f(2)
2*12-k <= k + 2
24-2 <= 2*k
k >= 11

Получили систему неравенств: k >= 11 и -1 <= k < 13. Следует, что при k = 11 и при k = 12  мы в качестве результата работы программы также получим 3.

Это еще 2 значения.

Сложим: 32 + 2 = 34

Ответ: 34.