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

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

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

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

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

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

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

7 Цепочки символов (строки) создаются по следующему правилу: Первая строка состоит из одного символа – цифры «1». Каждая из последующих цепочек создается такими действиями: в начало записывается число – номер строки по порядку (для i-й строки ставится число «i»), далее дважды подряд записывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу: (1) 1 (2) 211 (3) (4) Сколько раз встречается цифра «1» в первых семи строках (суммарно)? Пример 4: Решение: Найдём закономерности, позволяющие решить задачу без выписывания семи строк. Заметим, что количество единиц в каждой строке можно вычислить по общей формуле: 2 i-1, где i – номер строки. Поэтому, можно предположить, что ответ можно получить следующим образом: = = 127 *Применяя формулу, которая «сворачивает» сумму степеней двойки: …+2 k =2 k+1 -1

8 Записано 7 строк, каждая имеет свой номер – от «0»- до «6»-й. В начальный момент в строке записана цифра 0 (ноль). На каждом из последующих 6 шагов выполняется следующая операция: в очередную строку записывается удвоенная предыдущая строка, а в конец строки приписывается очередная цифра (на i-м шаге приписывается цифра i). Для удобства в скобках пишется номер строки (начиная с 0). Ниже показаны первые строки, сформированные по описанному правилу: (0) 0 Какая цифра стоит в последней строке (1) 001 на 123-м месте (считая слева направо)? (2) (3) Пример 5: Решение: Найдём закономерности, позволяющие решить задачу без выписывания семи строк. Заметим, что количество цифр в каждой строке можно вычислить по общей формуле: 2 i+1 -1, где i – номер строки. Поэтому, можно предположить, что в строке с номером 6 будет =127 цифр. Начинаем рассуждения с цифр, которые встречаются реже всего. Последняя цифра (6) будет на 127 месте, тогда цифра (5) будет встречаться на 126-м и 63-м местах. Поэтому можно ограничиться построением строки с номером 4, поскольку именно она будет повторяться в строке с номером 5 (и число 5 окажется на 126 месте): (4) Следовательно, на 125 окажется число 4, 124– 3, 123 – 2

9 Цепочки символов (строки) создаются по следующему правилу: первая строка состоит из одного символа, это цифра 1. Каждая из следующих цепочек создается так: сначала записывается порядковый номер данной строки, далее дважды записывается вся цепочка цифр из предыдущей строки. Первые 4 строки, созданные по этому правилу, выглядят следующим образом: 1 Сколько раз в общей сложности встречаются 211 в 10-й строке нечетные цифры (1,3, 5, 7,9)? Пример 6: Найдём закономерности, позволяющие решить задачу без выписывания десяти строк. Заметим, что количество нечётных чисел в каждой строке можно вычислить по общим формулам: количество единиц в каждой строке можно вычислить по общей формуле: 2 i-1, где i – номер строки, т.е. в 10-й строке единиц будет 2 9 =512; количество троек в каждой строке (начиная с третьей) можно вычислить по общей формуле: 2 i-3, где i – номер строки, т.е. в 10-й строке троек будет 2 7 =128; количество пятёрок в каждой строке (начиная с пятой) можно вычислить по общей формуле: 2 i-5, где i – номер строки, т.е. в 10-й строке пятёрок будет 2 5 =32; количество семёрок в каждой строке (начиная с седьмой) можно вычислить по общей формуле: 2 i-7, где i – номер строки, т.е. в 10-й строке семёрок будет 2 3 =8; и, что и так понятно, количество девяток в десятой строке равно 2 и это можно вычислить по общей формуле: 2 i-9, где i – номер строки, т.е. действительно в 10-й строке девяток будет 2 1 =2. Поэтому, можно предположить, что ответ можно получить следующим образом: = = 682 Решение:

10 Цепочки символов (строки) создаются по следующему правилу: в начальный момент в строке записана цифра 0 (ноль). На каждом из последующих 9 шагов выполняется следующая операция: в очередную строку дважды записывается предыдущая строка, а в конец строки приписывается очередная цифра (на n-м шаге приписывается цифра n.). Ниже показаны первые строки, сформированные по описанному правилу (в скобках записан номер строки, начиная с 0). (0) 0 (1) 001 (2) (3) Сколько раз встретится цифра 1 в последней строке? Пример 7: Решение: Найдём закономерности, позволяющие решить задачу без выписывания десяти строк. Заметим, что количество единиц в каждой строке (кроме нулевой) можно вычислить по общей формуле: 2 i-1, где i – номер строки. Поэтому, можно предположить, что в десятой строке (после девятого шага исполнения алгоритма построения строк) количество цифр 1 будет равно = 2 8 = 256

11 В начальный момент в строке записана цифра 0 (ноль). На каждом из последующих 9 шагов выполняется следующая операция: в очередную строку дважды записывается предыдущая строка, а в конец строки приписывается очередная цифра (на i-м шаге приписывается цифра i). Ниже показаны первые строки, сформированные по описанному правилу (в скобках записан номер строки, начиная с 0). (0) 0 (1) 001 (2) (3) Какая цифра стоит в последней строке на 1022-м месте? Пример 8: Решение: Найдём закономерности, позволяющие решить задачу без выписывания десяти строк. Заметим, что количество цифр в каждой строке можно вычислить по общей формуле: 2 i+1 -1, где i – номер строки (от 0 до 9). Поэтому, можно предположить, что в строке с номером 9 будет =1023 цифр. Начинаем рассуждения с цифр, которые встречаются реже всего. Последняя цифра (9) будет на 1023 месте, тогда цифра (8) будет встречаться на 1022-м и 511-м местах. Следовательно, на 1022-м месте окажется число 8

12 Первая строка состоит из одного символа - латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется «i»-я буква алфавита), к ней справа дважды подряд приписывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу: (1) A (2) BAA (3) СВААВАА (4) DCBAABAACBAABAA Пример 9: Латинский алфавит (для справки): 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

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

14 Решение (продолжение): Начинаем рассуждения с букв, которые встречаются реже всего. Последняя в восьмой строке буква 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

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

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

17 Строки (цепочки символов латинских букв) создаются по следующему правилу. Первая строка состоит из одного символа - латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется «i»-я буква алфавита), к ней слева дважды подряд приписывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу: 1)А 2)ААВ 3)ААВААВС 4) AABAABCAABAABCD Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ Запишите шесть символов подряд, стоящие в седьмой строке с 53-го по 58-е место (считая слева направо). Пример 11: Решение: Определим номера букв в латинском алфавите: A B C D E F G H … Z Найдём закономерности, позволяющие решить … 26 задачу без выписывания семи строк. Заметим, что количество букв в каждой строке можно вычислить по общей формуле: 2 i -1, где i – номер строки. Поэтому, можно предположить, что в строке с номером 7 будет =127 букв. Начинаем рассуждения с букв, которые встречаются реже всего. Последняя буква в седьмой строке G будет на 127 месте, тогда буква F будет встречаться на 126-м и 63-м местах. Следовательно, на 62-м месте будет стоять буква E, на 61-м месте – буква D, на 60-м месте – C, на 59-м – B, 58-м – A. Это совпадает с фрагментом строки 4), если отсчитывать назад от последней буквы A (которая будет в седьмой строке стоять на 58-м месте), то получаем ответ: CAABAA

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

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

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