Задачи с циклами и ветвлениями

Задача №20 единого государственного экзамена по информатике предполагает проверку умений восстановить входные данные по результату работы программы, содержащей цикл и ветвления.

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

Задача №20. Ниже записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: a и b. Укажите наименьшее из таких чисел x, при вводе которого алгоритм печатает сначала 3, а потом 2.

Задача 20 ЕГЭ

Решение.

Раccмотрим в общих чертах программу:

  1. В программу вводится число х. Переменным a и b присваивается значение 0.
  2. В цикле с предусловием исполняется ряд инструкций.
  3. После выполнения цикла значения a и b (3 и 2 соответственно) выводится на экран.

Разберем работу цикла

  1. Цикл будет выполняться пока условное выражение x > 0 - истинно.
  2. В инструкции a = a + 1 при каждой итерации значение а увеличивается на 1. Значит, a – счетчик числа выполнений тела цикла.
  3. Если в инструкции if условное выражение (b < x % 8) истинно, то переменной b присваивается значение остатка от деления х на 8. Значит, в b будет хранится текущее значение, удовлетворяющее условию b < x % 8.
  4. В конце каждой итерации в переменную х записывается результат целочисленного деления x/8.

Перейдем к анализу выходных данных:

  1. Так как а = 3, то тело цикла выполнилось ровно три раза.
  2. b = 2 - наибольший остаток от целочисленного деления текущего значения x на 8 (при выполнении условия b < x % 8)

Выясним, какое наименьшее из чисел x будет удовлетворять выходным данным программы:

  1. Минимальное десятичное число, при котором тело данного цикла выполнится трижды, равно
    1•82 + 0•81 + 0•80 = 64.
    Но для данного числа в переменную b будет записана 1.
  2. Очевидно, цифра 2 должна быть в крайнем правом разряде числа. Поэтому искомое число
    1•82 + 0•81 + 2•80 = 66