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

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

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

Двумерный массив А(m,n) можно представить в виде следующей матрицы: A 11 A 12 A 13 …A 14 A 21 A 22 A 23 …A 24 …………… A m1 A m2 A m3 …A mn где m – количество строк, n – количество столбцов. 1.массив – это набор однотипных элементов, имеющих общее имя; 2.для обращения к элементу массива используют круглые (или квадратные – на языке Паскаль) скобки, запись A(i) обозначает элемент массива A с номером (индексом) i; 3.матрица (двухмерный массив) – это прямоугольная таблица однотипных элементов; 4.если матрица имеет имя A, то обращение A(i,k) обозначает элемент, расположенный на пересечении строки i и столбца k; 5.элементы, у которых номера строки и столбца совпадают (i=j), расположены на главной диагонали. 6.Номер столбца j элемента на побочной диагонали можно вычислить по формуле j=n-i+1, где n – размер квадратной матрицы, i – номер строки

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

Пример 2:

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

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

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

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

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

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

У исполнителя Утроитель две команды, которым присвоены номера: 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 из исходного числа 3. Число Команда12211 Пример 5: Правильный ответ

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

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

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

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

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

Определите значение целочисленных переменных a и b после выполнения фрагмента программы (ниже представлена одна и та же программа, записанная на разных языках программирования): БейсикПаскаль a=42 b=14 a=a\b b=a*b a=b\a \ - стандартная операция, вычисляющая результат деления нацело первого аргумента на второй a:=42; b:=14; a:=a div b; b:=a*b; a:=b div a; {div - стандартная операция, вычисляющая результат деления нацело первого аргумента на второй} 1) a = 42, b = 14 2) a = 1, b = 423) a = 0, b = 5884) a = 14, b = 42 Решение: a=42 b=14 a=3 b=42 a=14 Пример 9: Правильный ответ - 4

Пример 10:

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

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

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

Пример 12:

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

Дан фрагмент программы, обрабатывающей массив A из n элементов: Чему будет равно значение переменной s после выполнения данного алгоритма, при любых значениях элементов массива А? 1) Максимальному элементу в массиве A 2) Индексу максимального элемента в массиве A (первому из них, если максимальных элементов несколько) 3) Индексу максимального элемента в массиве A (последнему из них, если максимальных элементов несколько) 4) Количеству элементов, равных максимальному в массиве A. БейсикПаскаль j = 1 FOR i = 1 TO n IF A(i)>A(j) THEN j=I NEXT I s=j j:=1; for i:=1 to n do if A[i]>A[j] then j:=i; s:=j; Решение: Нетрудно заметить, что в циклическом операторе по выполнению условия IF A(i)>A(j) переменная j перехватывает индекс наибольшего в паре A(i), A(j) элемента. Следовательно, по завершении циклического оператора переменная j примет значение индекса последнего наибольшего элемента массива. Правильный ответ - 3 Пример 13:

Дан фрагмент программы, обрабатывающей двухмерный массив A(n×n): Представим массив в виде квадратной таблицы, в которой для элемента массива A[i,j] величина i является номером строки, а величина j – номером столбца, в котором расположен элемент. Тогда данный алгоритм меняет местами 1) два столбца в таблице 2) две строки в таблице 3) элементы диагонали и k-ой строки таблицы 4) элементы диагонали и k-го столбца таблицы Пример 14: БейсикПаскаль k = 1 for i=1 to n c = A(i,i) A(i,i)= A(k,i) A(k,i)= c next i k := 1; for i:=1 to n do begin c := A[i,i]; A[i,i] := A[k,i]; A[k,i] := c; end

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

Пример 15:

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

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

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

В программе описан одномерный целочисленный массив А с индексами от 0 до 10. Ниже представлен фрагмент одной и той же программы, записанный на разных языках программирования, в котором значения элементов сначала задаются, а затем меняются. Чему окажутся равны элементы этого массива? БейсикПаскаль FOR i=0 ТО 10 A(i)=i-1 NEXT i FOR i=10 TO 1 STEP -1 A(i-l)=A(i) NEXT i for i:=0 to 10 do A[i]:=i-l; for i:=10 downto 1 do A[i-1]:=A[i]; Решение: После первого цикла: После второго цикла: Правильный ответ - 2 Пример 17:

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

Для составления цепочек используются бусины, помеченные буквами: 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: 1) CBE2) ADD 3) ECE4) EAD У1:1111 У2:0110 У3:1101 Правильный ответ - 2

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

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

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

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

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

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

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

Решение: Первый управляющий байт Его старший бит 0 говорит о том, что следующие 11 2 = 3 символа повторяются по одному разу. Получаем 3 символа. Следующий управляющий байт (пятый) – и начинается он с 1, что говорит о том, что следующий за ним символ нужно повторить =15 раз. Получаем еще 15 символов. Полная длина распакованной последовательности равна = 18 символов. Итого: Таким образом, правильный ответ – 18 управляющийбайты 1-3управляющийбайты , , (повторяется)

Пример 24:

Решение:

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