Значение выражения
<<  Порядок выполнения действий в выражениях Тема урока: Раскрытие скобок  >>
Цепочки
Цепочки
2004 — A24
2004 — A24
2006 — B6
2006 — B6
2009 — B8
2009 — B8
2011 — B8
2011 — B8
Как же решать подобные задачи
Как же решать подобные задачи
№ Позиции
№ Позиции
Такие же сравнительно простые рассуждения нетрудно проводить и в
Такие же сравнительно простые рассуждения нетрудно проводить и в
Однако бывают и задачи, где требуется искать символ (либо символы) в
Однако бывают и задачи, где требуется искать символ (либо символы) в
Впрочем, разобравшись уже с предыдущей задачей, мы можем сразу сказать
Впрочем, разобравшись уже с предыдущей задачей, мы можем сразу сказать
2. Очевидно, что искомые нами символы располагаются во второй по счету
2. Очевидно, что искомые нами символы располагаются во второй по счету
Формула (рекуррентная): Ni = Ni–1 * 2 + ((i – 1) mod 2), N1 = 0
Формула (рекуррентная): Ni = Ni–1 * 2 + ((i – 1) mod 2), N1 = 0
Однако вывод подобных формул представляет дополнительные затруднения
Однако вывод подобных формул представляет дополнительные затруднения
Возможна также модификация данной задачи, в которой нумерация цепочек
Возможна также модификация данной задачи, в которой нумерация цепочек
Цифра
Цифра
А в заключение рассмотрим еще одну задачу, которая, правда, не входит
А в заключение рассмотрим еще одну задачу, которая, правда, не входит

Презентация: «Цепочки». Автор: RestWs. Файл: «Цепочки.ppt». Размер zip-архива: 164 КБ.

Цепочки

содержание презентации «Цепочки.ppt»
СлайдТекст
1 Цепочки

Цепочки

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

По материалам Журнала № 4 / 2011 // ИНФОРМАТИКА

2 2004 — A24

2004 — A24

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

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

3 2006 — B6

2006 — B6

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

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

4 2009 — B8

2009 — B8

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

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

5 2011 — B8

2011 — B8

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

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

6 Как же решать подобные задачи

Как же решать подобные задачи

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

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

7 № Позиции

№ Позиции

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

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

№ Цепочки (i)

0

1

2

3

4

5

6

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

1

3

7

15

31

63

127

121

122

123

124

125

126

127

Цифра

0

1

2

3

4

5

6

8 Такие же сравнительно простые рассуждения нетрудно проводить и в

Такие же сравнительно простые рассуждения нетрудно проводить и в

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

№ Цепочки (i)

0

1

2

3

4

5

6

Конечная позиция цепочки

1

3

7

15

31

63

127

Окончание подцепочки

0

01

012

0123

01234

012345

0123456

9 Однако бывают и задачи, где требуется искать символ (либо символы) в

Однако бывают и задачи, где требуется искать символ (либо символы) в

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

10 Впрочем, разобравшись уже с предыдущей задачей, мы можем сразу сказать

Впрочем, разобравшись уже с предыдущей задачей, мы можем сразу сказать

что искомая формула будет такой: <длина цепочки> = 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

№ Цепочки

Цепочка

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

1

A

1

2

AAB

3

3

AABAABC

7

4

AABAABC AABAABCD

15

11 2. Очевидно, что искомые нами символы располагаются во второй по счету

2. Очевидно, что искомые нами символы располагаются во второй по счету

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

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

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

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

(6)

(6)

G

(6)

(5)

(5)

F

G

1–63

64–126

127

1–63

64-94

95-125

126

127

A

A

B

A

A

B

C

117

118

119

120

121

122

123

(6)

(6)

G

(6)

(5)

(5)

F

G

1–63

64–126

127

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

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

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

Третье типовое решение. А теперь рассмотрим две “модифицированные” задачи, в которых требуется подсчитывать количество единиц либо количество четных цифр. Самый простой способ такого подсчета — попытаться вывести общую формулу, аналогично тому, как мы ранее определяли формулу для вычисления длины цепочек.

Задача 2007 — B6

Задача 2008 — B6

№ Цепочки

Цепочка

Кол-во_четных цифр

1

1

0

2

112

1

3

1121123

2

4

112112311211234

5

5

10

№ Цепочки

Цепочка

Кол-во_единиц

1

1

1

2

211

2

3

3211211

4

4

432112113211211

8

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

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

13 Однако вывод подобных формул представляет дополнительные затруднения

Однако вывод подобных формул представляет дополнительные затруднения

для школьников. Поэтому для решения таких задач можно предложить более простой табличный метод, придуманный одним из авторов данной статьи. Хитрость здесь в том, что та или иная цифра 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

14 Возможна также модификация данной задачи, в которой нумерация цепочек

Возможна также модификация данной задачи, в которой нумерация цепочек

и их построение начинается не с единицы, а с нуля: (0) 0 (1) 001 (2) 0010012 (3) 001001200100123 и т.д. Пусть, например, в этом случае надо подсчитать суммарное количество единиц в цепочке с номером 9. Очевидно, в этом случае наша таблица будет иметь такой вид:

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

№_Цепочки

0

1

2

3

4

5

6

7

8

9

Цифра_1

-

1

2

4

8

16

32

64

128

256

15 Цифра

Цифра

Цифра

№_Цепочки

№_Цепочки

№_Цепочки

№_Цепочки

№_Цепочки

№_Цепочки

№_Цепочки

№_Цепочки

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

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

16 А в заключение рассмотрим еще одну задачу, которая, правда, не входит

А в заключение рассмотрим еще одну задачу, которая, правда, не входит

в демоварианты ЕГЭ (пока), но предлагалась московским школьникам во время пробного ЕГЭ и вызвала некоторые трудности. Цепочки символов (строки) создаются по следующему правилу. Первая строка состоит из одного символа — цифры 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

9

10

1

1

2

4

8

16

32

64

128

256

256

512+1

3

-

-

1

2

4

8

16

32

64

64

128

5

-

-

-

-

1

2

4

8

16

16

32

7

-

-

-

-

-

-

1

2

4

4

8

9

-

-

-

-

-

-

-

-

1

1

2

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

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

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

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

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

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

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

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

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

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

683

683

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

«Цепочки»
http://900igr.net/prezentacija/matematika/tsepochki-108401.html
cсылка на страницу

Значение выражения

17 презентаций о значении выражения
Урок

Математика

71 тема
Слайды