Задание 6. Алгоритмы. Анализ алгоритмов с числами и системами счисления. ЕГЭ 2020 по информатике
Средний процент выполнения: 58%
Ответом к заданию 6 по информатике может быть цифра (число) или слово.
Задачи для практики
Задача 1
У исполнителя Вычислитель есть две команды, которым присвоены номера:
1) Прибавь 7;
2) Раздели на 3.
Первая из них увеличивает число на экране на 7, вторая — делит его на 3 (в случае, если число делится без остатка). Запишите порядок команд в программе получения из числа 2 числа 5, содержащей не более 6 команд, указывая лишь номера команд.
Например, последовательность цифр 12112 соответствует программе, состоящей из команд Вычислителя, записанных в следующем порядке:
Прибавь 7
Раздели на 3
Прибавь 7
Прибавь 7
Раздели на 3
Последовательность этих команд преобразует число 5 в число 6.
Решение
Число 2 не делится на 3 без остатка, следовательно, первой будет выполняться команда 1 — прибавь 7. В результате получим число 9. Рассуждая далее аналогичным образом, запишем возможные преобразования в виде дерева переходов от одного числа к другому, где над стрелками указаны номера команд.
Анализируя полученные преобразования, получаем, что, используя не более 6 команд, из числа 2 число 5 можно получить в результате выполнения последовательности команд 122112.
Задача 2
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится троичная запись числа N.
2) К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры троичной записи, и остаток от деления суммы на 3 дописывается в конец числа (справа). Например, запись 2102 преобразуется в запись 21022;
б) над этой записью производятся те же действия: справа дописывается остаток от деления суммы цифр на 3.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является троичной записью искомого числа R. Укажите минимальное число R, которое превышает 82 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе.
Решение
1) Проанализируем работу алгоритма. А именно рассмотрим, какие цифры могут быть дописаны к исходному числу в результате его работы. Заметим, что возможные остатки от деления на 3 могут быть равны 0, 1 или 2.
Остаток 0 может быть получен только в случае, когда сумма цифр делится на 3. В этом случае после второго шага алгоритма также будет получен 0. В результате работы алгоритма последними двумя разрядами в полученном числе будут 00.
Остаток 1 может быть получен только в случае, когда сумма цифр может быть представлена в виде 3k + 1, где k —натуральное число. В этом случае после второго шага алгоритма будет получено число на 1 больше предыдущего, то есть представимое в виде 3k + 1 + 1 = 3k + 2. Остаток от деления на 3 такого числа равен 2. В результате работы алгоритма последними двумя разрядами в полученном числе будут 12.
Остаток 2 может быть получен только в случае, когда сумма цифр может быть представлена в виде 3k + 2, где k —натуральное число. В этом случае после второго шага алгоритма будет получено число на 2 больше предыдущего, то есть представимое в виде 3k+2+2 = 3k+3+1 = 3k1+1.
Остаток от деления на 3 такого числа равен 1. В результате работы алгоритма последними двумя разрядами в полученном числе будут 21.
2) По условию задачи требуется найти наименьшее число, превышающее 82. Возьмём наименьшее возможное число 83. Рассмотрим, может ли быть это число результатом работы алгоритма. Переведём это число в троичную систему счисления 8310 = 34 + 2 = 100023. Согласно алгоритму, последние две цифры 02 этого числа были приписаны к исходному. Согласно рассуждений, приведённых выше, такие числа не могут быть дописаны в результате работы алгоритма.
Построим упорядоченную возрастающую последовательность троичных чисел, начиная с числа 10002, в которой каждое последующее двоичное число на 1 больше предыдущего: 10002, 10010, 10011, 10012, 10020 . . . .
Для поиска числа R среди этой последовательности, будем искать наименьшее, в котором сумма цифр (за исключением двух последних) кратна 3 и число оканчивается на 00, или сумма цифр (за исключением двух последних) при делении на 3 даёт в остатке 1 и число оканчивается на 12, или сумма цифр (за исключением двух последних) при делении на 3 даёт в остатке 2 и число оканчивается на 21. Таким числом является 10012.
Переведём это число в десятичную систему счисления 100123 = 1 · 34 + 0 · 33 + 0 · 32 + 1 · 31 + 2 · 30 = 81 + 3 + 2 = 86.
Задача 3
Автомат получает на вход трёхзначное число. Из этого числа строится новое число по следующим правилам.
1) Вычисляются два числа — сумма первой и второй цифр, сумма второй и третьей цифр.
2) Полученные числа записываются в порядке возрастания (без разделителей).
Пример. Исходное число: 915. Сумма первой и второй цифр — 10. Сумма второй и третьей цифр — 6. Результат: 610.
Укажите наибольшее число, в результате обработки которого автомат выдаст число 1316.
Решение
Полученное в результате выполнения алгоритма число следует разбить на два числа, каждое из которых не превосходит 18 (согласно алгоритму, выполняется только поразрядное суммирование, а сумма любых двух цифр не превосходит 18).
Число 1316 можно разбить на числа 13 и 16.
Наибольшее число будем строить, начиная со старшего разряда. На первое место искомого числа поставим наибольшую цифру.
Для этого из чисел 13 и 16 выберем наибольшее 16 и представим его в виде суммы 9 + 7. Если число 9 поставить на первое место искомого числа, то цифра 7 будет стоять на втором месте (в разряде десятков). Но тогда в разряде единиц должно быть число 13 − 7 = 6. Значит, младшей цифрой искомого числа будет 6. Итак, наибольшим числом, в результате обработки которого автомат выдаст число 1316, является 976.
Задача 4
Автомат получает на вход четырёхзначное число. Из этого числа строится новое число по следующим правилам.
1. Вычисляются три числа—сумма первой и второй цифр, сумма второй и третьей цифр и сумма третьей и четвёртой цифр.
2. Полученные три числа записываются друг за другом в порядке возрастания (без разделителей).
Пример. Исходное четырёхзначное число: 7348. Сумма первой и второй цифр — 10. Сумма второй и третьей цифр — 7. Сумма третьей и четвёртой цифр—12. Результат: 71012.
Укажите наибольшее число, в результате обработки которого автомат выдаст число 81016.
Решение
Задача 5
Автомат получает на вход четырёхзначное число. Из этого числа строится новое число по следующим правилам.
1. Вычисляются три числа—сумма первой и второй цифр, сумма второй и третьей цифр и сумма третьей и четвёртой цифр.
2. Полученные три числа записываются друг за другом в порядке неубывания (без разделителей).
Пример. Исходное четырёхзначное число: 7348. Сумма первой и второй цифр — 10. Сумма второй и третьей цифр — 7. Сумма третьей и четвёртой цифр — 12. Результат: 71012.
Укажите наименьшее число, в результате обработки которого автомат выдаст число 51117.
Решение
Задача 6
Автомат получает на вход четырёхзначное число. Из этого числа строится новое число по следующим правилам.
1. Вычисляются три числа—сумма первой и второй цифр, сумма второй и третьей цифр и сумма третьей и четвёртой цифр.
2. Полученные три числа записываются друг за другом в порядке неубывания (без разделителей).
Пример. Исходное четырёхзначное число: 7348. Сумма первой и второй цифр — 10. Сумма второй и третьей цифр — 7. Сумма третьей и четвёртой цифр—12. Результат: 71012.
Укажите наибольшее число, в результате обработки которого автомат выдаст число 71115.
Решение
Задача 7
Автомат получает на вход четырёхзначное число. Из этого числа строится новое число по следующим правилам.
1. Вычисляются три числа—сумма первой и второй цифр, сумма второй и третьей цифр и сумма третьей и четвёртой цифр.
2. Полученные три числа записываются друг за другом в произвольном порядке (без разделителей).
Пример. Исходное четырёхзначное число: 7348. Сумма первой и второй цифр — 10. Сумма второй и третьей цифр — 7. Сумма третьей и четвёртой цифр—12. Результат: 12107.
Укажите наименьшее число, в результате обработки которого автомат выдаст число 16119.
Решение
Задача 8
Автомат получает на вход два трёхзначных числа. По этим числам строится новое число по следующим правилам.
1. Записывается результат сложения значений средних разрядов заданных чисел.
2. Если полученная сумма больше десяти, то справа от этой суммы дописывается результат сложения значений старших разрядов заданных чисел, в противном случае—слева.
3. Итоговое число получают приписыванием слева к полученному после второго шага числу суммы значений младших разрядов исходных чисел.
Пример. Исходные трёхзначные числа: 728, 536. Поразрядные суммы: 12, 5, 14. Результат: 14125.
Известно, что одним из чисел, подаваемых на вход автомата, является 368. Укажите второе число, подаваемое на вход автомата, если в результате автомат выдаёт число 9145.
Решение
Задача 9
Автомат получает на вход два трёхзначных числа. По этим числам строится новое число по следующим правилам.
1. Записывается результат сложения значений средних разрядов заданных чисел.
2. Если полученная сумма больше десяти, то справа от этой суммы дописывается результат сложения значений старших разрядов заданных чисел, в противном случае — слева.
3. Итоговое число получают приписыванием слева к полученному после второго шага числу суммы значений младших разрядов исходных чисел.
Пример. Исходные трёхзначные числа: 728, 536. Поразрядные суммы: 12, 5, 14. Результат: 14125.
Известно, что одним из чисел, подаваемых на вход автомата, является 763. Укажите второе число, подаваемое на вход автомата, если в результате автомат выдаёт число 121113.
Решение
Задача 10
Автомат получает на вход два трёхзначных числа. По этим числам строится новое число по следующим правилам.
1. Записывается результат сложения значений младших разрядов заданных чисел.
2. Если полученная сумма меньше десяти, то слева от этой суммы дописывается результат сложения значений средних разрядов заданных чисел, в противном случае—справа.
3. Итоговое число получают приписыванием слева к полученному после второго шага числу суммы значений старших разрядов исходных чисел.
Пример. Исходные трёхзначные числа: 728, 536. Поразрядные суммы: 12, 5, 14. Результат: 12145.
Известно, что одним из чисел, подаваемых на вход автомата, является 574. Укажите второе число, подаваемое на вход автомата, если в результате автомат выдаёт число 14159.
Решение
Задача 11
Автомат получает на вход два трёхзначных числа.По этим числам строится новое число по следующим правилам.
1. Записывается результат сложения значений младших разрядов заданных чисел.
2. Если полученная сумма меньше десяти, то слева от этой суммы дописывается результат сложения значений средних разрядов заданных чисел, в противном случае—справа.
3. Итоговое число получают приписыванием слева к полученному после второго шага числу суммы значений старших разрядов исходных чисел.
Пример. Исходные трёхзначные числа: 728, 536. Поразрядные суммы: 12, 5, 14. Результат: 12145.
Известно, что одним из чисел, подаваемых на вход автомата, является 424. Укажите второе число, подаваемое на вход автомата, если в результате автомат выдаёт число 91311.
Решение
Задача 12
Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам.
1) Вычисляются два числа—произведение первой и второй цифр исходного числа, а затем—произведение второй и третьей цифр.
2) Полученные числа записываются в порядке убывания (без разделителей).
Пример.Исходное число: 824.Произведение первой и второй цифр8 · 2 = 16. Результат произведения второй и третьей цифр2 · 4 = 8. Результат: 168.
Укажите наименьшее число, в результате обработки которого автомат выдаст число 1815.
Решение
Задача 13
Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам.
1) Вычисляются два числа — произведение первой и третьей цифр исходного числа, а затем произведение второй и третьей цифр.
2) Полученные числа записываются в порядке возрастания (без разделителей).
Пример. Исходное число: 389. Произведение первой и третьей цифр — 3 · 9 = 27. Результат произведения второй и третьей цифр—8 · 9 = 72. Результат: 2772.
Укажите наибольшее число, в результате обработки которого автомат выдаст число 1218.
Решение
Задача 14
Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам.
1) Вычисляются два числа — сумма второй и третьей цифр исходного числа, а также вычисляется результат умножения первой цифры на 3.
2) Полученные числа записываются в порядке убывания (без разделителей).
Пример. Исходное число: 781. Сумма второй и третьей цифр — 8 + 1 = 9. Результат умножения первой цифры на 3: 7 · 3 = 21. Результат: 219.
Укажите наименьшее число, в результате обработки которого автомат выдаст число 1814.
Решение
Задача 15
Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам.
1) Вычисляются два числа — сумма первой и последней цифр исходного числа, а также вычисляется результат умножения средней цифры на 2.
2) Полученные числа записываются в порядке возрастания (без разделителей).
Пример. Исходное число: 781. Сумма первой и последней цифр7 + 1 = 8. Результат умножения средней цифры на 2: 8 · 2 = 16. Результат: 816.
Укажите наибольшее число, в результате обработки которого автомат выдаст число 1314.
Решение
Задача 16
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11001 преобразуется в запись 110011;
б) над этой записью производятся те же действия: справа дописывается остаток от деления суммы цифр на 2.Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите минимальное число R, которое превышает 30 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе.
Решение
Задача 17
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конец числа (справа) дописываются 10, в противном случае справа дописываются 11.
Например, двоичная запись 110 числа 6 будет преобразована в 11010. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа — результата работы данного алгоритма.
Укажите минимальное число N, для которого результат работы алгоритма будет больше 202. В ответе это число запишите в десятичной системе.
Решение
Задача 18
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конец числа (справа) дописываются 00, в противном случае справа дописываются 10.
Например, двоичная запись 110 числа 6 будет преобразована в 11000. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числаN) является двоичной записью числа—результата работы данного алгоритма.
Укажите минимальное число N, для которого результат работы алгоритма будет больше 130. В ответе это число запишите в десятичной системе.
Решение
Задача 19
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конец числа (справа) дописываются 01, в противном случае справа дописываются 11.
Например, двоичная запись 110 числа 6 будет преобразована в 11001. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа — результата работы данного алгоритма.
Укажите минимальное число N, для которого результат работы алгоритма будет больше 105. В ответе это число запишите в десятичной системе.
Решение
Задача 20
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
- Строится двоичная запись числа N.
- К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конец числа (справа) дописываются два нуля, в противном случае справа дописываются две единицы.
Например, двоичная запись 110 числа 6 будет преобразована в 11000.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа—результата работы данного алгоритма.
Укажите минимальное число N, для которого результат работы алгоритма будет больше 124. В ответе это число запишите в десятичной системе.