Одна из сложных разновидностей задач, встречающихся в Едином государственном экзамене, связана с цепочками. Общий смысл таких задач: дано некое правило. - презентация

1 Одна из сложных разновидностей задач, встречающихся в Едином государственном экзамене, связана с цепочками. Общий смысл таких задач: дано некое правило формирования цепочек из букв или цифр путем соединения на очередном шаге двух копий цепочек, полученных на предыдущем шаге, и дописывания к ним очередного символа, а в качестве ответа требуется указать символ либо группу символов, расположенных в позиции (позициях) с указанным порядковым номером (номерами) от начала. В демонстрационных вариантах ЕГЭ по информатике за различные годы такая задача реализуется в следующих видах: По материалам Журнала 4 / 2011 // ИНФОРМАТИКА ЦЕПОЧКИ

2 2004 A24. Записано 6 строк, каждая имеет свой номер от 0 до 5. В 0-й строке записана цифра 0 (ноль). Каждая последующая строка состоит из двух повторений предыдущей и добавленного в конец своего номера (в i-й строке в конце приписана цифра i). Ниже показаны первые четыре строки, сформированные по описанному правилу (в скобках записан номер строки): (0) 0 (1) 001 (2) (3) Какая цифра стоит в последней строке на 62-м месте (считая слева направо)? 1) 1; 3) 3; 2) 2; 4) B6. Записано 7 строк, каждая имеет свой номер от 0 до 6. В начальный момент в строке записана цифра 0 (ноль). На каждом из последующих шести шагов выполняется следующая операция: в очередную строку записывается удвоенная предыдущая строка, а в конец строки приписывается очередная цифра (на i-м шаге приписывается цифра i). Для удобства в скобках пишется номер строки (начиная с 0). Ниже показаны первые строки, сформированные по описанному правилу: (0) 0 (1) 001 (2) (3) Какая цифра стоит в последней строке на 123-м месте (считая слева направо)? (Ответ: 2.)

3 2006 B6. Цепочки символов (строки) создаются по следующему правилу. Первая строка состоит из одного символа цифры 1. Каждая из последующих цепочек создается такими действиями: в очередную строку дважды записывается цепочка цифр из предыдущей строки (одна за другой, подряд), а в конец приписывается еще одно число номер строки по порядку (на i-м шаге дописывается число i). Вот первые 4 строки, созданные по этому правилу: (1) 1 (2) 112 (3) (4) Какая цифра стоит в седьмой строке на 120-м месте (считая слева направо)? (Ответ: 1.) 2007 B6. Цепочки символов (строки) создаются по следующему правилу. Первая строка состоит из одного символа цифры 1. Каждая из последующих цепочек создается следующим действием: в очередную строку дважды записывается предыдущая цепочка цифр (одна за другой, подряд), а в конец приписывается еще одно число номер строки по порядку (на i-м шаге дописывается число i). Вот первые 4 строки, созданные по этому правилу: (1) 1 (2) 112 (3) (4) Сколько раз в общей сложности встречаются в восьмой строке четные цифры (2, 4, 6, 8)? (Ответ: 85.)

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

5 2010 B8. Строки (цепочки латинских букв) создаются по следующему правилу. Первая строка состоит из одного символа латинской буквы А. Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется i-я буква алфавита), к ней слева дважды подряд приписывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу: (1) A (2) AAB (3) AABAABC (4) AABAABCAABAABCD Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ Запишите шесть символов подряд, стоящие в седьмой строке со 117-го по 122-е место (считая слева направо). (Ответ: AABAAB.) 2011 B8. Строки (цепочки символов латинских букв) создаются по следующему правилу. Первая строка состоит из одного символа латинской буквы А. Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется i- я буква алфавита), к ней слева дважды подряд приписывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу: (1) A (2) AAB (3) AABAABC (4) AABAABCAABAABCD Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ Имеется задание: Определить символ, стоящий в n-й строке на позиции 2n–1–5, считая от левого края цепочки. Выполните это задание для n = 8. (Ответ: С.)

6 Как же решать подобные задачи? Очевидно, что процесс решения может быть во всех подобных случаях одинаков (кроме задач на определение количества символов, где можно рассчитывать на некоторое упрощение алгоритма решения), независимо от того, состоит ли цепочка из букв или цифр, начинается ли нумерация цепочек с нуля или с единицы и с какой стороны (в начале или в конце) дописывается на каждом шаге новый символ. Решим для примера задачу 2005 B6. Записано 7 строк, каждая имеет свой номер от 0 до 6. В начальный момент в строке записана цифра 0 (ноль). На каждом из последующих 6 шагов выполняется следующая операция: в очередную строку записывается удвоенная предыдущая строка, а в конец строки приписывается очередная цифра (на i-м шаге приписывается цифра i). Для удобства в скобках пишется номер строки (начиная с 0). Ниже показаны первые строки, сформированные по описанному правилу: (0) 0 (1) 001 (2) (3) Какая цифра стоит в последней строке на 123-м месте (считая слева направо)?

7 Научимся расплетать предполагаемую цепочку по шагам, чтобы найти в ней нужное. Сначала посмотрим еще раз на принцип формирования цепочек. Первая по счету (и нулевая по порядковому номеру) цепочка имеет длину 1. Далее на каждом очередном шаге длина цепочки удваивается, а затем увеличивается еще на 1 (приписыванием в конце очередной цифры номера данной цепочки): цепочки (i) Длина цепочки Отсюда нетрудно вывести формулу определения длины цепочки по ее номеру i: = 2 i + 1 – 1 (Кстати, нетрудно понять, что если цепочки нумеровались бы не с нуля, а с единицы, при соблюдении всех прочих условий, то в данной формуле в показателе степени для двойки прибавлять единицу было бы не нужно.) Таким образом, искомая цифра (на 123-м месте) отстоит от конца итоговой цепочки на 4 позиции левее. Вспомнив, что на каждом шаге к удваиваемой цепочке каждый раз дописывалась одна цифра, равная порядковому номеру очередной цепочки, нетрудно сообразить, что итоговая цепочка будет завершаться цифрами: … , где шестерка стоит на последнем, 127- м, месте. И, отсчитав 4 позиции влево, получить, что на 123-м месте находится цифра 2. позиции Цифра

8 Такие же сравнительно простые рассуждения нетрудно проводить и в других случаях, когда искомый символ располагается близко к концу цепочки (а точнее не более чем в i позициях от ее конца, где i порядковый номер цепочки, считая с нуля) либо вблизи от позиции, соответствующей концу какой-либо составляющей ее подцепочки, номера этих внутренних позиций поможет определить таблица, построенная по вычисленным согласно вышеприведенной формуле значениям длин подцепочек. цепочки (i) Конечная позиция цепочки Окончание подцепочки

9 Однако бывают и задачи, где требуется искать символ (либо символы) в середине цепочек. И тогда уже не обойтись без полноценного расплетания. Второе типовое решение. Решим достаточно свежую (по году) задачу 2010 B8. Строки (цепочки латинских букв) создаются по следующему правилу. Первая строка состоит из одного символа латинской буквы А. Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется i-я буква алфавита), к ней слева дважды подряд приписывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу: (1) A (2) AAB (3) AABAABC (4) AABAABCAABAABCD Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ Запишите шесть символов подряд, стоящие в седьмой строке со 117-го по 122-е место (считая слева направо). Сначала тем же самым способом, как и в предыдущей задаче, найдем формулу для вычисления длины итоговой цепочки, начав выписывать длины первых цепочек, приведенных в условии:

10 цепочкиЦепочкаДлина цепочки 1A1 2AAB3 3AABAABC7 4AABAABC AABAABCD15 Впрочем, разобравшись уже с предыдущей задачей, мы можем сразу сказать, что искомая формула будет такой: = 2 i – 1 (Напомним: прибавление единицы в показателе степени двойки здесь не требуется, так как нумерация цепочек производится не с нуля, а с единицы.) Тогда, очевидно, длина итоговой, 7- й, цепочки будет равна 2 7 – 1 = 127 символам. А вот сейчас начинается самое интересное. Теперь мы должны научиться расплетать цепочку по шагам назад. Итак… 1. Согласно правилам, указанным в условии задачи, итоговая, 7-я, цепочка имеет формат: (6) (6) G При этом согласно выведенной нами формуле 6-я цепочка имеет длину 2 6 – 1 = 63 символа. Тогда в нашу табличку, обозначающую формат рассматриваемой строки- цепочки, можно добавить обозначения соответствующих номеров позиций символов (При этом нужно не забывать, что отсчет номеров позиций (как и отсчет дней по календарю) ведется по следующим правилам: если предыдущая подцепочка начинается с символа с порядковым номером n и имеет длину d, то номер символа, которым заканчивается эта подцепочка, вычисляется по формуле (n + d – 1), а следующая подцепочка будет начинаться с символа под номером (n + d).): (6) G 1–6364–126127

11 2. Очевидно, что искомые нами символы располагаются во второй по счету подстроке (6). Продолжим расплетание цепочек еще на один шаг назад, раскрывая эту вторую цепочку (6) и оставляя неизменными остальные части таблицы. При этом учитываем, что длина предыдущей, 5-й, цепочки равна 2 5 – 1 = 31 символу. (6) G 1–6364– (6) (5) F G 1– Искомые символы находятся во второй раскрытой нами цепочке (5). Расплетем и ее, вычислив, что длина цепочки (4) равна 2 4 – 1 = 15 символам. (6) G 1–6364– (6) (5) F G 1– (6) (5)(4)(4)(4)EF G 1– Увидев, что искомые символы находятся во второй раскрытой нами цепочке (4), расплетем и ее (вычислив, что длина цепочки (3) равна 2 3 – 1 = 7 символам): (6) (5)(4)(3)(3)(3)(3)DEF G 1– В данном случае нам повезло: все нужные символы находятся в одной подцепочке (вторая (3)). А ее уже совсем нетрудно выписать полностью, подсмотрев ее в условии задачи: ААВААВС. AABAABC

12 Третье типовое решение. А теперь рассмотрим две модифицированные задачи, в которых требуется подсчитывать количество единиц либо количество четных цифр. Самый простой способ такого подсчета попытаться вывести общую формулу, аналогично тому, как мы ранее определяли формулу для вычисления длины цепочек. Задача 2007 B6 цепочкиЦепочкаКол-во_четных цифр …10 Формула (рекуррентная): N i = N i–1 * 2 + ((i – 1) mod 2), N1 = 0. Задача 2008 B6 цепочкиЦепочкаКол-во_единиц Формула: 2 i – 1, где i номер цепочки. (В обоих случаях формулы действительны до цепочки с номером 9 включительно; далее же надо учитывать, что в начале на каждом шаге должны дописываться двухзначные числа 10, 11, 12, …, потом трехзначные и т.д., но в задачах ЕГЭ пока до таких номеров строк составители заданий не доходили.)

13 Однако вывод подобных формул представляет дополнительные затруднения для школьников. Поэтому для решения таких задач можно предложить более простой табличный метод, придуманный одним из авторов данной статьи. Хитрость здесь в том, что та или иная цифра i впервые появляется в цепочке с номером i (что очевидно), а дальше на каждом шаге количество таких цифр удваивается. Поэтому очень легко составить таблицу количеств каждой интересующей нас цифры, а потом в графе, соответствующей требуемой строке, подсчитать сумму количеств этих цифр. Начнем с более простой по сюжету задачи 2008 B6. Цепочки символов (строки) создаются по следующему правилу: Первая строка состоит из одного символа цифры 1. Каждая из последующих цепочек создается такими действиями: в начало записывается число номер строки по порядку (для i-й строки ставится число i), далее дважды подряд записывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу: (1) 1 (2) 211 (3) (4) Сколько раз встречается цифра 1 в первых семи строках (суммарно)? Здесь требуется подсчитать количество единиц, которые начинают появляться сразу с первой же цепочки. Поэтому таблица будет выглядеть так: _цепочки Суммарно: Цифра_

14 Возможна также модификация данной задачи, в которой нумерация цепочек и их построение начинается не с единицы, а с нуля: (0) 0(1) 001(2) (3) и т.д. Пусть, например, в этом случае надо подсчитать суммарное количество единиц в цепочке с номером 9. Очевидно, в этом случае наша таблица будет иметь такой вид: _цепочки Цифра_ В этом случае надо учесть, что в самой первой цепочке (с номером 0) единичек нет вообще, впервые единица появляется в цепочке с номером 1, а далее в таблице записывается все та же волшебная последовательность чисел, хорошо известная каждому старшекласснику, последовательность степеней двойки. Ответ: 256.

15 Теперь рассмотрим более сложную задачу 2007 B6. Цепочки символов (строки) создаются по следующему правилу. Первая строка состоит из одного символа цифры 1. Каждая из последующих цепочек создается следующим действием: в очередную строку дважды записывается предыдущая цепочка цифр (одна за другой, подряд), а в конец приписывается еще одно число номер строки по порядку (на i-м шаге дописывается число i). Вот первые 4 строки, созданные по этому правилу: (1) 1 (2) 112 (3) (4) Сколько раз в общей сложности встречаются в восьмой строке четные цифры (2, 4, 6, 8)? Здесь таблица составляется точно так же практически механической записью чисел степеней двойки, но она будет содержать несколько строк по одной для каждой четной цифры: Цифра _цепочки Всего_четных_ цифр85

16 А в заключение рассмотрим еще одну задачу, которая, правда, не входит в демоварианты ЕГЭ (пока), но предлагалась московским школьникам во время пробного ЕГЭ и вызвала некоторые трудности. Цепочки символов (строки) создаются по следующему правилу. Первая строка состоит из одного символа цифры 1. Каждая из последующих цепочек создается следующим действием: сначала записывается число номер строки по порядку (т.е. на i-м шаге записывается число i), а далее дважды записывается предыдущая цепочка цифр (одна за другой, подряд). Вот первые 4 строки, созданные по этому правилу: (1) 1 (2) 211 (3) (4) Сколько раз в общей сложности встречаются в 10-й строке нечетные цифры (1, 3, 5, 7, 9)? Для решения этой задачи составляем таблицу, аналогичную предыдущей: Цифра _цепочки Всего_нечетных_ цифр683 Единственное, на что нужно обязательно обратить внимание (и на чем споткнулись многие учащиеся, решая эту задачу), на то, что в 10-й строке, кроме единиц, накапливаемых за счет удвоения предыдущей подцепочки, вначале дописывается новое число 10, которое тоже содержит единицу. Поэтому-то в последнем столбце в строке, соответствующей цифре 1, к очередной степени двойки (512) прибавляется 1. А затем, как и в предыдущей задаче, нужно подсчитать сумму чисел для всех строк последнего столбца.