5 задание ЕГЭ информатика на анализ алгоритмов

✎ 1 вариант решения:

• Введем обозначения:
• пусть x — это команда Вперед 5
• пусть y — это команда Назад 3
• Поскольку Кузнечик двигается с начала числовой оси (с 0) и в итоге достигает точки 21, то получим уравнение:

5x - 3y = 21  (-3y - поскольку двигаемся назад)

• Выразим x:

5x = 21 + 3y

• Чтобы выразить x необходимо будет правую часть уравнения разделить на 5. А поскольку x не может быть дробным числом, то делаем вывод, что правая часть должна делиться на 5 без остатка.
• Поскольку нам нужно получить наименьшее y, то будем подбирать y, начиная с 1:

у=1 -> 21+3 не делится на 5
у=2 -> 21+6 не делится на 5
у=3 -> 21+9 делится на 5

Результат: 3
 
✎ 2 вариант решения:

• Допустим, Кузнечик допрыгал до 21 (и дальше). Он это мог сделать только при помощи команды Вперед 5. Будем рассматривать числа > 21 и делящиеся на 5 без остатка (т.к. Вперед 5).
• Первое число большее 21 и делящееся на 5 без остатка — это 25.

25 - 3 (Назад 3)= 22  -> не 21

• Следующее такое число — 30.

30 - 3 - 3 - 3 = 21  -> получили 21!

• При этом была использована команда Назад 3 три раза.

Результат: 3

• Для того чтобы узнать количество обеих команд, необходимо ввести неизвестное x. Представим, что количество команд Вперед 3 было выполнено x раз, тогда количество команд Назад 2 было x+12 раз. Так как всего команд было 50 и других команд не было, то составим уравнение:

x + x + 12 = 50 команд

• Найдем x (количество команд Вперед 3):

2х = 50 - 12
x = 38/2 = 19

• Теперь найдем точку на числовой оси, в которой оказался Кузнечик. Учтем, что он 19 раз выполнил прыжок на три «шага» вперед и 19 + 12 раз прыгнул назад на 2 шага:

3 * 19 - 2 * (19 + 12) = 57 - 62 = -5

• -5 означает, что можно было переместиться в эту точку одной командой — Назад 5

Результат: Назад 5

• Поскольку число 2500 достаточно большое, поэтому разгадать, какими командами можно до него «дойти» сложно.
• В такого рода задачах следует начать решение с конца — с числа 2500, и каждый раз пытаться выполнить действие квадратный корень из числа (т.к. квадратный корень — операция обратная возведению в квадрат). Если квадратный корень не извлекается, будем выполнять обратную команду для первой команды — Вычти 1 (обратная для Прибавь 1):

2500: квадрат числа 50 -> операция 2
50: не является квадратом, значит, команда Отнять 1, получим 49 -> операция 1
49: квадрат числа 7  -> операция 2
7: не является квадратом, значит, команда Отнять 1, получим 6 -> операция 1
6: не является квадратом, значит, команда Отнять 1, получим 5 -> операция 1

• Запишем все команды в обратной последовательности и получим результат:

Результат: 11212

• В такого рода задачах иногда проще начать решение с конца — с числа 24, и каждый раз пытаться выполнить действие разделить на 5 (т.к. деление — операция обратная умножению). Если рассматриваемое число не делится целочисленно на 5, то будем выполнять обратную команду для первой команды — вычти 3 (обратная для прибавь 3):

24: не делится на 5, значит 24 - 3 = 21 -> операция 1
21: не делится на 5, значит 21 - 3 = 18 -> операция 1
18: не делится на 5, значит 18 - 3 = 15 -> операция 1
15: 15 / 5 = 3 -> операция 2

• Запишем все команды в обратной последовательности и получим результат: 2111.

Ответ: 2111

• Для выполнения первой команды переведем число в двоичную систему счисления:

19110 = 101111112

• Команда 1: Команда сдвинь вправо означает, что младший бит будет «утерян» (попадет в специальную ячейку — бит переноса), а в старший — добавится 0 (который является незначащим, значит, можно его не писать).

10111111 - > 1011111

• Команда 1: Еще раз повторим действие предыдущего пункта:

01011111 - > 101111

• Команда 2: Данную команду проще выполнить, переведя число в десятичную систему счисления:

1011112 -> 4710

• теперь прибавим 4:

47 + 4 = 51

• Команда 1: Опять переведем в двоичную систему счисления:

5110 = 1100112

• Выполним сдвиг:

110011 - > 11001

• Команда 1: Выполним сдвиг еще раз:

11001 - > 1100

• Команда 2: Переведем число в десятичную систему счисления и прибавим 4:

11002 -> 1210

12 + 4 = 16

Результат: 16
 
✎ 2 способ:

• При сдвиге вправо в старший бит попадает нуль, а младший бит отправляется в специальную ячейку – бит переноса, т. е. он будет «утерян». Таким образом, если число чётное, то при сдвиге оно уменьшается в два раза; если нечётное, — уменьшается в два раза ближайшее меньшее чётное число (либо исходное нечетное целочисленно делится на 2).
• Получим результаты выполнения последовательности команд:

команда 1: 191 -> 95
команда 1: 95 -> 47
команда 2: 47 -> 51
команда 1: 51 -> 25
команда 1: 25 -> 12
команда 2: 12 -> 16

Результат: 16

• Подставим по порядку выполняемые команды согласно номерам в последовательности команд. Для удобства будем использовать скобки:
  12112:

((((3+3)*х)+3)+3)*х = 120

• Получим квадратное уравнение:

6х2 + 6х - 120 = 0

• Решим его и получим результат:

x1=4; x2=-60/12

• Так как по заданию х — натуральное, то х2 нам не подходит.
• Подставим х1 в наше уравнение для проверки:

((((3+3)*4)+3)+3)*4 = 120

Все верно.

Результат: 4

Результат: 2949

Результат: 1

• Обозначим каждую цифру числа Y согласно заданию:

Y =    3       1       2
       x mod 7    x mod 2    x mod 5

• Сделаем выводы:

1. x mod 2 = 1 => значит, X — нечетное число
2. x mod 5 = 2 => значит, X — либо ?2, либо ?7.
3. раз x — нечетное, то из пред. пункта получаем x = ?7
4. x mod 7 = 3 => переберем все варианты:

97 - не подходит, 
87 - подходит (87 / 7 = 12, остаток = 3)
77 - не подходит,
67 - не подходит,
57 - не подходит,
47 - не подходит,
37 - не подходит,
27 - не подходит,
17 - подходит (17 / 7 = 2, остаток = 3)

Результат: 2

• Заметим, что после выполнения второго пункта задания, будут получаться только четные числа! Наименьшим возможным четным числом, превышающим 129, является число 130. С ним и будем работать.
• Переведем 130 в двоичную систему счисления:

13010 = 100000102

• Это двоичное число получилось из исходного двоичного, после того как дважды был добавлен остаток от деления суммы цифр на 2. Т.е.:

в обратном порядке:
было 1000001 -> стало 10000010 
еще раз то же самое: 
было 100000 -> стало 1000001 

• Значит, необходимое нам двоичное число — это 100000.
• Переведем 100000 в 10-ю систему:

1000002 = 3210

• Так как по условию у нас 4*N, то 32 делим на 4 — > 8.

Результат: 8

• Заметим, что после второго пункта условия задачи получаются только четные числа (т.к. если число в двоичной системе заканчивается на 0, то оно четное). Таким образом, нас будут интересовать только четные числа.
• Наименьшим возможным числом, превышающим 83, является число 84. С ним и будем работать.
• Переведем 84 в двоичную систему счисления:

84 = 1010100

• В данном числе выделенная часть — это N. Значит, необходимое нам двоичное число — это 10101. После первого пункта задачи к данному числу должна была добавиться справа единица, так как оно нечетное. А мы имеем 0. Соответственно, это оно не подходит.
• Возьмем следующее четное число — 86. Переведем его в двоичную систему счисления:

86 = 1010110

• В данном числе выделенная часть — это N. Значит, необходимое нам двоичное число — это 10101. После первого пункта задачи к данному числу должна была добавиться справа единица, так и есть: 101011. А затем добавляется 0: 1010110. Соответственно, оно подходит.

Результат: 86

• Поскольку требуется найти наибольшее число, то возьмем наибольшее из возможных чисел, которые < 100 — это число 99. Переведем его в двоичную систему:

99 = 11000112

• По алгоритму это число получилось путем добавления справа двух разрядов, значение которых зависит от исходного N:

1100011
  N    

• Т.е. в конце были добавлены две единицы — по алгоритму это значит, что исходное N должно в остатке при делении на 4 давать 3. Переведем найденное N в десятичную систему:

11000 = 2410

• 24 делится на 4 нацело, т.е. в конце по алгоритму должны были добавиться два разряда — 00. У нас же в конце 11. Т.е. число 99 не подходит. Проверим следующее — 98.

98 = 11000102  : 10 в конце добавлено алгоритмом
N = 110002 = 2410
24 делится нацело на 4. 
По алгоритму в конце должно быть 00, а мы имеем 10 
98 - не подходит

97 = 11000012 : 01 в конце добавлено алгоритмом
N = 110002 = 2410
24 делится нацело на 4. 
По алгоритму в конце должно быть 00, а мы имеем 01 
97 - не подходит

96 = 11000002 : 00 в конце добавлено алгоритмом
N = 110002 = 2410
24 делится нацело на 4. 
По алгоритму в конце должно быть 00, у нас 00 - верно!
96 - подходит!

Результат: 96

• В постановке задания задано R > 114. R — это результат работы алгоритма. Для того, чтобы определить наименьшее возможно N, переведем сначала 114 в двоичную систему счисления и выделим в нем три добавленные по алгоритму цифры:

114 = 11100102

• Проанализируем, как могло бы получиться двоичное число 114 (R) по алгоритму:

2. В полученное числе N = 1110 дублируется последняя цифра и получается 11100.
3. Поскольку число единиц (3) — нечетное, то справа добавляется 1: 111001.
4. Т.к. в полученном наборе цифр четное число единиц, то добавляем 0: 1110010

• Поскольку из числа N = 1110 по алгоритму могла получиться только такая последовательность цифр (1110010), то для получения минимального R, но большего чем R = 114, увеличим в N = 1110 самый младший разряд на единицу и рассмотрим работу алгоритма с полученным числом:

1. N = 1110 + 1 = 1111

Работа по алгоритму:
2. 11111 - дублирование последней цифры.
3. 111111 - справа дописываем единицу, т.к. в полученном числе 5 единиц (нечетное)
4. 1111110 - дописываем ноль, т.к. в полученном числе четное число единиц.

• Ответ нужно получить в десятичной системе счисления:

min R = 11111102 = 12610

Результат: 126

• Результатом выполнения алгоритма является число 45. Алгоритм работает в двоичной системе счисления, поэтому переведем число:

45 = 001011012

• Пронумеруем биты слева направо, начиная с единицы. Рассмотрим каждый бит отдельно, начиная с левого бита под номером 1.
• 1. Так как биты в уменьшаемом и вычитаемом должны быть различны, то единица в результате может получится только 1 - 0, с учетом, что у разряда с единицей заняли. То есть бит:

   .
_  1 _ _ _ _ _ _ _    N инвертируемое
=  0 _ _ _ _ _ _ _    N исходное
   0 0 1 0 1 1 0 1  = 45   результат

• 2. 1 - 0 не может в результате дать 0, так как у следующей слева единицы мы заняли. Значит, 0 - 1. Чтобы не получить единицу в ответе, необходимо у нуля тоже занять:

   . .
_  1 0 _ _ _ _ _ _ 
=  0 1 _ _ _ _ _ _ 
   0 0 1 0 1 1 0 1  = 45   результат

• 3. 1 - 0 не может быть, так как у следующего слева нуля мы заняли.
  Значит 0 - 1. То есть как раз чтобы получить единицу (10 - 1 = 1), занимаем у следующих слева разрядов:

   . .
_  1 0 0 _ _ _ _ _ 
=  0 1 1 _ _ _ _ _ 
   0 0 1 0 1 1 0 1  = 45   результат

• 4. 0 - 1 не может быть. Значит, чтобы получить в результате ноль, берем 1 - 0, у единицы должно быть занято.

   . .   .
_  1 0 0 1 _ _ _ _ 
=  0 1 1 0 _ _ _ _ 
   0 0 1 0 1 1 0 1  = 45   результат

• 5. 1 - 0 не может быть. Так как слева у единицы занято. Значит, чтобы получить в результате 1, берем 0 - 1:

   . .   .
_  1 0 0 1 0 _ _ _ 
=  0 1 1 0 1 _ _ _ 
   0 0 1 0 1 1 0 1  = 45   результат

• 6. 0 - 1 не даст в ответе единицу, значит, имеем 1 - 0:

   . .   .
_  1 0 0 1 0 1 _ _ 
=  0 1 1 0 1 0 _ _ 
   0 0 1 0 1 1 0 1  = 45   результат

• 7. 0 - 1 не может быть, значит, 1 - 0. Чтобы получить в результате 0, необходимо, чтобы у 1 было занято:

   . .   .     .
_  1 0 0 1 0 1 1 _ 
=  0 1 1 0 1 0 0 _ 
   0 0 1 0 1 1 0 1  = 45   результат

• 8. Чтобы получить 1, имеем 0 - 1:

   . .   .     .
_  1 0 0 1 0 1 1 0 
=  0 1 1 0 1 0 0 1
   0 0 1 0 1 1 0 1  = 45   результат

• Полученное число (вычитаемое) и есть искомое N. Переведем его в 10-ю с.с.:

01101001 = 10510

Ответ: 105