Задание 22. Графы. Подсчёт количества программ. ЕГЭ 2021 по информатике

Проанализируем, что происходит в результате выполнения данной программы. Для этого в качестве x рассмотрим произвольное целое число, входящее в диапазон типа объявленной переменной (в нашем случае −32768 ≤ x ≤ 32767), например, 412.

Заметим, что a принимает значение, равное сумме цифр числа x, а переменная b — наименьшей цифре числа x.

Из условия задачи имеем:

1) a = 15, значит, сумма цифр исходного числа x равна 15;

2) b = 7, значит, в исходном числе x наименьшая цифра равна 7.

В наименьшем из таких чисел x цифра, стоящая в старшем разряде, должна быть наименьшей, то есть 7 (мы определили, что эта цифра наименьшая в числе). Тогда сумма цифр, расположенных правее 7 равна 15 − 7 = 8. Так как 8 < 10, а нам требуется найти наименьшее число, то исходное число является двузначным, и в разряде единиц у него стоит 8.

Значит, числом x, удовлетворяющим условию задачи, является 78.

Решение на С++

for (int i = 1; i < 10000; ++i) {
    int x = i, a = 0, b = 0;
    while (x > 0){
        a++;
        if (x % 2 != 0) b++;
        x /= 2;
    }
    if (b == 3 && a == 7)
        cout << i << " "; // выводим то, что "вводили"
}

Проанализируем работу алгоритма.

На каждой итерации цикла значение переменной a увеличивается на 1.

Далее значение этой переменной не изменяется. Следовательно, по окончании работы программы значение переменной a будет равно количеству итераций цикла. Согласно условию a = 5.

Цикл выполняется до тех пор, пока значение переменной x > 0. На каждой итерации цикла переменная x с помощью оператора целочисленного деления на 2 (x:=x div 2) уменьшается в два раза. Так как a = 5, то исходное число не превышает 2⁵ = 32 и больше, чем 2⁴ = 16.

Условие x mod 2 = 0 проверяет, является ли число x чётным. В том случае, когда условие истинно, к переменной b прибавляется единица (b:=b+1). Следовательно, в результате работы алгоритма значение переменной b будет равно количеству чётных чисел, полученных в результате последовательного деления исходного числа x на 2.

Рассмотрим случай, когда исходное число x = 32. В этом случае будет выполнено 6 итераций цикла while, в результате переменная x будет последовательно принимать значения 32, 16, 8, 4, 2, 1. В результате выполнения алгоритма переменная a примет значение 6, переменная b — 5.

Если исходное число x = 31, то получим последовательность: 31, 15, 7, 3, 1. В этом случае получим a = 5, b = 0.

Далее, когда мы последовательно будем уменьшать исходное число x от 30 до 16, значение переменной a будет равно 5, а значение переменной b будет изменяться в диапазоне от 0 до 4.

Так при x = 30, получим последовательность: 30, 15, 7, 3, 1. В этом случае a = 5, b = 1.

При x = 29 получим последовательность: 29, 14, 7, 3, 1. В этом случае a = 5, b = 1.

При x = 28 получим последовательность: 28, 14, 7, 3, 1. В этом случае a = 5, b = 2.

Согласно условию требуется указать наибольшее из таких чисел x, при вводе которого после окончания выполнения алгоритма b = 2, a = 5. Искомым числом является 28.