Задачи с циклами и ветвлениями
Задача №20 единого государственного экзамена по информатике предполагает проверку умений восстановить входные данные по результату работы программы, содержащей цикл и ветвления.
Рассмотрим ниже задачи, относящиеся к данному типу, и разберем способы их решения.
Задача №20. Ниже записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: a и b. Укажите наименьшее из таких чисел x, при вводе которого алгоритм печатает сначала 3, а потом 2.
Решение.
Раccмотрим в общих чертах программу:
- В программу вводится число х. Переменным a и b присваивается значение 0.
- В цикле с предусловием исполняется ряд инструкций.
- После выполнения цикла значения a и b (3 и 2 соответственно) выводится на экран.
Разберем работу цикла
- Цикл будет выполняться пока условное выражение x > 0 - истинно.
- В инструкции a = a + 1 при каждой итерации значение а увеличивается на 1. Значит, a – счетчик числа выполнений тела цикла.
- Если в инструкции if условное выражение (b < x % 8) истинно, то переменной b присваивается значение остатка от деления х на 8. Значит, в b будет хранится текущее значение, удовлетворяющее условию b < x % 8.
- В конце каждой итерации в переменную х записывается результат целочисленного деления x/8.
Перейдем к анализу выходных данных:
- Так как а = 3, то тело цикла выполнилось ровно три раза.
- b = 2 - наибольший остаток от целочисленного деления текущего значения x на 8 (при выполнении условия b < x % 8)
Выясним, какое наименьшее из чисел x будет удовлетворять выходным данным программы:
- Минимальное десятичное число, при котором тело данного цикла выполнится трижды, равно
1•82 + 0•81 + 0•80 = 64.
Но для данного числа в переменную b будет записана 1. - Очевидно, цифра 2 должна быть в крайнем правом разряде числа. Поэтому искомое число
1•82 + 0•81 + 2•80 = 66