КОПИЛКА ЗНАНИЙСайт учителя физики и информатики МБОУ "Лицей №17" Назаренко О.Г.
Главная » 2018»Март»27 » Консультация ЕГЭ №16 Алгоритмы и исполнители
15:14
Консультация ЕГЭ №16 Алгоритмы и исполнители
Задание 6 Исполнитель для возведения в квадрат, деления, умножения и сложения
6-я тема характеризуется, как задания базового уровня сложности, время выполнения – примерно 4 минуты
Тезисно рассмотрим то, что может пригодиться для решения 6 задания.
в задаче, для которой требуется определить все возможные результаты работы алгоритма какого-либо исполнителя, можно исходные данные обозначить переменными и вычислить алгоритм с этими переменными;
в задаче, для которой требуется найти оптимальную программу (или наиболее короткую), и которая с помощью заданного набора команд преобразует некоторое число в другое, лучше для решения строить дерево возможных вариантов; таким образом, вычисляя, какие результаты получатся после одного шага, после двух шагов и т.д., в результате найдется общее решение
если среди заданных в задании команд исполнителя есть необратимая команда (например, исполнитель работает с целыми числами и есть команда возведения в квадрат – любое число можно возвести в квадрат, но не из любого числа можно извлечь квадратный корень, получив при этом целое число), то дерево вариантов лучше строить с конца, т.е. в обратном порядке, двигаясь от конечного числа к начальному; тогда как получившаяся при этом в результате последовательность команд программы необходимо записать от начального числа к конечному
Для выполнения некоторых заданий необходимо повторить тему системы счисления;
максимальное значение суммы цифр десятичного числа — это число 18, так как 9+9=18;
для проверки правильности переданного сообщения иногда вводится бит четности — дополнительный бит, которым дополняется двоичный код таким образом, чтобы в результате количество единиц стало четным: т.е. если в исходном сообщении количество единиц было нечетным, то добавляется 0, если четным — добавляется 1:
добавление к двоичной записи числа нуля справа увеличивает число в 2 раза:
Теперь будем рассматривать конкретные типовые экзаменационные варианты по информатике с объяснением их решения.
Решение заданий 6 ЕГЭ по информатике для темы Исполнители
Вы можете посмотреть видео решенного ниже 6 задания ЕГЭ по информатике:
ЕГЭ 6.1: У исполнителя Квадр две команды, которым присвоены номера:
прибавь 1,
возведи в квадрат.
Первая из этих команд увеличивает число на экране на 1, вторая — возводит в квадрат. Программа для исполнителя Квадр — это последовательность номеров команд.
Например, 22111 — это программа
возведи в квадрат
возведи в квадрат
прибавь 1
прибавь 1
прибавь 1
Эта программа преобразует число 3 в число 84.
Запишите программу для исполнителя Квадр, которая преобразует число 5 в число 2500 и содержит не более 6 команд. Если таких программ более одной, то запишите любую из них.
Решение:
Поскольку число 2500 достаточно большое, поэтому разгадать какими командами можно до него «дойти» сложно.
В такого рода задачах следует начать решение с конца — с числа 2500, и каждый раз пытаться выполнить действие квадратный корень из числа (т.к. квадратный корень — операция обратная возведению в квадрат). Если квадратный корень не извлекается, будем выполнять обратную команду для первой команды — Вычти 1 (обратная для Прибавь 1):
Число 2500: квадрат числа 50 -> операция 2
Число 50: не является квадратом, значит команда Отнять 1, получим 49 -> операция 1
Число 49: квадрат числа 7 -> операция 2
Число 7: не является квадратом, значит команда Отнять 1, получим 6 -> операция 1
Число 6: не является квадратом, значит команда Отнять 1, получим 5 -> операция 1
Запишем все команды в обратной последовательности и получим результат:
Результат: 11212
Задание 6 ЕГЭ по информатике 2017 ФИПИ вариант 19 (Крылов С.С., Чуркина Т.Е.):
У исполнителя Прибавлятеля-Умножателя две команды, которым присвоены номера:
Прибавь 3
Умножь на х
Первая из них увеличивает число на экране на 3, вторая умножает его на х. Программа для исполнителя — это последовательность номеров команд. Известно, что программа 12112 преобразует число 3 в число 120.
Определите значение х, если известно, что оно натуральное.
Решение:
((((3+3)*х)+3)+3)*х = 120
6х2 + 6х — 120 = 0
x1=4; x2=-60/12
((((3+3)*4)+3)+3)*4 = 120
Все верно.
Подставим по порядку выполняемые команды согласно номерам в последовательности команд: 12112:
Получим квадратное уравнение:
Решим его и получим результат:
Так как по заданию х — натуральное, то х2 нам не подходит.
Подставим х1 в наше уравнение для проверки:
Результат: 4
Подробней разбор урока можно посмотреть на видео ЕГЭ по информатике 2017:
Решение заданий для темы Проверка числовой последовательности
Задание 6 ЕГЭ по информатике 2017 ФИПИ вариант 2 (Крылов С.С., Чуркина Т.Е.):
На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом:
Строится двоичная запись числа 4N.
К этой записи дописываются справа еще два разряда по следующему правилу:
складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 10000 преобразуется в запись 100001;
над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на 2.
Полученная таким образом запись является двоичной записью искомого числа R.
Укажите такое наименьшее число N, для которого результат работы алгоритма больше 129. В ответе это число запишите в десятичной системе счисления.
Решение:
Наименьшим возможным числом, превышающим число 129, является число 130. С ним и будем работать.
Переведем 130 в двоичную систему счисления: 10000010
Это двоичное число, получилось из исходного двоичного, после того как дважды был добавлен остаток от деления суммы цифр на 2. Т.е, было 1000001 -> стало 10000010; еще раз то же самое: было 100000 -> стало 1000001. Значит необходимое нам двоичное число — это 100000.
Переведем 100000 в 10-ю систему — > 32.
Так как по условию у нас 4*N, то 32 делим на 4 — > 8.
Результат: 8
Для более детального разбора предлагаем посмотреть видео решения данного 6 задания ЕГЭ по информатике:
ЕГЭ по информатике задание 6 с сайта К. Полякова (задание под номером Р-06):
Автомат получает на вход четырёхзначное число. По этому числу строится новое число по следующим правилам.
Складываются первая и вторая, а также третья и четвёртая цифры исходного числа.
Полученные два числа записываются друг за другом в порядке убывания (без разделителей).
Складываются первая и вторая, затем вторая и третья, а далее третья и четвёртая цифры исходного числа.
Полученные три числа записываются друг за другом в порядке возрастания (без разделителей)
Укажите наибольшее число в результате обработки которого автомат выдаст число 2512.
Решение:
Результат: 9320
Подробное решение данного 6 задания можно просмотреть на видео:
Задание 6 ЕГЭ по информатике 2017 ФИПИ (Ушаков Д.М.) вариант 2:
Автомат получает на вход два двузначных шестнадцатеричных числа. В этих числах все цифры не превосходят цифру 6 (если в числе есть цифра больше 6, автомат отказывается работать). По этим числам строится новое шестнадцатеричное число по следующим правилам:
Вычисляются два шестнадцатеричных числа — сумма старших разрядов полученных чисел и сумма младших разрядов этих чисел.
Полученные два шестнадцатеричных числа записываются друг за другом в порядке убывания (без разделителей)
Какие из предложенных чисел могут быть результатом работы автомата?
Перечислите в алфавитном порядке буквы, соответствующие этим числам, без пробелов и знаков препинания.
A) 127
B) C6
C) BA
D) E3
E) D1
Решение:
Результат: BC
Подробное решение данного 6 задания можно просмотреть на видео:
Задание 6_7:
Исполнитель КУЗНЕЧИК живет на числовой оси. Начальное положение КУЗНЕЧИКА — точка 0. Система команд КУЗНЕЧИКА:
Вперед 5 — Кузнечик прыгает вперед на 5 единиц,
Назад 3 — Кузнечик прыгает назад на 3 единицы.
Какое наименьшее количество раз должна встретиться в программе команда «Назад 3», чтобы КУЗНЕЧИК оказался в точке 21?
Решение:
Рассмотрим два варианта решения.
1 вариант решения:
5x - 3y = 21 (-3y — поскольку двигаемся назад)
5x = 21 + 3y
Поскольку нам нужно получить наименьшее y, то будем подбирать y, начиная с 1: у=1 -> 21+3 не делится на 5 у=2 -> 21+6 не делится на 5 у=3 -> 21+9 делится на 5
Введем обозначения:
пусть x — это команда Вперед 5
пусть y — это команда Назад 3
Поскольку Кузнечик двигается с начала числовой оси (с 0) и в итоге достигает точки 21, то получим уравнение:
Выразим x:
Чтобы выразить x необходимо будет правую часть делить на 5. А поскольку x не может быть дробным числом, то делаем вывод, что правая часть должна делиться на 5 без остатка.
2 вариант решения:
Допустим, Кузнечик допрыгал до 21 (и дальше). Он это мог сделать только при помощи команды Вперед 5. Будем рассматривать числа >21 и делящиеся на 5 без остатка (т.к. Вперед 5).
Первое число большее 21 и делящееся на 5 без остатка — это 25.
25 - 3 (Назад 3)= 22 -> не 21
30 - 3 - 3 - 3 = 21 -> получили 21!
При этом была использована команда Назад 3 3 раза.
Результат: 3
Если что-то осталось непонятным, предлагаем посмотреть видео с разбором решения:
Задание 6_8:
У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера:
сдвинь вправо
прибавь 4
Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд вправо, а выполняя вторую, добавляет к нему число 4. Исполнитель начал вычисления с числа 191 и выполнил цепочку команд 112112. Запишите результат в десятичной системе счисления.
Решение:
1 способ:
Для выполнения первой команды переведем число в двоичную систему счисления:
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
2 способ:
При сдвиге вправо в старший бит попадает нуль, а младший бит отправляется в специальную ячейку – бит переноса, т. е. он будет «утерян». Таким образом, если число чётное, то при сдвиге оно уменьшается в два раза; если число нечётное, уменьшается в два раза ближайшее меньшее чётное число (либо исходное нечетное число целочисленно делится на 2).
команда 1: 191 -> 95
команда 1: 95 -> 47
команда 2: 47 -> 51
команда 1: 51 -> 25
команда 1: 25 -> 12
команда 2: 12 -> 16
Результат: 16
Подробное объяснение смотрите на видео:
Задание 6_9:
Имеется исполнитель Кузнечик, живущий на числовой оси. Система команд Кузнечика:
Вперед N (Кузнечик прыгает вперед на N единиц);
Назад M (Кузнечик прыгает назад на M единиц).
Переменные N и M могут принимать любые целые положительные значения. Известно, что Кузнечик выполнил программу из 50 команд, в которой команд Назад 2 на 12 больше, чем команд Вперед 3. Других команд в программе не было. На какую одну команду можно заменить эту программу, чтобы Кузнечик оказался в той же точке, что и после выполнения программы?
Решение:
x+x+12 = 50 команд
2х = 50-12
x = 38/2 = 19
3*19-2*(19+12) = 57 - 62 = -5
Для того, чтобы узнать количество обеих команд, необходимо ввести неизвестное x. Представим, что количество команд Вперед 3 было выполнено x раз, тогда количество команд Назад 2 было x+12 раз. Так как всего команд было 50 и других команд не было, то составим уравнение:
Найдем x (кол-во команд Вперед 3):
Теперь найдем точку на числовой оси, в которой оказался Кузнечик. Учтем, что он 19 раз выполнил прыжок на три «шага» вперед и 19+12 раз прыгнул назад на 2 шага:
-5 означает, что можно было переместиться в эту точку одной командой — Назад 5
Результат: Назад 5
Предлагаем посмотреть разбор задания 6 на видео:
6 задание. Демоверсия ЕГЭ 2018 информатика:
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите минимальное число R, которое превышает число 83 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.
Строится двоичная запись числа N.
К этой записи дописываются справа ещё два разряда по следующему правилу:
складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.
Решение:
84 = 1010100
86 = 1010110
Заметим, что после второго пункта условия задачи получаются только четные числа (т.к. если число в двоичной системе заканчивается на 0, то это число четное). Таким образом нас будут интересовать только четные числа.
Наименьшим возможным числом, превышающим число 83, является число 84. С ним и будем работать.
Переведем 84 в двоичную систему счисления
В данном числе выделенная часть — это N. Значит необходимое нам двоичное число — это 10101. После первого пункта задачи к данному числу должна была добавиться справа единица, так как число нечетное. А мы имеем 0. Значит это число не подходит.
Возьмем следующее четное число — 86. Переведем его в двоичную систему счисления:
В данном числе выделенная часть — это N. Значит необходимое нам двоичное число — это 10101. После первого пункта задачи к данному числу должна была добавиться справа единица, так и есть: 101011. А затем добавляется 0: 1010110. Значит это число подходит.
Результат: 86
Подробное решение данного 6 задания из демоверсии ЕГЭ 2018 года смотрите на видео:
6 задание ЕГЭ. Задание 4 ГВЭ 11 класс 2018 год ФИПИ
Автомат получает на вход два двузначных шестнадцатеричных числа. В этих числах все цифры не превосходят цифру 7 (если в числе есть цифра больше 7, автомат отказывается работать). По этим числам строится новое шестнадцатеричное число по следующим правилам.
1. Вычисляются два шестнадцатеричных числа: сумма старших разрядов полученных чисел и сумма младших разрядов этих чисел. 2. Полученные два шестнадцатеричных числа записываются друг за другом в порядке возрастания (без разделителей).