Э Исполнитель. Е Г Школа 58 Иванцова С.А., МОУ СОШ 58, г.Н.Новгород. - презентация

1 Э Исполнитель. Е Г Школа 58 Иванцова С.А., МОУ СОШ 58, г.Н.Новгород

2 В этой презентации приводятся тренировочные задания из нескольких источников: открытого сегмента федерального банка тестовых заданий, демонстрационных вариантов ЕГЭ прошлых лет, материалов К. Ю. Полякова, учебного пособия «ЕГЭ Информатика» (Крылов С.С., Лещинер В.Р., Якушкин П.А. - М.: Интеллект-Центр, 2007). Презентация содержит систематизированную информацию из различных источников, а также разработки автора в виде необходимых для исследования тем курса рекомендаций и решения ряда задач. Цель данной работы помочь вам «набить руку» в решении тестов ЕГЭ, разобраться с наиболее сложными заданиями и узнать объективный уровень своих знаний.

3 Пример 1: Решение: Правильный ответ - 414

4 Пример 2:

5 Черепашка прочертит на экране 4 линии, но последний отрезок полностью совпадет с первым, так как после третьего выполнения цикла черепашка полностью обернется вокруг своей оси и окажется в той же точке, что и изначально. Так что на экране появится правильный треугольник. Внутренние углы получившейся фигуры равны: 3*( )=3*60=180º– это сумма углов треугольника. Для справки, сумма внутренних углов: 4-угольника равна 360º; 5-угольника равна 540º; 6-угольника равна 720º; 7-угольника равна 900º; 8-угольника равна 1080º и т.д. Решение: Правильный ответ - 2

6 Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости: вверх, вниз, влево, вправо. При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх, вниз, влево, вправо. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: снизу свободно, слева свободно, справа свободно, слева свободно. Цикл ПОКА команда выполняется, пока условие истинно, иначе происходит переход на следующую строку. Если РОБОТ начнет движение в сторону стены, то он разрушится и программа прервется. Сколько клеток лабиринта соответствуют требованию, что, выполнив предложенную программу, РОБОТ уцелеет и остановится в той же клетке, с которой он начал движение? НАЧАЛО ПОКА вправо ПОКА вверх ПОКА влево ПОКА вниз КОНЕЦ 1) 1; 2) 2; 3) 3; 4) 4. Пример 3:

7 Решение: НАЧАЛО ПОКА вправо ПОКА вверх ПОКА влево ПОКА вниз КОНЕЦ Сразу отсекаем те клетки, у которых снизу свободно, а справа – стена, т.к. начиная с них РОБОТ разрушится (х). Потом отсекаем те клетки, у которых снизу уже не свободно, справа свободно, а вверху – стена, т.к. начиная с них РОБОТ разрушится (х). Отмечаем те клетки, у которых снизу и справа уже не свободно, сверху свободно, а влево – стена, т.к. начиная с них РОБОТ разрушится – таких нет. Отмечаем и те клетки, движение из которых приводит в «опасные» клетки и РОБОТ рушится (х). Есть и клетки, начиная движение из которых РОБОТ не разбивается, но не возвращается в начальную клетку (х). Только две клетки оказались «безопасными» для РОБОТА и он в них вернулся по окончании движения. Легко понять, что для того, чтобы РОБОТ вернулся обратно в ту клетку, откуда он начал движения, четыре (или две) стенки должны быть расставлены так, чтобы он упирался в них, например, при движении вправо, вверх, влево, вниз (или вправо-влево). Кроме этого, необходимо, чтобы «коридор» был свободен для прохода. Эти рассуждения оптимизируют алгоритм. Правильный ответ - 2

8 Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости: вверх, вниз, влево, вправо. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: сверху свободно, снизу свободно, слева свободно, справа свободно. Цикл ПОКА команда выполняется, пока условие истинно, иначе происходит переход на следующую строку. Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ остановится в той же клетке, с которой он начал движение? 1) 1 2) 0 3) 3 4) ABCDEF НАЧАЛО ПОКА вправо ПОКА вверх ПОКА влево ПОКА вниз КОНЕЦ Пример 4:

9 Правильный ответ - 4 о о 3 2 оо 1 ABCDEF НАЧАЛО ПОКА вправо ПОКА вверх ПОКА влево ПОКА вниз КОНЕЦ Решение: о 6 о 5 о 4 оо 3 о 2 оо оооо 1 ABCDEF Для того, чтобы РОБОТ вернулся обратно в ту клетку, откуда он начал движения, четыре стенки должны быть расставлены так, чтобы он упирался в них последовательно при движении вправо, вверх, влево и, наконец, вниз при условии свободного «коридора» движения. Алгоритм движения заканчивается после выполнения цикла: ПОКА вниз, поэтому нужно рассматривать лишь те клетки, где есть стенка снизу. Отметим на исходной карте чёрным кружочком такие клетки-кандидаты. Из них только 4 удовлетворяют условию задачи, т.е. РОБОТ останавливается в той же клетке, с которой он начал движение.

10 Имеется исполнитель Кузнечик, который живет на числовой оси. Система команд Кузнечика: Вперед N (Кузнечик прыгает вперед на N единиц); Назад M (Кузнечик прыгает назад на M единиц). Переменные N и M могут принимать любые целые положительные значения. Известно, что Кузнечик выполнил программу из 50 команд, в которой команд Назад 2 на 12 больше, чем команд Вперед 3. Других команд в программе не было. На какую одну команду можно заменить эту программу, что и после выполнения программы? Пример 5: Решение: Пусть x – количество команд Вперед 3, тогда: (12 + х) + х = 50 Отсюда х=19, т.е. команд Вперед 3 было 19, а Назад 2 было 19+12=31. Значит Кузнечик выполнил прыжков вперёд 3*19=57, а назад 2*31=62. После выполнения программы Кузнечик оказался на 62-57=5 прыжков сзади. Чтобы Кузнечик оказался в той же точке, можно было выполнить команду Назад 5.

11 У исполнителя Утроитель две команды, которым присвоены номера: 1. вычти 1 2. умножь на 3 Первая из них уменьшает число на экране на 1, вторая – увеличивает его в три раза. Запишите порядок команд в программе получения из числа 3 числа 16, содержащей не более 5 команд, указывая лишь номера команд. (Например, программа это программа: умножь на 3 вычти 1 умножь на 3 вычти 1 вычти 1, которая преобразует число 1 в 4. Решение (1способ): Начинаем рассуждения с конца, т.е. с числа 16, учитывая при этом, что умножение эффективнее сложения, поэтому нужно постараться максимально использовать умножение, а сложение – только в крайних случаях. Число 16 точно получено не умножением на 3, значит последняя команда 1. вычти 1 и перед её выполнением было число 17, которое тоже не делится нацело на 3, значит предпоследняя – команда 1 и число было 18, которое скорее всего было получено с помощью команды 2. умножь на 3 числа 6. Которое тоже в свою очередь получено командой 2. умножь на 3 числа 2. Это число получено командой 1. вычти 1 из исходного числа Число Команда12211 Пример 6: Правильный ответ

12 У исполнителя Утроитель две команды, которым присвоены номера: 1. вычти 1 2. умножь на 3 Первая из них уменьшает число на экране на 1, вторая – увеличивает его в три раза. Запишите порядок команд в программе получения из числа 3 числа 16, содержащей не более 5 команд, указывая лишь номера команд. Решение (2способ): Начинаем рассуждения с начала (с 3 до 16), учитывая, что в условии ограничено число команд, поэтому неявно ставится задача написать самую короткую программу для решения задачи. На первом шаге с помощью имеющихся команд из числа 3 можно получить 2 или 9 и т.д. Нужно выбрать такой план дальнейшего перебора вариантов, который может быстрее всего привести к цели (числу 16), отсекая заведомо «тупиковые» ветки в «дереве». Пример 6: Правильный ответ

13 У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера: 1. сдвинь влево 2. вычти 1 Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд влево, а выполняя вторую, вычитает из него 1. Исполнитель начал вычисления с числа 91 и выполнил цепочку команд Запишите результат в десятичной системе. Решение: «Сдвиг влево» - так называется операция, при которой все биты числа в ячейке (регистре) сдвигаются на 1 бит влево, в младший бит записывается нуль, а старший бит попадает в специальную ячейку – бит переноса: Пример 7: Сдвиг влево двоичных разрядов влево равнозначен умножению числа на 10 2 =2 10 ( вправо, соответственно – делению нацело на 10 2 =2 10 ). Но если в старшем (7-ом) бите исходного числа была 1, то она после сдвига влево окажется в бите переноса и будет потеряна, поэтому мы фактически получим остаток от деления удвоенного числа на 2 8 = = Бит переноса

14 Решение (продолжение): Цепочка команд для числа выполняется следующим образом: Код командыДействиеРезультат 1 умножь на = , т.о. ищем остаток от деления mod = вычти = умножь на = , т.о. ищем остаток от деления mod = вычти = Правильный ответ – 171

15 Пример 8:

16 Решение:

17

18 Спасибо за внимание!