cepochki

Цепочки
19 января
2012

№ 4 / 2011 // ИНФОРМАТИКА
Решение задач ЕГЭ


На основе работы О.Б. Богомоловой, д. п. н., учителя информатики и математики ГОУ СОШ № 1360, Восточный округ г. Москвы и Д.Ю. Усенкова, ст. н. с. Института информатизации образования Российской академии образования, Москва
Одна из сложных разновидностей задач, встречающихся в Едином государственном экзамене, связана с цепочками. Общий смысл таких задач: дано некое правило формирования цепочек из букв или цифр путем соединения на очередном шаге двух копий цепочек, полученных на предыдущем шаге, и дописывания к ним очередного символа, а в качестве ответа требуется указать символ либо группу символов, расположенных в позиции (позициях) с указанным порядковым номером (номерами) от начала. В демонстрационных вариантах ЕГЭ по информатике за различные годы такая задача реализуется в следующих видах:

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

РЕШЕНИЕ
№ цепочки (i)
0
1
2
3
4
5

Длина цепочки
D=2i+1-1
1
3
7
15
31
63

Структура цепочки
(0)
(0) (0) 1
(1) (1) 2
(2) (2) 3
(3) (3) 4
(4) (4) 5

Конец цепочки
0
01
012
0123
01234
012345


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

РЕШЕНИЕ
№ цепочки (i)
0
1
2
3
4
5
6

Длина цепочки
d=2i+1-1
1
3
7
15
31
63
127

Структура цепочки
(0)
(0) (0) 1
(1) (1) 2
(2) (2) 3
(3) (3) 4
(4) (4) 5
(5) (5) 6

Конец цепочки
0
01
012
0123
01234
012345
0123456

Место
121
122
123
124
125
126
127

Цифра
0
1
2
3
4
5
6



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

РЕШЕНИЕ
№ цепочки (i)
1
2
3
4
5
6
7

Длина цепочки
d=2i-1
1
3
7
15
31
63
127

Структура цепочки
(1)
(1) (1) 2
(2) (2) 3
(3) (3) 4
(4) (4) 5
(5) (5) 6
(6) (6) 7

Конец цепочки
1
12
123
1234
12345
123456
1234567

Номер позиции
120
121
122
123
124
125
126
127

Цифра
1
1
2
3
4
5
6
7



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

РЕШЕНИЕ

№ цепочки (i)
1
2
3
4
5
6
7
8

Длина цепочки
d=2i-1
1
3
7
15
31
63
127
255

Структура цепочки
(1)
2 (1) (1)
3 (2) (2)
4 (3) (3)
5 (4) (4)
6 (5) (5)
7 (6) (6)
8 (7) (7)

Начало цепочки
A
BA
CBA
DCBA
EDCBA
FEDCBA
GFEDCBA
HGFEDCBA

Номер позиции 8 строки






(6)
2-128
(6) 129-255
1

Буква








H

Номер позиции
126
127
128
129
130
131
132



Буква
B
A
A
G
F
E
D





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

РЕШЕНИЕ

№ цепочки (i)
1
2
3
4
5
6
7

Длина цепочки
d=2i-1
1
3
7
15
31
63
127

Структура цепочки
(1)
(1) (1) B
(2) (2) C
(3) (3) D
(4) (4) E
(5) (5) F
(6) (6) G

Конец цепочки
A
AB
ABC
ABCD
ABCDE
ABCDEF
ABCDEFG

Номер позиции 7 строки





(6)
1-63
(6) 64-126
127

Буква







G

Номер позиции 6 строки




(5) 1-31
(5) 32-125
126


Буква






F


Номер позиции
117
118
119
120
121
122
123
124
125

Буква
A
A
B
A
A
B
C
D
E


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

РЕШЕНИЕ n=8, следовательно, искомый номер позиции 28-1-5=128-5=123, следовательно, 7-ая строка
№ цепочки (i)
1
2
3
4
5
6
7

Длина цепочки
d=2i-1
1
3
7
15
31
63
127

Структура цепочки
(1)
(1) (1) B
(2) (2) C
(3) (3) D
(4) (4) E
(5) (5) F
(6) (6) G

Конец цепочки
A
AB
ABC
ABCD
ABCDE
ABCDEF
ABCDEFG

Номер позиции 7 строки





(6)
1-63
(6) 64-126
127

Буква







G

Номер позиции




123
124
125
126

Буква




C
D
E
F

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

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

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

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

РЕШЕНИЕ
Научимся “расплетать” предполагаемую цепочку по шагам, чтобы найти в ней нужное. Сначала посмотрим еще раз на принцип формирования цепочек. Первая по счету (и нулевая по порядковому номеру) цепочка имеет длину 1. Далее на каждом очередном шаге длина цепочки удваивается, а затем увеличивается еще на 1 (приписыванием в конце очередной цифры номера данной цепочки):

№ цепочки (i)
0
1
2
3
4
5
6

Длина цепочки
1
3
7
15
31
63
127


Отсюда нетрудно вывести формулу определения длины цепочки по ее номеру i: <длина цепочки> = 2i + 1 – 1 (Кстати, нетрудно понять, что если цепочки нумеровались бы не с нуля, а с единицы, при соблюдении всех прочих условий, то в данной формуле в показателе степени для двойки прибавлять единицу было бы не нужно.) Таким образом, искомая цифра (на 123-м месте) отстоит от конца итоговой цепочки на 4 позиции левее. Вспомнив, что на каждом шаге к удваиваемой цепочке каждый раз дописывалась одна цифра, равная порядковому номеру очередной цепочки, нетрудно сообразить, что итоговая цепочка будет завершаться цифрами: 0123456, где “шестерка” стоит на последнем, 127-м, месте. И, отсчитав 4 позиции влево, получить, что на 123-м месте находится цифра 2.

№ позиции
121
122
123
124
125
126
127

Цифра
0
1
2
3
4
5
6


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

№ цепочки (i)
0
1
2
3
4
5
6

Конечная позиция цепочки
1
3
7
15
31
63
127

Окончание подцепочки
0
01
012
0123
01234
012345
0123456


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

№ цепочки
Цепочка
Длина цепочки

1
A
1

2
AAB
3

3
AABAABC
7

4
AABAABC AABAABCD
15


Впрочем, разобравшись уже с предыдущей задачей, мы можем сразу сказать, что искомая формула будет такой: <длина цепочки> = 2i – 1 (Напомним: прибавление единицы в показателе степени двойки здесь не требуется, так как нумерация цепочек производится не с нуля, а с единицы.) Тогда, очевидно, длина итоговой, 7-й, цепочки будет равна 27 – 1 = 127 символам. А вот сейчас начинается самое интересное. Теперь мы должны научиться “расплетать” цепочку по шагам назад. Итак
1. Согласно правилам, указанным в условии задачи, итоговая, 7-я, цепочка имеет формат: (6) (6) G
При этом согласно выведенной нами формуле 6-я цепочка имеет длину 26 – 1 = 63 символа. Тогда в нашу табличку, обозначающую формат рассматриваемой строки-цепочки, можно добавить обозначения соответствующих номеров позиций символов (При этом нужно не забывать, что отсчет номеров позиций (как и отсчет дней по календарю) ведется по следующим правилам: если предыдущая подцепочка начинается с символа с порядковым номером n и имеет длину d, то номер символа, которым заканчивается эта подцепочка, вычисляется по формуле (n + d – 1), а следующая подцепочка будет начинаться с символа под номером (n + d).):
(6)
(6)
G

1–63
64–126
127

2. Очевидно, что искомые нами символы располагаются во второй по счету подстроке (6). Продолжим “расплетание” цепочек еще на один шаг назад, “раскрывая” эту вторую цепочку (6) и оставляя неизменными остальные части таблицы. При этом учитываем, что длина предыдущей, 5-й, цепочки равна 25 – 1 = 31 символу.
(6)
(6)
G

1–63
64–126
127

(6)
(5)
(5)
F
G

1–63
64-94
95-125
126
127







3. Искомые символы находятся во второй “раскрытой” нами цепочке (5). “Расплетем” и ее, вычислив, что длина цепочки (4) равна 24 – 1 = 15 символам.
(6)
(6)
G

1–63
64–126
127




(6)
(5)
(5)
F
G

1–63
64-94
95-125
126
127


(6)
(5)
(4)
(4)
E
F
G

1–63
64-94
95-109
110-124
125
126
127




4. Увидев, что искомые символы находятся во второй “раскрытой” нами цепочке (4), “расплетем” и ее (вычислив, что длина цепочки (3) равна 23 – 1 = 7 символам):
(6)
(6)
G

1–63
64–126
127

(6)
(5)
(5)
F
G

1–63
64-94
95-125
126
127

(6)
(5)
(4)
(4)
E
F
G

1–63
64-94
95-109
110-124
125
126
127

(6)
(5)
(4)
(3)
(3)
D
E
F
G

1–63
64-94
95-109
110-116
117-123
124
125
126
127











5. В данном случае нам “повезло”: все нужные символы находятся в одной подцепочке (вторая (3)). А ее уже совсем нетрудно выписать полностью, “подсмотрев” ее в условии задачи: ААВААВС.

A
A
B
A
A
B
C

117
118
119
120
121
122
123


И тут уже совершенно очевидно, что искомые символы, записанные на позициях 117–122, это AABAAB. (Ну а если бы нам не повезло и искомые символы оказались бы распределены между несколькими подцепочками, то нетрудно было бы или “расплести” эти подцепочки, или сразу их выписать и найти искомое.)
Третье типовое решение.
А теперь рассмотрим две “модифицированные” задачи, в которых требуется подсчитывать количество единиц либо количество четных цифр. Самый простой способ такого подсчета попытаться вывести общую формулу, аналогично тому, как мы ранее определяли формулу для вычисления длины цепочек.

Задача 2007 B6
№ цепочки
Цепочка
Кол-во_четных цифр

1
1
0

2
112
1

3
1121123
2

4
112112311211234
5

5

10


Формула (рекуррентная):
Ni = Ni–1 * 2 + ((i – 1) mod 2), N1 = 0.

Задача 2008 B6
№ цепочки
Цепочка
Кол-во_единиц

1
1
1

2
211
2

3
3211211
4

4
432112113211211
8

Формула:
2i – 1, где i номер цепочки.

(В обоих случаях формулы действительны до цепочки с номером 9 включительно; далее же надо учитывать, что в начале на каждом шаге должны дописываться двухзначные числа 10, 11, 12, , потом трехзначные и т.д., но в задачах ЕГЭ пока до таких номеров строк составители заданий не доходили.)

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

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

Цифра_1
1
2
4
8
16
32
64
127

Возможна также модификация данной задачи, в которой нумерация цепочек и их построение начинается не с единицы, а с нуля:
(0) 0 (1) 001 (2) 0010012 (3) 001001200100123 и т.д.
Пусть, например, в этом случае надо подсчитать суммарное количество единиц в цепочке с номером 9. Очевидно, в этом случае наша таблица будет иметь такой вид:
№_цепочки
0
1
2
3
4
5
6
7
8
9

Цифра_1
-
1
2
4
8
16
32
64
128
256

В этом случае надо учесть, что в самой первой цепочке (с номером 0) единичек нет вообще, впервые единица появляется в цепочке с номером 1, а далее в таблице записывается все та же “волшебная” последовательность чисел, хорошо известная каждому старшекласснику, последовательность степеней двойки.
Ответ: 256.

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


1
2
3
4
5
6
7
8

2
-
1
2
4
8
16
32
64

4
-
-
-
1
2
4
8
16

6
-
-
-
-
-
1
2
4

8
-
-
-
-
-
-
-
1

Всего_четных_ цифр
85


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


1
2
3
4
5
6
7
8
9
10

1
1
2
4
8
16
32
64
128
256
512+1

3
-
-
1
2
4
8
16
32
64
128

5
-
-
-
-
1
2
4
8
16
32

7
-
-
-
-
-
-
1
2
4
8

9
-
-
-
-
-
-
-
-
1
2

Всего_нечетных_ цифр
683

Ответ: 683.
Единственное, на что нужно обязательно обратить внимание (и на чем “споткнулись” многие учащиеся, решая эту задачу), на то, что в 10-й строке, кроме единиц, накапливаемых за счет удвоения предыдущей подцепочки, вначале дописывается новое число 10, которое тоже содержит единицу. Поэтому-то в последнем столбце в строке, соответствующей цифре 1, к очередной степени двойки (512) прибавляется 1. А затем, как и в предыдущей задаче, нужно подсчитать сумму чисел для всех строк последнего столбца.








13 PAGE \* MERGEFORMAT 14215




15

Приложенные файлы

  • doc 19061567
    Размер файла: 198 kB Загрузок: 0

Добавить комментарий