Э презентация

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

Цель данной работы — помочь вам «набить руку» в решении тестов ЕГЭ, разобраться с наиболее сложными заданиями и узнать объективный уровень своих знаний.

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

количество строк, n – количество столбцов.

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

последний отрезок полностью совпадет с первым, так как после третьего выполнения цикла черепашка полностью обернется вокруг своей оси и окажется в той же точке, что и изначально. Так что на экране появится правильный треугольник. Внутренние углы получившейся фигуры равны: 3*(180-120)=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

НАЧАЛО
ПОКА <справа свободно> вправо
ПОКА <сверху свободно> вверх
ПОКА <слева свободно> влево
ПОКА <снизу свободно> вниз
КОНЕЦ

Пример 4:

ПОКА <сверху свободно> вверх
ПОКА <слева свободно> влево
ПОКА <снизу свободно> вниз
КОНЕЦ

Решение:

Для того, чтобы РОБОТ вернулся обратно в ту клетку, откуда он начал движения, четыре стенки должны быть расставлены так, чтобы он упирался в них последовательно при движении вправо, вверх, влево и, наконец, вниз при условии свободного «коридора» движения. Алгоритм движения заканчивается после выполнения цикла: ПОКА <снизу свободно> вниз, поэтому нужно рассматривать лишь те клетки, где есть стенка снизу. Отметим на исходной карте чёрным кружочком такие клетки-кандидаты. Из них только 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 команд, указывая лишь номера команд. (Например, программа 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

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

Пример 5:

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

однобайтовыми двоичными числами, две команды, которым присвоены номера:
1. сдвинь влево
2. вычти 1
Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд влево, а выполняя вторую, вычитает из него 1. Исполнитель начал вычисления с числа 91 и выполнил цепочку команд 112112 . Запишите результат в десятичной системе.
Решение:
«Сдвиг влево» - так называется операция, при которой все биты числа в ячейке (регистре) сдвигаются на 1 бит влево, в младший бит записывается нуль, а старший бит попадает в специальную ячейку – бит переноса.

Пример 6:

Сдвиг влево двоичных разрядов влево равнозначен умножению числа на 102=210 ( вправо, соответственно – делению нацело на 102=210).
Но если в старшем (7-ом) бите исходного числа была 1, то она после сдвига влево окажется в бите переноса и будет потеряна, поэтому мы фактически получим остаток от деления удвоенного числа на 28=25610=1000000002

Бит переноса

Правильный ответ – 171

Определите значение целочисленных переменных a и b после выполнения фрагмента программы:






1) a = 0, b = 18 2) a = 11, b = 19 3) a = 10, b = 18 4) a = 9, b = 17

Для решения нужно использовать «ручную прокрутку» программы, то есть, выполнить вручную все действия. Наиболее удобно и наглядно это получается при использовании таблицы, где в первом столбце записаны операторы программы, а в остальных показаны изменения переменных при выполнении этих операторов:

Пример 7:

Решение:

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

Таблица значений переменных:

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

Определите значение целочисленных переменных a и b после выполнения фрагмента программы (ниже представлена одна и та же программа, записанная на разных языках программирования):

Решение:
a=42
b=14
a=3
b=42
a=14

Пример 9:

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

с=55

Пример 11:

значение переменной s после выполнения данного алгоритма, при любых значениях элементов массива А?
1) Максимальному элементу в массиве A
2) Индексу максимального элемента в массиве A (первому из них, если максимальных элементов несколько)
3) Индексу максимального элемента в массиве A (последнему из них, если максимальных элементов несколько)
4) Количеству элементов, равных максимальному в массиве A.

Решение: Нетрудно заметить, что в циклическом операторе по выполнению условия IF A(i)>A(j) переменная j перехватывает индекс наибольшего в паре A(i), A(j) элемента. Следовательно, по завершении циклического оператора переменная j примет значение индекса последнего наибольшего элемента массива.
Правильный ответ - 3

Пример 13:

квадратной таблицы, в которой для элемента массива A[i,j] величина i является номером строки, а величина j – номером столбца, в котором расположен элемент. Тогда данный алгоритм








меняет местами
1) два столбца в таблице
2) две строки в таблице
3) элементы диагонали и k-ой строки таблицы
4) элементы диагонали и k-го столбца таблицы

Пример 14:

в качестве вспомогательной ячейки. Элементы A[i,i] расположены на главной диагонали матрицы, а у элементов A[k,i] фиксирован номер строки (k), но меняется в цикле номер столбца. Следовательно, в программе элементы главной диагонали обмениваются с первой строкой (при k=1).

Решение:
(предложенное К.Ю. Поляковым)

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

1) два столбца в таблице
2) две строки в таблице
3) элементы диагонали и k-ой строки таблицы
4) элементы диагонали и k-го столбца таблицы

до 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:

На первом месте в цепочке стоит одна из бусин 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

чисел в каждой строке увеличивается в два раза (т. к. длина строки тоже увеличивается в два раза). Если номер строки четный, то к этому количеству прибавляется ещё единица. Т.о., чётных чисел в 7-й строке – 42, в 8-й строке - 85

Цепочки символов (строки) создаются по следующему правилу. Первая строка состоит из одного символа – цифры «1». Каждая из последующих цепочек создается следующим действием: в очередную строку дважды записывается предыдущая цепочка цифр (одна за другой, подряд), а в конец приписывается еще одно число – номер строки по порядку (на i-м шаге дописывается число «i»). Вот первые 4 строки, созданные по этому правилу:
(1) 1
(2) 112
(3) 1121123
(4) 112112311211234

Сколько раз в общей сложности встречаются в восьмой строке четные цифры (2, 4, 6, 8)?

Пример 20:

Первая строка состоит из одного символа - латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на 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

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

Пример 22:

Решение (способ 1 – с помощью логических рассуждений): Найдём закономерности, позволяющие решить задачу без выписывания восьми строк. Заметим, что количество букв каждой строке можно вычислить по общей формуле: 2i-1, где i – номер строки. Поэтому, можно предположить, что в восьмой строке количество букв будет равно 28-1 =257

в восьмой строке буква 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

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

Пример 22:

Решение (способ 2 – предложенный К.Ю. Поляковым): используя приведенное правило, можно построить следующие строки:
(5) EDCBAABAACBAABAADCBAABAACBAABAA
(6) FEDCBAABAACBAABAADCBAABAACBAABAAEDCBAABAACBAABAADCB AABAACBAABAA
...
мы быстро убедимся, что следующие строки получаются достаточно длинные, и легко запутаться, отсчитывая символы с номерами 126-132 в восьмой строке.
Попробуем найти закономерности, позволяющие решить задачу без выписывания 8-ой строки.

… – это числа вида 2i - 1, где i – номер строки; таким образом, длина 7-ой строки – 127, а длина восьмой – 255 символов. Восьмая строка строится так: восьмая буква латинского алфавита (H) и затем – два раза седьмая строка (сверху написаны номера символов)





Символы 126-132 находятся на границе двух цепочек, повторяющих 7-ую строку; заметим, что в соответствии с заданным алгоритмом можно легко определить первые символы в 7-ой строке (GFEDC) и последние символы (AABAA)
Далее сразу находим, что интересующая нас часть 8-ой строки имеет вид:





Таким образом, правильный ответ – BAAGFED

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

Пример 23:

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






Таким образом, правильный ответ – 18