Содержание:
Объяснение 6 задания
Исполнитель для возведения в квадрат, деления, умножения и сложения
Тезисно рассмотрим то, что может пригодиться для решения 6 задания.
- в задаче, для которой требуется определить все возможные результаты работы алгоритма какого-либо исполнителя, можно исходные данные обозначить переменными и вычислить алгоритм с этими переменными;
- в задаче, для которой требуется найти оптимальную программу (или наиболее короткую), и которая с помощью заданного набора команд преобразует некоторое число в другое, лучше для решения строить дерево возможных вариантов; таким образом, вычисляя, какие результаты получатся после одного шага, после двух шагов и т.д. В результате найдется общее решение;
- если среди заданных в задании команд исполнителя есть необратимая команда (например, исполнитель работает с целыми числами и есть команда возведения в квадрат – любое число можно возвести в квадрат, но не из любого числа можно извлечь квадратный корень, получив при этом целое), то дерево вариантов лучше строить с конца, т.е. в обратном порядке, двигаясь от конечного числа к начальному; тогда как получившаяся при этом в результате последовательность команд программы необходимо записать от начального числа к конечному.
Проверка числовой последовательности на соответствие алгоритму
- для выполнения некоторых заданий необходимо повторить тему системы счисления;
- максимальное значение суммы цифр десятичного числа — это 18, так как 9 + 9 = 18;
- для проверки правильности переданного сообщения иногда вводится бит четности — дополнительный бит, которым дополняется двоичный код таким образом, чтобы в результате количество единиц стало четным: т.е. если в исходном сообщении количество единиц было четным, то добавляется 0, если нечетным — добавляется 1:
например: 310 = 112 после добавления бита четности: 110 ---- 410 = 1002 после добавления бита четности: 1001
например: 1112 - это 710 добавим 0 справа: 11102 - это 1410
Теперь будем рассматривать конкретные типовые экзаменационные варианты по информатике с объяснением их решения.
Разбор 6 задания
Решение заданий 6 ЕГЭ по информатике для темы Исполнители
Исполнитель КУЗНЕЧИК живет на числовой оси. Начальное положение КУЗНЕЧИКА — точка 0. Система команд КУЗНЕЧИКА:
- Вперед 5 — Кузнечик прыгает вперед на 5 единиц,
- Назад 3 — Кузнечик прыгает назад на 3 единицы.
Какое наименьшее количество раз должна встретиться в программе команда «Назад 3», чтобы КУЗНЕЧИК оказался в точке 21?
Подобные задания для тренировки
✍ Решение:
✎ 1 вариант решения:
- Введем обозначения:
- пусть x — это команда Вперед 5
- пусть y — это команда Назад 3
- Поскольку Кузнечик двигается с начала числовой оси (с 0) и в итоге достигает точки 21, то получим уравнение:
5x - 3y = 21 (-3y - поскольку двигаемся назад)
5x = 21 + 3y
у=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 - 3 - 3 - 3 = 21 -> получили 21!
Результат: 3
Если что-то осталось непонятным, предлагаем посмотреть видео с разбором решения:
Имеется исполнитель Кузнечик, живущий на числовой оси. Система команд Кузнечика:
- Вперед N (Кузнечик прыгает вперед на N единиц);
- Назад M (Кузнечик прыгает назад на M единиц).
Переменные N и M могут принимать любые целые положительные значения.
Известно, что Кузнечик выполнил программу из 50 команд, в которой команд Назад 2 на 12 больше, чем команд Вперед 3. Других команд в программе не было.
На какую одну команду можно заменить эту программу, чтобы Кузнечик оказался в той же точке, что и после выполнения программы?
Подобные задания для тренировки
✍ Решение:
- Для того чтобы узнать количество обеих команд, необходимо ввести неизвестное x. Представим, что количество команд Вперед 3 было выполнено x раз, тогда количество команд Назад 2 было x+12 раз. Так как всего команд было 50 и других команд не было, то составим уравнение:
x + x + 12 = 50 команд
2х = 50 - 12 x = 38/2 = 19
3 * 19 - 2 * (19 + 12) = 57 - 62 = -5
Результат: Назад 5
Предлагаем посмотреть разбор задания 6 на видео:
У исполнителя Квадр две команды, которым присвоены номера:
- прибавь 1,
- возведи в квадрат.
Первая из этих команд увеличивает число на экране на 1, вторая — возводит в квадрат. Программа для исполнителя Квадр — это последовательность номеров команд.
Например, 22111 — это программа возведи в квадрат возведи в квадрат прибавь 1 прибавь 1 прибавь 1 Эта программа преобразует число 3 в 84.
Запишите программу для исполнителя Квадр, которая преобразует число 5 в число 2500 и содержит не более 6 команд. Если таких программ более одной, то запишите любую из них.
Подобные задания для тренировки
✍ Решение:
- Поскольку число 2500 достаточно большое, поэтому разгадать, какими командами можно до него «дойти» сложно.
- В такого рода задачах следует начать решение с конца — с числа 2500, и каждый раз пытаться выполнить действие квадратный корень из числа (т.к. квадратный корень — операция обратная возведению в квадрат). Если квадратный корень не извлекается, будем выполнять обратную команду для первой команды — Вычти 1 (обратная для Прибавь 1):
Результат: 11212
Вы можете посмотреть видео решенного 6 задания ЕГЭ по информатике:
У исполнителя Калькулятор две команды, которым присвоены номера:
- прибавь 3,
- умножь на 5.
Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на 5.
Запишите порядок команд в программе, которая преобразует число 3 в число 24 и содержит не более четырёх команд. Указывайте лишь номера команд.
Подобные задания для тренировки
✍ Решение:
- В такого рода задачах иногда проще начать решение с конца — с числа 24, и каждый раз пытаться выполнить действие разделить на 5 (т.к. деление — операция обратная умножению). Если рассматриваемое число не делится целочисленно на 5, то будем выполнять обратную команду для первой команды — вычти 3 (обратная для прибавь 3):
Ответ: 2111
У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера:
- сдвинь вправо
- прибавь 4
Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд вправо, а выполняя вторую, добавляет к нему 4.
Исполнитель начал вычисления с числа 191 и выполнил цепочку команд 112112. Запишите результат в десятичной системе счисления.
Подобные задания для тренировки
✍ Решение:
- Для выполнения первой команды переведем число в двоичную систему счисления:
19110 = 101111112
10111111 - > 1011111
01011111 - > 101111
1011112 -> 4710
47 + 4 = 51
5110 = 1100112
110011 - > 11001
11001 - > 1100
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
Подробное объяснение смотрите на видео:
У исполнителя Прибавлятеля-Умножателя две команды, которым присвоены номера:
- Прибавь 3
- Умножь на х
Первая из них увеличивает число на экране на 3, вторая умножает его на х. Программа для исполнителя — это последовательность номеров команд. Известно, что программа 12112 преобразует число 3 в число 120.
Определите значение х, если известно, что оно натуральное.
✍ Решение:
- Подставим по порядку выполняемые команды согласно номерам в последовательности команд. Для удобства будем использовать скобки:
12112:
((((3+3)*х)+3)+3)*х = 120
6х2 + 6х - 120 = 0
x1=4; x2=-60/12
((((3+3)*4)+3)+3)*4 = 120
Все верно.
Результат: 4
Подробней разбор урока можно посмотреть на видео ЕГЭ по информатике 2017:
Решение заданий для темы Проверка числовой последовательности (Автомат)
Автомат получает на вход четырёхзначное число. По этому числу строится новое число по следующим правилам.
- Складываются первая и вторая, а также третья и четвёртая цифры исходного числа.
- Полученные два числа записываются друг за другом в порядке убывания (без разделителей).
Пример. Исходное число: 3165. Суммы: 3 + 1 = 4; 6 + 5 = 11. Результат: 114.
Укажите наименьшее число, в результате обработки которого, автомат выдаст число 1311.
✍ Решение:
Результат: 2949
Процесс решения данного 6 задания представлен в видеоуроке:
Автомат получает на вход четырехзначное число. По нему строится новое число по следующим правилам:
- Складываются первая и вторая, затем вторая и третья, а далее третья и четвёртая цифры исходного числа.
- Полученные три числа записываются друг за другом в порядке возрастания (без разделителей).
Пример: Исходное число: 7531. Суммы: 7+5=12; 5+3=8; 3+1=4. Результат: 4812.
Укажите наибольшее число в результате обработки которого автомат выдаст 2512.
Подобные задания для тренировки
✍ Решение:
Подробное решение данного 6 задания можно просмотреть на видео:
Автомат получает на вход два двузначных шестнадцатеричных числа. В этих числах все цифры не превосходят цифру 6 (если в числе есть цифра больше 6, автомат отказывается работать). По этим числам строится новое шестнадцатеричное число по следующим правилам:
- Вычисляются два шестнадцатеричных числа — сумма старших разрядов полученных чисел и сумма младших разрядов этих чисел.
- Полученные два шестнадцатеричных числа записываются друг за другом в порядке убывания (без разделителей).
Пример: Исходные числа: 25, 66. Поразрядные суммы: 8, B. Результат: B8.
Какие из предложенных чисел могут быть результатом работы автомата?
Перечислите в алфавитном порядке буквы, соответствующие этим числам, без пробелов и знаков препинания.
Варианты:
A) 127
B) C6
C) BA
D) E3
E) D1
✍ Решение:
Подробное решение данного 6 задания можно просмотреть на видео:
Автомат получает на вход два двузначных шестнадцатеричных числа. В этих числах все цифры не превосходят цифру 7 (если в числе есть цифра больше 7, автомат отказывается работать). По этим числам строится новое шестнадцатеричное число по следующим правилам.
1. Вычисляются два шестнадцатеричных числа: сумма старших разрядов полученных чисел и сумма младших разрядов этих чисел.
2. Полученные два шестнадцатеричных числа записываются друг за другом в порядке возрастания (без разделителей).
Пример. Исходные числа: 66, 43. Поразрядные суммы: A, 9. Результат: 9A.
Определите, какое из предложенных чисел может быть результатом работы автомата.
Варианты:
1) AD
2) 64
3) CF
4) 811
✍ Решение:
Результат: 1
Решение 4 задания ГВЭ 11 класса смотрите на видео:
Автомат получает на вход натуральное число X. По этому числу строится трёхзначное число Y по следующим правилам:
1. Первая цифра числа Y (разряд сотен) – остаток от деления X на 7.
2. Вторая цифра числа Y (разряд десятков) – остаток от деления X на 2.
3. Третья цифра числа Y (разряд единиц) – остаток от деления X на 5.
Сколько существует двузначных чисел, при обработке которого автомат выдаёт результат 312?
✍ Решение:
- Обозначим каждую цифру числа 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
Решение задания про алгоритм, который строит число R
На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом:
- Строится двоичная запись числа 4N.
- К этой записи дописываются справа еще два разряда по следующему правилу:
- складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 10000 преобразуется в запись 100001;
- над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на 2.
Полученная таким образом запись является двоичной записью искомого числа R.
Укажите такое наименьшее число N, для которого результат работы алгоритма больше 129. В ответе это число запишите в десятичной системе счисления.
✍ Решение:
- Заметим, что после выполнения второго пункта задания, будут получаться только четные числа! Наименьшим возможным четным числом, превышающим 129, является число 130. С ним и будем работать.
- Переведем 130 в двоичную систему счисления:
13010 = 100000102
в обратном порядке: было 1000001 -> стало 10000010 еще раз то же самое: было 100000 -> стало 1000001
1000002 = 3210
Результат: 8
Для более детального разбора предлагаем посмотреть видео решения данного 6 задания ЕГЭ по информатике:
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
- Строится двоичная запись числа N.
- К этой записи дописываются справа ещё два разряда по следующему правилу:
- складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
- над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите минимальное число R, которое превышает число 83 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.
✍ Решение:
- Заметим, что после второго пункта условия задачи получаются только четные числа (т.к. если число в двоичной системе заканчивается на 0, то оно четное). Таким образом, нас будут интересовать только четные числа.
- Наименьшим возможным числом, превышающим 83, является число 84. С ним и будем работать.
- Переведем 84 в двоичную систему счисления:
84 = 1010100
86 = 1010110
Результат: 86
Подробное решение данного 6 задания из демоверсии ЕГЭ 2018 года смотрите на видео:
На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа еще два разряда по следующему правилу:
— если N делится нацело на 4, в конец числа (справа) дописывается сначала ноль, а затем еще один ноль;
— если N при делении на 4 дает в остатке 1, то в конец числа (справа) дописывается сначала ноль, а затем единица;
— если N при делении на 4 дает в остатке 2, то в конец числа (справа) дописывается сначала один, а затем ноль;
— если N при делении на 4 дает в остатке 3, в конец числа (справа) дописывается сначала один, а затем еще одна единица.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа R — результата работы данного алгоритма.
Укажите максимальное число R, которое меньше 100 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.
Подобные задания для тренировки
✍ Решение:
- Поскольку требуется найти наибольшее число, то возьмем наибольшее из возможных чисел, которые < 100 — это число 99. Переведем его в двоичную систему:
99 = 11000112
1100011 N
11000 = 2410
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
Предлагаем посмотреть видео решения:
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1. Строится двоичная запись числа N.
2. К этой записи дописывается (дублируется) последняя цифра.
3. Затем справа дописывается бит чётности: 0, если в двоичном коде полученного числа чётное число единиц, и 1, если нечётное.
4. К полученному результату дописывается ещё один бит чётности.
Полученная таким образом запись (в ней на три разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите минимальное число R, большее 114, которое может быть получено в результате работы этого алгоритма. В ответе это число запишите в десятичной системе.
✍ Решение:
- В постановке задания задано R > 114. R — это результат работы алгоритма. Для того, чтобы определить наименьшее возможно N, переведем сначала 114 в двоичную систему счисления и выделим в нем три добавленные по алгоритму цифры:
114 = 11100102
2. В полученное числе N = 1110 дублируется последняя цифра и получается 11100.
3. Поскольку число единиц (3) — нечетное, то справа добавляется 1: 111001.
4. Т.к. в полученном наборе цифр четное число единиц, то добавляем 0: 1110010
1. N = 1110 + 1 = 1111 Работа по алгоритму: 2. 11111 - дублирование последней цифры. 3. 111111 - справа дописываем единицу, т.к. в полученном числе 5 единиц (нечетное) 4. 1111110 - дописываем ноль, т.к. в полученном числе четное число единиц.
min R = 11111102 = 12610
Результат: 126
Автомат обрабатывает целое число N (0 ≤ N ≤ 255) по следующему алгоритму:
1. Строится восьмибитная двоичная запись числа N.
2. Все цифры двоичной записи заменяются на противоположные (0 на 1, 1 на 0).
3. Полученное число переводится в десятичную запись.
4. Из нового числа вычитается исходное, полученная разность выводится на экран.
Какое число нужно ввести в автомат, чтобы в результате получилось 45?
✍ Решение:
- Результатом выполнения алгоритма является число 45. Алгоритм работает в двоичной системе счисления, поэтому переведем число:
45 = 001011012
1 - 0, с учетом, что у разряда с единицей заняли. То есть бит:. _ 1 _ _ _ _ _ _ _ N инвертируемое = 0 _ _ _ _ _ _ _ N исходное 0 0 1 0 1 1 0 1 = 45 результат
1 - 0 не может в результате дать 0, так как у следующей слева единицы мы заняли. Значит, 0 - 1. Чтобы не получить единицу в ответе, необходимо у нуля тоже занять:. . _ 1 0 _ _ _ _ _ _ = 0 1 _ _ _ _ _ _ 0 0 1 0 1 1 0 1 = 45 результат
1 - 0 не может быть, так как у следующего слева нуля мы заняли.Значит
0 - 1. То есть как раз чтобы получить единицу (10 - 1 = 1), занимаем у следующих слева разрядов:. . _ 1 0 0 _ _ _ _ _ = 0 1 1 _ _ _ _ _ 0 0 1 0 1 1 0 1 = 45 результат
0 - 1 не может быть. Значит, чтобы получить в результате ноль, берем 1 - 0, у единицы должно быть занято.. . . _ 1 0 0 1 _ _ _ _ = 0 1 1 0 _ _ _ _ 0 0 1 0 1 1 0 1 = 45 результат
1 - 0 не может быть. Так как слева у единицы занято. Значит, чтобы получить в результате 1, берем 0 - 1:. . . _ 1 0 0 1 0 _ _ _ = 0 1 1 0 1 _ _ _ 0 0 1 0 1 1 0 1 = 45 результат
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 результат
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 результат
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 результат
01101001 = 10510
Ответ: 105
Смотрите разбор задания на видео и подписывайтесь на наш канал:
