Задание 20. Программирование: циклы и ветвления

20 задание демоверсия ЕГЭ 2018 информатика:Ниже записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: L и M. Укажите наименьшее число x, при вводе которого алгоритм печатает сначала 5, а потом 7.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

var x, L, M: integer;
begin
readln(x);
L := 0;
M := 0;
while x>0 do
begin
  M := M + 1;
  if x mod 2 <> 0 then
     L := L + 1;
  x := x div 2;
end;
writeln(L);
writeln(M);
end.
    Для начала рассмотрим алгоритм программы:
    • В начале программы вводится x, и обнуляются две переменные — L и M.
    • Далее следует цикл, который зависит от переменной x: пока x>0 выполняется тело цикла.
    • В теле цикла каждый его шаг происходит увеличение переменной M на единицу. Т.е. переменная M — это счетчик, соответственно, его значение по завершению работы цикла будет соответствовать количеству шагов цикла.
    • В конце программы печатается сначала L, потом M. Т.е. L должно быть равно 5, а M = 7. Раз M будет равно 7, то из предыдущего пункта видим, что цикл имеет 7 шагов, т.е. 7 итераций.
    • L — это тоже счетчик, но из условия if x mod 2 <> 0 видим, что счетчик L подсчитывает количество нечетных промежуточных x. Т.е. x в цикле постоянно меняется, а L проверяет x и в случае нечетного значения увеличивается на единицу. В программе L должно стать 5.
    • В цикле x делится целочисленно на 2: x := x div 2
    • Поскольку цикл завершит работу, когда x = 0, то последним шагом будет x = 1 div 2 = 0. Т.е. в предпоследнем шаге x = 1.
    • Решим данную задачу с конца, проследив все итерации цикла. Получается, что из предыдущего шага в следующий шаг x изменяется по двум правилам, назовем их командами:
1. x*2 -> если предыдущий x - четный, 
например 4 div 2 - обратное действие 2*2 = 4

2. x*2+1 -> если предыдущий x - нечетный, 
например 5 div 2 - обратное действие 2*2+1 = 5
    • Так как L в результате равно 5, значит в программе 5 команд № 2 и 2 команды №1 (7-5 = 2)
    • Нарисуем дерево команд и получающиеся значения, начиная с последней итерации цикла до начальной итерации. Т.е. начнем с завершения цикла, когда x стал = 0:

1-120

  • Вниз уходят команды, дающие четные значения x, а вверх — нечетные. Поскольку нам необходимо найти наименьший x, то «выгоднее» проследить нижние ветви дерева, т.к. они в результате дают меньшие значения.
  • Из дерева видим, что первая команда — это команда 2. В итоге осталось 4 команды № 2 и 2 команды № 1.
  • Нам выгодно с самого начала «двигаться» по дереву, используя команды 1 (чтобы x был наименьшим). Поэтому вторая и третья ветвь будут соответствовать команде 1. Поскольку первых команд должно быть только две, остальные команды будут №2.
  • Итого получаем следующий путь по дереву, в результате которого x становится равным 79.

Результат: 79