'

Э

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

Что нужно знать*: Переменная – это величина, которая имеет имя, тип и значение; переменная может изменяться во время выполнения программы Оператор присваивания служит для записи значения в переменную, если в переменную записывают новое значение, старое стирается Знаки +, -, *, / используются для обозначения операций сложения, вычитания, умножения и деления Запись вида a div b означает результат целочисленного деления a на b (остаток отбрасывается), запись вида a mod b означает остаток от деления a на b Запись вида a := b + 2*c + 3; означает «вычислить значения выражения справа от знака присваивания := и записать результат в переменную a»; при этом значения других переменных (кроме a) не изменяются * Теория из материалов К.Ю. Полякова


Слайд 3

Двумерный массив А(m,n) можно представить в виде следующей матрицы: где m – количество строк, n – количество столбцов. массив – это набор однотипных элементов, имеющих общее имя; для обращения к элементу массива используют круглые (или квадратные – на языке Паскаль) скобки, запись A(i) обозначает элемент массива A с номером (индексом) i; матрица (двухмерный массив) – это прямоугольная таблица однотипных элементов; если матрица имеет имя A, то обращение A(i,k) обозначает элемент, расположенный на пересечении строки i и столбца k; элементы, у которых номера строки и столбца совпадают (i=j), расположены на главной диагонали. Номер столбца j элемента на побочной диагонали можно вычислить по формуле j=n-i+1, где n – размер квадратной матрицы, i – номер строки


Слайд 4

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


Слайд 5

Пример 2:


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

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


Слайд 10

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


Слайд 11

Имеется исполнитель Кузнечик, который живет на числовой оси. Система команд Кузнечика: Вперед 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.


Слайд 12

У исполнителя Утроитель две команды, которым присвоены номера: 1. вычти 1 2. умножь на 3 Первая из них уменьшает число на экране на 1, вторая – увеличивает его в три раза. Запишите порядок команд в программе получения из числа 3 числа 16, содержащей не более 5 команд, указывая лишь номера команд. (Например, программа 21211 это программа: умножь на 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 из исходного числа 3. Пример 5: Правильный ответ - 12211


Слайд 13

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


Слайд 14

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


Слайд 15

Решение (продолжение): Цепочка команд 112112 для числа 9110 выполняется следующим образом: Правильный ответ – 171


Слайд 16

Определите значение целочисленных переменных a и b после выполнения фрагмента программы: 1) a = 0, b = 18 2) a = 11, b = 19 3) a = 10, b = 18 4) a = 9, b = 17 Для решения нужно использовать «ручную прокрутку» программы, то есть, выполнить вручную все действия. Наиболее удобно и наглядно это получается при использовании таблицы, где в первом столбце записаны операторы программы, а в остальных показаны изменения переменных при выполнении этих операторов: Пример 7: Решение: Правильный ответ - 4


Слайд 17

Пример 8: Решение: Таблица значений переменных: Правильный ответ - 1


Слайд 18

Определите значение целочисленных переменных a и b после выполнения фрагмента программы (ниже представлена одна и та же программа, записанная на разных языках программирования): Решение: a=42 b=14 a=3 b=42 a=14 Пример 9: Правильный ответ - 4


Слайд 19

Пример 10:


Слайд 20

Далее Решение:


Слайд 21

Решение: Правильный ответ - 2


Слайд 22

. Определите значение переменной с после выполнения фрагмента алгоритма: Решение: Правильный ответ: с=55 Пример 11:


Слайд 23

Пример 12:


Слайд 24

Решение: Правильный ответ - 2


Слайд 25

Дан фрагмент программы, обрабатывающей массив A из n элементов: Чему будет равно значение переменной s после выполнения данного алгоритма, при любых значениях элементов массива А? 1) Максимальному элементу в массиве A 2) Индексу максимального элемента в массиве A (первому из них, если максимальных элементов несколько) 3) Индексу максимального элемента в массиве A (последнему из них, если максимальных элементов несколько) 4) Количеству элементов, равных максимальному в массиве A. Решение: Нетрудно заметить, что в циклическом операторе по выполнению условия IF A(i)>A(j) переменная j перехватывает индекс наибольшего в паре A(i), A(j) элемента. Следовательно, по завершении циклического оператора переменная j примет значение индекса последнего наибольшего элемента массива. Правильный ответ - 3 Пример 13:


Слайд 26

Дан фрагмент программы, обрабатывающей двухмерный массив A(n?n): Представим массив в виде квадратной таблицы, в которой для элемента массива A[i,j] величина i является номером строки, а величина j – номером столбца, в котором расположен элемент. Тогда данный алгоритм меняет местами 1) два столбца в таблице 2) две строки в таблице 3) элементы диагонали и k-ой строки таблицы 4) элементы диагонали и k-го столбца таблицы Пример 14:


Слайд 27

Внутри цикла меняются местами значения A[i,i] и A[k,i], используя переменную c в качестве вспомогательной ячейки. Элементы A[i,i] расположены на главной диагонали матрицы, а у элементов A[k,i] фиксирован номер строки (k), но меняется в цикле номер столбца. Следовательно, в программе элементы главной диагонали обмениваются с первой строкой (при k=1). Решение: (предложенное К.Ю. Поляковым) Правильный ответ - 3 1) два столбца в таблице 2) две строки в таблице 3) элементы диагонали и k-ой строки таблицы 4) элементы диагонали и k-го столбца таблицы


Слайд 28

Пример 15:


Слайд 29

Решение: Правильный ответ - 4


Слайд 30

Пример 16: Решение:


Слайд 31

Правильный ответ - 10 Решение:


Слайд 32

В программе описан одномерный целочисленный массив А с индексами от 0 до 10. Ниже представлен фрагмент одной и той же программы, записанный на разных языках программирования, в котором значения элементов сначала задаются, а затем меняются. Чему окажутся равны элементы этого массива? -1 -1 0 1 2 3 4 5 6 7 8 9 9 9 9 9 9 9 9 9 9 9 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 9 Решение: После первого цикла: -1 0 1 2 3 4 5 6 7 8 9 После второго цикла: 9 9 9 9 9 9 9 9 9 9 9 Правильный ответ - 2 Пример 17:


Слайд 33

Пример 18: Правильный ответ - 4


Слайд 34

Для составления цепочек используются бусины, помеченные буквами: A, B, C, D, E. На первом месте в цепочке стоит одна из бусин A, C, E. На втором – любая гласная, если первая буква согласная, и любая согласная, если первая гласная. На третьем месте – одна из бусин C, D, E, не стоящая в цепочке на первом месте. Какая из перечисленных цепочек создана по этому правилу? 1) CBE 2) ADD 3) ECE 4) EAD Решение: Можно составить по условию задачи несколько утверждений: У1: На первом месте в цепочке стоит одна из бусин A, C, E. У2: На втором – любая гласная, если первая буква согласная, и любая согласная, если первая гласная. У3: На третьем месте – одна из бусин C, D, E, не стоящая в цепочке на первом месте. Составим таблицу, в которой знак «0» – утверждение ложно. Свободен от «0» только второй столбец Пример 19: Правильный ответ - 2


Слайд 35

Решение (способ 1): Продолжим строки, чтобы понять закономерность четных элементов: Количество четных чисел в каждой строке увеличивается в два раза (т. к. длина строки тоже увеличивается в два раза). Если номер строки четный, то к этому количеству прибавляется ещё единица. Т.о., чётных чисел в 7-й строке – 42, в 8-й строке - 85 Цепочки символов (строки) создаются по следующему правилу. Первая строка состоит из одного символа – цифры «1». Каждая из последующих цепочек создается следующим действием: в очередную строку дважды записывается предыдущая цепочка цифр (одна за другой, подряд), а в конец приписывается еще одно число – номер строки по порядку (на i-м шаге дописывается число «i»). Вот первые 4 строки, созданные по этому правилу: (1) 1 (2) 112 (3) 1121123 (4) 112112311211234 Сколько раз в общей сложности встречаются в восьмой строке четные цифры (2, 4, 6, 8)? Пример 20:


Слайд 36

Первая строка состоит из одного символа - латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется «i»-я буква алфавита), к ней справа дважды подряд приписывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу: (1) A (2) BAA (3) СВААВАА (4) DCBAABAACBAABAA Пример 21: Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ Определите количество букв D в первых одиннадцати строках. Решение: Найдём закономерности, позволяющие решить задачу без выписывания одиннадцати строк. Пронумеруем наши последовательности (строки) и подсчитаем количество букв D в каждой из них. В соответствии с алгоритмом построения строк: в 4-й строке количество букв D – 1=20 в 5-й строке количество букв D – 2=21 в 6-й строке количество букв D – 4=22 Т.о. количество букв D в строке можно вычислить по формуле: 2 i-4 , где i- номер строки. Тогда количество букв D в 11-й строке будет равно 211-4 = 27= 128. Найдем суммарное количество букв D в строках с 4 по 11: 20+21+22+23+24+25+26+27 = 28-1 = 255 *Применяя формулу, которая «сворачивает» сумму степеней двойки: 1+2+4+8+…+2k =2k+1-1 Ответ: 255


Слайд 37

Строки (цепочки символов латинских букв) создаются по следующему правилу. Первая строка состоит из одного символа – латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется «i»-я буква алфавита), к ней справа дважды подряд приписывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу: (1) A (2) BAA (3) CBAABAA (4) DCBAABAACBAABAA Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ Запишите семь символов подряд, стоящие в восьмой строке со 126-го по 132-е место (считая слева направо). Пример 22: Решение (способ 1 – с помощью логических рассуждений): Найдём закономерности, позволяющие решить задачу без выписывания восьми строк. Заметим, что количество букв каждой строке можно вычислить по общей формуле: 2i-1, где i – номер строки. Поэтому, можно предположить, что в восьмой строке количество букв будет равно 28-1 =257


Слайд 38

Решение (продолжение): Начинаем рассуждения с букв, которые встречаются реже всего. Последняя в восьмой строке буква H будет на 1-м месте, тогда буква G будет встречаться на 2-м и 129-м местах (в 7-й строке 27-1=127 букв). Тогда буква F будет встречаться на 3-м, 66-м (с периодичностью 26-1=63 буквы), 130-м (с периодичностью 26-1=63 +1 буква – за счёт буквы G, появляющейся в предыдущей 7-й строке ), 193-м (опять с периодичностью 26-1=63 буквы) местах. Поэтому можно ограничиться построением строки с номером 5, поскольку именно она в 6-й строке начинается с буквы F и повторяется 2 раза: (5) EDCBAABAACBAABAADCBAABAACBAABAA Итак, мы определили, что буква G встречается на 129-м месте, следовательно, на 128-м будет буква A (т.к. строки повторяются), на 127-м снова будет буква A, на 126-м будет буква B (3 последние буквы строк (5,6)). Получаем ответ: BAA + буква G (начало строки (7)+начало строки (6) FED ). Ответ: BAAGFED


Слайд 39

Строки (цепочки символов латинских букв) создаются по следующему правилу. Первая строка состоит из одного символа – латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется «i»-я буква алфавита), к ней справа дважды подряд приписывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу: (1) A (2) BAA (3) CBAABAA (4) DCBAABAACBAABAA Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ Запишите семь символов подряд, стоящие в восьмой строке со 126-го по 132-е место (считая слева направо). Пример 22: Решение (способ 2 – предложенный К.Ю. Поляковым): используя приведенное правило, можно построить следующие строки: (5) EDCBAABAACBAABAADCBAABAACBAABAA (6) FEDCBAABAACBAABAADCBAABAACBAABAAEDCBAABAACBAABAADCB AABAACBAABAA ... мы быстро убедимся, что следующие строки получаются достаточно длинные, и легко запутаться, отсчитывая символы с номерами 126-132 в восьмой строке. Попробуем найти закономерности, позволяющие решить задачу без выписывания 8-ой строки.


Слайд 40

Прежде всего, заметим, что длины первых строк 1, 3, 7, 15, … – это числа вида 2i - 1, где i – номер строки; таким образом, длина 7-ой строки – 127, а длина восьмой – 255 символов. Восьмая строка строится так: восьмая буква латинского алфавита (H) и затем – два раза седьмая строка (сверху написаны номера символов) Символы 126-132 находятся на границе двух цепочек, повторяющих 7-ую строку; заметим, что в соответствии с заданным алгоритмом можно легко определить первые символы в 7-ой строке (GFEDC) и последние символы (AABAA) Далее сразу находим, что интересующая нас часть 8-ой строки имеет вид: Таким образом, правильный ответ – BAAGFED


Слайд 41

Упаковка информации методом RLE-кодирования состоит в следующем. Упакованная последовательность содержит управляющие байты, за каждым управляющим байтом следует один или несколько байтов данных. Если старший бит управляющего байта равен 1, то следующий за управляющим байт данных при распаковке нужно повторить столько раз, сколько записано в оставшихся 7 битах управляющего байта. Если же старший бит управляющего байта равен 0, то надо взять несколько следующих байтов данных без изменения. Сколько именно – записано в оставшихся 7 битах управляющего байта. Например, управляющий байт 10000111 говорит о том, что следующий за ним байт надо повторить 7 раз, а управляющий байт 00000100 – о том, что следующие за ним 4 байта надо взять без изменений. После кодирования методом RLE получилась следующая последовательность байтов (первый байт – управляющий): 00000011 10101010 00000010 10101111 10001111 11111111. Сколько байт будет содержать данная последовательность после распаковки? Впишите в бланк только число. Пример 23:


Слайд 42

Решение: 00000011 10101010 00000010 10101111 10001111 11111111 Первый управляющий байт 00000011. Его старший бит 0 говорит о том, что следующие 112 = 3 символа повторяются по одному разу. Получаем 3 символа. Следующий управляющий байт (пятый) – 10001111 и начинается он с 1, что говорит о том, что следующий за ним символ нужно повторить 11112 =15 раз. Получаем еще 15 символов. Полная длина распакованной последовательности равна 3 + 15 = 18 символов. Итого: Таким образом, правильный ответ – 18


Слайд 43

Пример 24:


Слайд 44

Решение:


Слайд 45

Решение:


Слайд 46

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


×

HTML:





Ссылка: