6. Анализ и построение алгоритмов

Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам.
1. Складываются первая и вторая, а также вторая и третья цифры исходного
числа.
2. Полученные два числа записываются друг за другом в порядке убывания
(без разделителей).
Пример. Исходное число: 348. Суммы: 3 + 4 = 7; 4 + 8 = 12. Результат: 127.
Укажите наименьшее число, в результате обработки которого автомат выдаст число 1711.

Демонстрационный вариант Единый государственный экзамен ЕГЭ 2017 г. – задание №6

Решение:

Исходное число: ABC

Так как ищем наименьшее число, то и начинать будем с наименьшей суммы (11), чтобы получить наименьшую первую цифру.

A+B=11 -> A=2, B=9

Число 17 получается как сумма 9 и 8:

B+C=17 ->B=9, C=8

Теперь составляем искомое наименьшее трехзначное число и получаем 298.

Ответ: 298

Демонстрационный вариант Единый государственный экзамен ЕГЭ 2016 г. – задание №6 а

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1. Строится двоичная запись числа N.

2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число N, для которого результат работы
алгоритма больше 125. В ответе это число запишите в десятичной системе счисления.

Ответ:

Решение:

  • Бит чётности – это дополнительный контрольный бит, который добавляется к двоичному коду так, чтобы количество единиц в полученном двоичном коде стало чётным; если в исходном коде уже было чётное количество единиц, дописывается 0, если нечётное – дописывается 1.
  • при добавлении к двоичной записи числа нуля справа число увеличивается в 2 раза

В пунктах а и б дважды приписывается бит четности, то есть после пункта а количество единиц всегда будет четным, а в б дописывается ноль, следовательно, число увеличивается вдвое.

По условию, мы должны получить четное число, большее(>)125. Нам подходят числа: 126, 128, 130…

Проверим число 126: после пункта б это число увеличилось в 2 раза, следовательно число в пункте а было равно 63. Запишем данное число в двоичной системе счисления: 6310 = 1111112. 

Замечаем, что число 63 содержит четное количество единиц, значит по условию в пункте а, мы добавили к исходному числу бит четности и получили число 63. Таким образом, первоначальное число 111112 = 3110.

Ответ: 31

 Демонстрационный вариант Единый государственный экзамен ЕГЭ 2016 г. – задание №6 б

У исполнителя Калькулятор две команды, которым присвоены номера:

1. прибавь 2,
2. умножь на 5.

Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, а выполняя вторую, умножает его на 5.

Например, программа 2121 – это программа
умножь на 5,
прибавь 2,
умножь на 5,
прибавь 2,
которая преобразует число 1 в число 37.

Запишите порядок команд в программе, которая преобразует число 2 в число 24 и содержит не более четырёх команд. Указывайте лишь номера команд.

 

Решение:

Такие задания легче решать с помощью обратного исполнителя:

1) Вычитаем 2

2) Делим на 5 ( только для чисел, оканчивающихся на 0 и 5)

Будем использовать следующий алгоритм: если число не делится на 5 , вычитаем 2 (команда 1); если число делится на 5, выполняется соответственно команда 2:

24-2=22 1

22-2=20 1

20:5=4 2

4-2=2 1

Таким образом, выполняя программу 1121,  получаем число 2 из 24. Записываем в обратном порядке, так как решали с помощью обратного исполнителя = 1211.

Ответ: 1211

Для составления цепочек используются бусины, помеченные буквами: A, B, C, D, E. На первом месте в цепочке стоит одна из бусин A, C, E. На втором – любая гласная, если первая буква согласная, и любая согласная, если первая гласная. На третьем месте – одна из бусин C, D, E, не стоящая в цепочке на первом месте. Какая из перечисленных цепочек создана по этому правилу?

1) CBE   2) ADD  3) ECE   4) EAD

Решение:

На втором – любая гласная, если первая буква согласная, и любая согласная, если первая гласная.

2) ADD  3) ECE

На третьем месте – одна из бусин C, D, E, не стоящая в цепочке на первом месте.

2) ADD

Ответ: 2

Джентльмен пригласил даму в гости, но вместо кода цифрового замка своего подъезда отправил ей такое сообщение: «В последовательности 52186 все четные цифры нужно разделить на 2, а из нечетных вычесть 1. Затем удалить из полученной последовательности первую и последнюю цифры». Определите код цифрового замка.

1) 104    2) 107    3) 218    4) 401

Решение:

 

Все четные цифры нужно разделить на 2, а из нечетных вычесть 1.

52186

41043

Затем удалить из полученной последовательности первую и последнюю цифры

104

Ответ: 1

Вася забыл пароль к Windows, но помнил алгоритм его получения из строки подсказки «23ABN12QR8N»: если последовательности символов «AB» и «QR» поменять местами, а затем из получившейся строки удалить все символы «N», то полученная последовательность и будет паролем. Определите пароль:

1) 23AB12QR8   2) 23QR12AB8   3) 23QRAB8        4) 23QR128

Решение:

 

если последовательности символов «AB» и «QR» поменять местами

23ABN12QR8N – 23QRN12AB8N

а затем из получившейся строки удалить все символы «N»

23QR12AB8

Ответ: 2

Пятизначное число формируется из цифр 0, 1, 3, 5, 7, 9. Известно, что число строится по следующим правилам: а) число делится без остатка на 10; б) модуль разности любых двух соседних цифр не менее 1. Какое из следующих чисел удовлетворяет всем условиям?

1) 56710                  2) 19910                     3) 75310                     4) 11110

Решение:

 

Пятизначное число формируется из цифр 0, 1, 3, 5, 7, 9.

2) 19910                     3) 75310                     4) 11110

Модуль разности любых двух соседних цифр не менее 1.

3) 75310

Ответ: 3

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

  1. Записывается результат сложения старших разрядов этих чисел.
  2. К нему дописывается результат сложения средних разрядов по такому правилу: если он меньше первой суммы, то полученное число приписывается к первому слева, иначе – справа.
  3. Итоговое число получают приписыванием справа к числу, полученному после второго шага, сумму значений младших разрядов исходных чисел.

Какое из перечисленных чисел могло быть построено по этому правилу?

1) 141215            2) 121514            3) 141519            4) 112112

Решение:

1) 141215            2) 121514            3) 141519            4) 112112

 

Сумма двух цифр не может быть больше, чем 18.

1) 141215            2) 121514

Со 2-го правила, мы понимаем, что номер на 1-й и 2-го разрядов должно быть меньше, чем число на 3-й и 4-й разрядов.

2) 121514

Ответ: 2

Автомат получает на вход четырехзначное десятичное число. По этому числу строится новое число по следующим правилам

  1. Складываются первая и вторая, а также третья и четвёртая цифры
  2. Полученные два числа записываются друг за другом в порядке возрастания (без разделителей)

Пример. Исходное число: 8754. Суммы: 8+7 = 15; 5+4 = 9. Результат: 915.

Определите, какое из следующих чисел может быть результатом работы автомата

1) 219                      2) 118                                3) 1411                        4) 151

Решение:

1) 219                      2) 118                                3) 1411                        4) 151

Сумма двух цифр не может быть больше, чем 18. Полученные два числа записываются друг за другом в порядке возрастания

2) 118

Ответ: 2

Учитель предложил детям потренироваться в действиях с шестнадцатеричными цифрами и поиграть в такую игру. Учитель предлагает детям три шестнадцатеричные цифры. Ученики должны сначала найти разность первой и второй цифр, потом — разность второй и третьей цифр. Обе разности должны быть записаны, как десятичные числа. Затем эти числа записываются друг за другом в порядке невозрастания (правое число меньше или равно левому).

Пример. Исходные цифры: A, A, 3. Разности: A16 – A16 = 0; A16 – 316 = 10 – 3 = 7. Результат: 70. Укажите, какое из следующих чисел может быть получено в результате.

1) 131                      2) 133                                3) 212                          4) D1

Решение:

 

1) 131                      2) 133                                3) 212                          4) D1

Обе разности должны быть записаны, как десятичные числа. Затем эти числа записываются друг за другом в порядке невозрастания.

1) 131                      2) 133

Разница между первой и второй разрядов составляет 13, поэтому мы предполагаем, что числа F (15) и 2.

F2?

Третья цифра не может быть больше, чем 2.

1) 131

Ответ: 1

Автомат получает на вход четырёхзначное число. По этому числу строится новое число по следующим правилам.

  1. Складываются первая и вторая, а также третья и четвёртая цифры исходного числа.
  2. Полученные два числа записываются друг за другом в порядке возрастания (без разделителей).

Пример. Исходное число: 3165. Суммы: 3 + 1 = 4; 6 + 5 = 11. Результат: 411.

Укажите минимальное число, в результате обработки которого, автомат выдаст число 79.

Решение:

Четырёхзначное число – abcd

a+b = 7 – минимальное число: a=1, b=6

c+d = 9 – минимальное число: c=0, d=9

abcd = 1609

Ответ: 1609

Автомат получает на вход четырёхзначное число. По этому числу строится новое число по следующим правилам.

  1. Складываются первая и третья, а также вторая и четвёртая цифры исходного числа.
  2. Полученные два числа записываются друг за другом в порядке возрастания (без разделителей).

Пример. Исходное число: 3165. Суммы: 3 + 6 = 9; 1 + 5 = 6. Результат: 69.

Укажите максимальное число, в результате обработки которого, автомат выдаст число 35.

Решение:

Четырёхзначное число – abcd

a+c = 5 – максимальное число: a=5, c=0

b+d = 3 – максимальное число: b=3, d=0

abcd = 5300

Ответ: 5300

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1) Строится двоичная запись числа N.

2) К этой записи дописываются справа ещё два разряда по следующему правилу:

а) в конец числа (справа) дописывается 1, если число единиц в двоичной записи числа чётно, и 0, если число единиц в двоичной записи числа нечётно.

б) к этой записи справа дописывается остаток от деления количества единиц на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число R, которое превышает 31 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе.

Решение:

Минимальное число R, которое превышает 31. Давайте попробуем число 32.

32 = 1000002 (дописываются справа ещё два разряда)

N = 10002

2.a) в конец числа (справа) дописывается 0, если число единиц в двоичной записи числа нечётно.

100002

2. б) к этой записи справа дописывается остаток от деления количества единиц на 2.

1000012 = 33

Ответ: 33

Исполнитель КАЛЬКУЛЯТОР имеет только две команды, которым присвоены номера:

  1. Умножь на 2
  2. Вычти 2

Выполняя команду номер 1, КАЛЬКУЛЯТОР умножает число на экране на 2, а выполняя

команду номер 2, вычитает из числа на экране 2. Напишите программу, содержащую не

более 5 команд, которая из числа 7 получает число 44. Укажите лишь номера команд.

Например, программа 11221 – это программа:

  • Умножь на 2;  
  • Умножь на 2;
  • Вычти 2;
  • Вычти 2;
  • Умножь на 2,

которая преобразует число 5 в число 32.

Решение:

7 14 12 24 22 44
1 2 1 2 1

Ответ: 12121

У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера:

  1. сдвинь вправо
  2. прибавь 4

Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд вправо, а выполняя вторую, добавляет к нему 4. Исполнитель начал вычисления с числа 191 и выполнил цепочку команд 112112. Запишите результат в десятичной системе.

Решение:

исполнитель сдвигает число на один двоичный разряд вправо = число делится на 2.

191 – 112112

1 1 2 1 1 2
191/2=95 95/2=47 47+4=51 51/2=25 25/2=12 12+4=16

Ответ: 16

Исполнитель Робот ходит по клеткам бесконечной вертикальной клетчатой доски, переходя по одной из команд вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. Робот выполнил следующую программу:

влево
вверх
вверх
влево
вниз
вправо
вправо
вправо

Укажите наименьшее возможное число команд в программе, Робота из той же начальной клетки в ту же конечную.

Решение:

Ответ: 2

Исполнитель Робот действует на клетчатой доске, между соседними клетками которой могут стоять стены. Робот передвигается по клеткам доски и может выполнять команды 1 (вверх), 2 (вниз), 3 (вправо) и 4 (влево), переходя на соседнюю клетку в направлении, указанном в скобках. Если в этом направлении между клетками стоит стена, то Робот разрушается.  Робот успешно выполнил программу

 33233241

Какую последовательность из четырех команд должен выполнить Робот, чтобы вернуться в ту клетку, где он был перед началом выполнения программы, и не разрушиться вне зависимости от того, какие стены стоят на поле?

Решение:

Ответ: 4144

Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 0. Система команд Кузнечика:

Вперед 5 – Кузнечик прыгает вперёд на 5 единиц,

Назад 3 – Кузнечик прыгает назад на 3 единицы.

Какое наименьшее количество раз должна встретиться в программе команда «Назад 3», чтобы Кузнечик оказался в точке 21?

Решение:

5.6 = 30

30 – 3.3 = 21

Ответ: 3

Исполнитель КАЛЬКУЛЯТОР имеет только две команды, которым присвоены номера:

  1. Прибавь 1
  2. Умножь на 2

Выполняя команду номер 1, КАЛЬКУЛЯТОР прибавляет к числу на экране 1, а выполняя

команду номер 2, умножает число на экране на 2. Укажите минимальное число команд, которое должен выполнить исполнитель, чтобы получить из числа 19 число 629.

Решение:

 

629 – 1 = 628 : 1

628 / 2 = 314 :  2

314 / 2 = 157 :  2

157 – 1 = 156 :  1

156 / 2 = 78 :  2

78 / 2 = 39 :  2

39 – 1 = 38 :  1

38 / 2 = 19 :  2

Ответ: 8

У исполнителя Аккорд две команды, которым присвоены номера:

  1. прибавь x
  2. умножь на 2

где x – неизвестное положительное число. Выполняя первую из них, Аккорд добавляет к числу на экране x, а выполняя вторую, умножает это число на 2.

Программа для исполнителя Аккорд – это последовательность номеров команд.

Известно, что программа 12121 переводит число 4 в число 65. Определите значение x.

Решение:

12121

2.(2.(4+x)+x)+x=65

2.(8+3x)+x=65

16+6x+x=65

7x=49

x=7

Ответ: 7