4 Math 6 Man Out [PDF]

Zitiervorschau

Н. А. Сопру­но­ва | М. А. Посицельская С. Е. Посицельский | Т. А. Рудченко Т. В. Михайлова

математика и информатика

4 класс

учебник | в шести частях | шестая часть

Москва | 2019 | ЦПМ, МЦНМО

1

2

УДК 373.167.1:51 ББК 22.1я71 Сопрунова Н. А. С 64 Математика и информатика. 4-й класс. Учебно-методическое издание. В 6 ч. Ч. 6 / Н. А. Сопрунова, М. А. По­си­цельская, С. Е. Посицельский, Т. А. Рудченко, Т. В. Михайлова. — М.: ЦПМ, МЦНМО, 2019. — 48 с.: ил. ISBN 978-5-4439-2870-8 (МЦНМО) ISBN 978-5-906085-66-5 (ИНТ) Курс «Математика и информатика» рассчитан на обучение в течение четырёх лет в объёме четырёх или пяти уроков в неделю. Предусмотрены различные варианты работы — как с использованием средств ИКТ, так и без них. В комплект для четвёртого класса входят учебник в шести частях и задачник в шести частях.

Дизайн книги — И. Э. Бернштейн, вёрстка — Д. А. Кобринский Иллюстрации — Е. В. Гаврилова  вторы благодарят: А за ценные замечания — С. Ф. Сопрунова; за помощь в подготовке издания к печати — Е. А. Акулину.



1

© Центр педагогического мастерства, 2019 © Московский центр непрерывного математического образования, 2019 © Институт новых технологий, 2019 © Н. А. Сопрунова, М. А. Посицельская, С. Е. Посицельский, Т. А. Рудченко, Т. В. Михайлова, 2019 © Е. В. Гаврилова, иллюстрации, 2019 © И. Э. Бернштейн, оформление, 2019 Все права защищены.

2

3

Цепочки Это цепочки.

У каждой цепочки есть начало и конец: начало цепочки

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

конец цепочки Порядок бусин в цепочке: первая бусина

следующая за жёлтой

последняя бусина

предыдущая перед жёлтой

2

3

4

Одинаковые цепочки Вот цепочка Ю:  Ю  В цепочке Ю первая бусина — жёлтая круглая, вторая — красная круглая, третья — зелёная квадратная. Вот такая же цепочка: Вот ещё такая же цепочка: У неё тоже первая бусина — жёлтая круглая, вторая — красная круглая, третья — зелёная квадратная. Эти две цепочки — одинаковые:     Эти две цепочки тоже одинаковые:

1

4

3

6



И эти две цепочки одинаковые:

Все пустые цепочки — одинаковые.

3

4

5

1

4

3

6

Для того чтобы узнать, одинаковы ли цепочки, нужно сравнить бусины, начиная с первой.

одинаковые одинаковые одинаковые одинаковые одинаковые одинаковые одинаковые Эти цепочки одинаковые.

Разные цепочки Первые три бусины в цепочке Б такие же, как в цепочке А. Но  четвёртые бусины в этих цепочках — разные. А

одинаковые



одинаковые



Б





одинаковые





разные





Цепочки А и Б — разные.

4

5

6

В цепочке У — три бусины, а в цепочке Ф — четыре. Цепочки У и Ф тоже разные.     У

        Ф

И эти две цепочки — разные:

к и л о г р а м м к и л о м е т р Эти две цепочки — разные: Эти две цепочки тоже разные: И эти две цепочки — разные:

1 2 3

1 2 3 4



Это тоже разные цепочки:

с т у к



к у с т

Здесь не все цепочки разные. Найди две одинаковые цепочки.

Ё Ж

5

6

7

З

И

Дерево перебора Используя только красный, жёлтый и  зелёный цвета, раскрась все бусины в цепочках так, чтобы все цепочки были разными и были истинны утверждения: После каждой красной бусины идёт либо красная бусина, либо конец  цепочки. После каждой жёлтой бусины идёт либо жёлтая бусина, либо красная  бусина, либо конец цепочки.

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

1

Сколько  цветов использовано в  цепочке?

3

2

6

7

8

Ариша подумала: «Если использовать только один цвет, то каким он  может быть?» Цепочка, в которой все бусины раскрашены одним из  цветов — красным, жёлтым или зелёным, подходит к условию задачи. Ариша написала вопрос и нарисовала три цепочки.

1 Какой цвет?

Сколько  цветов использовано в  цепочке?

3

2

«Если использовано два цвета, то какого цвета нет?» — подумала Ариша и вписала третий вопрос.

1 Какой цвет?

Сколько  цветов использовано в  цепочке?

2 Какого цвета  нет?

7

8

9

3

«Если жёлтого цвета нет, то сколько зелёных можно поставить? Все  четыре бусины раскрашивать зелёным цветом нельзя — нужно использовать ровно два цвета. Значит, зелёных может быть либо одна, либо две, либо три, а  остальные — красные».

1 Какой цвет?

Сколько  цветов использовано в  цепочке?

3

2 Какого цвета  нет?

Сколько зелёных? 1

3 2

8

9

10

«Зелёные бусины могут быть только в начале. Ведь если красная бусина появится на каком-нибудь месте, то после неё могут идти только красные».

1 Какой цвет?

Сколько  цветов использовано в  цепочке?

2 Какого цвета  нет?

Сколько зелёных? 1

3 2

9

10

11

3

«Если в цепочке нет красных бусин, зелёных опять может быть одна, две или три. И снова они идут подряд от начала цепочки».

1

Сколько  цветов использовано в  цепочке?

Какой цвет?

3

2 Какого цвета  нет?

Сколько зелёных? Сколько зелёных? 1

1

3 2

3 2

10

11

12

«Если же в цепочке отсутствует зелёный цвет, значит, есть жёлтый и  красный. После красной бусины могут стоять только красные. Значит,  жёлтые бусины тоже могут стоять только подряд от начала цепочки».

1

Сколько  цветов использовано в  цепочке?

Какой цвет?

3

2 Какого цвета  нет?

Сколько зелёных? Сколько зелёных? 1

3 2

11

12

13

1

Сколько жёлтых?

3 2 1

3 2

«Остаётся случай, когда нужно использовать все три цвета. Сколько  в  такой цепочке может быть зелёных бусин? Не больше двух, иначе не  останется места для остальных цветов. Значит,  одна или две».

1

Сколько  цветов использовано в  цепочке?

Какой цвет?

3 Сколько зелёных?

2

1

Какого цвета  нет?

2

Сколько зелёных? Сколько зелёных? 1

3 2

1

Сколько жёлтых?

3 2 1

3 2

12

13

14

«Если зелёная бусина только одна, сколько в цепочке жёлтых бусин? Тоже не больше двух. Место для зелёных есть только в начале, поскольку после жёлтых могут быть только жёлтые или красные, а  после красных вообще только красные».

1

Сколько  цветов использовано в  цепочке?

Какой цвет?

3 Сколько зелёных?

2

1

Какого цвета  нет?

2

Сколько жёлтых?

1

Сколько зелёных? Сколько зелёных? 1

3 2

13

14

15

1

Сколько жёлтых?

3 2 1

3 2

2

«А если зелёных две, то жёлтых и красных по одной. Причём жёлтая раньше, иначе ей уже не попасть в цепочку».

1

Сколько  цветов использовано в  цепочке?

Какой цвет?

3 Сколько зелёных?

2

1

Какого цвета  нет?

2

Сколько жёлтых?

1

Сколько зелёных? Сколько зелёных? 1

3 2

1

2

Сколько жёлтых?

3 2 1

3 2

У Ариши получилось дерево перебора: в развилках стоят вопросы, на  ветках написаны ответы на вопросы, листья — это объекты, которые мы перебираем. Обрати внимание: у этого дерева есть развилки, из  которых выходит больше двух веток. Значит, это дерево не  двоичное!

14

15

16

Тимоша тоже сообразил, что в цепочке сначала идут все зелёные бусины (если они есть), потом все жёлтые, а потом все красные. При  переборе он задавал себе другие вопросы, и у него получилось другое дерево перебора. Сколько красных? 0

4 1

2

3

Сколько зелёных? Сколько зелёных?

4

0 1

2

3

0

Сколько зелёных?

0

3 1

15

16

17

Сколько зелёных?

2

0

1

2

1

Вот как выглядит дерево перебора:

вопрос

ответ

ответ

от в

ет

ет отв

отв ет

вопрос от в

ет

в от

вопрос

ответ

ет

вариант

вариант вариант

вариант вопрос от в

т ве

ет

ответ

от

вариант

от в

ет

ответ

вопрос

вариант

вариант вопрос от в

ет

вариант

ет

ответ

в от

вариант

вариант

Для того чтобы с помощью дерева перебора не упустить ни одного варианта, нужно, чтобы в каждой развилке стоял вопрос, а на каждой ветке — ответ на вопрос.

16

17

18

Общий делитель двух чисел Мы хотим найти такие числа, на которые делятся и число 120, и число 96, то есть их общие делители.

·

Разложим число 120 на простые множители и выпишем все его делители. Это 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120.

5  3 120 =  2 2 2

Разложим число 96 на простые множители и выпишем все его делители. Это 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 96.

2 3 2 96 =  2 2 2

·

1, 2, 3, 4, 6, 8, 12, 24 — общие делители чисел 120 и 96. 24 — наибольший общий делитель чисел 120 и 96. Мешок его разложения — это общая часть мешков разложения чисел 120 и 96.

24 = 

·

 3 2 2 2

Сокращённое обозначение: НОД (120; 96) = 24 Найдём наибольший общий делитель чисел, если одно из них делится на другое. Например, 72 и 9. Поскольку 72 делится на 9, то все делители девяти, включая его самого, являются их общими делителями, а наибольший среди них — 9. НОД (72; 9) = 9

17

18

19

Взаимно простые числа Числа, у которых нет общих делителей, кроме единицы, называются взаимно простыми. Например, числа 29 и 31 — взаимно простые, потому что оба они делятся только на 1 и на само себя. НОД (29; 31) = 1 Найдём наибольший общий делитель чисел 15 и 26. 15 делится только на 1, 3, 5 и 15. 26 делится только на 1, 2, 13 и 26. Общих делителей, кроме 1, у чисел 15 и 26 нет. Значит, НОД (15; 26) = 1 Числа 15 и 26 взаимно просты, хотя ни одно из них не является простым. Чему может быть равен наибольший общий делитель соседних чисел? Между чётными числами не меньше двух шагов, значит, оба соседних числа не могут делиться на 2. Между числами, делящимися на 3, не меньше трёх шагов, значит,  оба  соседних числа не могут делиться на 3. Между числами, делящимися на 5, не меньше пяти шагов, значит,  оба  соседних числа не могут делиться на 5. И так далее. Соседние числа всегда взаимно просты. НОД (20; 21) = 1  НОД (48; 49) = 1  НОД (189 765 827; 189 765 828) = 1

18

19

20

Разность и общий делитель Чтобы найти общие делители двух чисел, не обязательно раскладывать числа на простые множители и выписывать все делители одного и  другого. Для поиска наибольшего общего делителя нам пригодится такое истинное утверждение: Если два числа делятся на одно и то же число, то и их сумма и  разность тоже будут делиться на это число. Возьмём, к примеру, два числа, делящихся на 7. Если число делится на 7, его можно представить в виде суммы нескольких семёрок. Если к сумме семёрок прибавить ещё несколько семёрок, снова получится сумма семёрок. Например, 98 = 7 · 14 = 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7  77 = 7 · 11 = 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 98 + 77 = 7 · 14 + 7 · 11 = 7 · 25 При вычитании из одной суммы семёрок другой суммы семёрок снова получится сумма семёрок. Например, 98 = 14 · 7 = (7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7) + (7 + 7 + 7)  77 = 11 · 7 =  7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 98 − 77 = 7 · 14 − 7 · 11 = 7 · 3 = 7 + 7 + 7 Точно так же, как про семёрки, можно рассуждать и про любое другое  число. Пользуясь этим утверждением, можно искать наибольший общий делитель больших чисел, не раскладывая каждое из них на простые множители и не выписывая все делители.

19

20

21

Например, нам нужно найти НОД (120; 96). Заменим большее из этих чисел на их разность. 120 − 96 = 24 Вместо того чтобы искать наибольший общий делитель чисел 120 и 96, найдём НОД (96; 24). Это  будет то же самое число в силу утверждения на предыдущей странице. И это гораздо удобнее, поскольку 24 — небольшое число, то есть его делители можно перебрать даже в уме. Нетрудно заметить, что 96 делится на 24. НОД (96; 24) = 24 А значит, и НОД (120; 96) тоже равен 24. Найдём теперь НОД (108; 84). Заменим 108 на разность этих чисел. 108 − 84 = 24 Будем искать НОД (84; 24). 84, в отличие от 96, уже не делится на 24. Будем перебирать делители числа 24 и проверять, делится ли 84 на них. Следующий по величине делитель — 12. 84  12 Нам повезло, не  пришлось долго перебирать. НОД (108; 24) = НОД (84; 24) = 12 Найдём теперь НОД (106; 82). Разность этих чисел тоже равна 24. Будем искать НОД (82; 24). Само число 24 не подходит, поскольку 82 / 24. Следующий делитель числа 24 — это 12. Но 82 / 12. Перебирая дальше делители числа 24, убеждаемся, что НОД (82; 24) = 2. А значит, НОД (106; 82) = 2. Возьмём ещё пару чисел с разностью 24. Например, 109 и 85. Найдём их наибольший общий делитель. Заменим 109 на 24 и будем искать НОД (85; 24). Число 85 нечётное, значит, единственный делитель числа 24, который нам нужно проверить, это число 3. Но 85 / 3. Итак, НОД (85; 24) = 1. Значит, и НОД (109; 85) = 1.

20

21

22

Мешок Это мешки.

В мешок можно положить всё что хочешь — монеты, игрушки, бусины. Это пустые мешки. В них ничего не лежит.

Вот кошелёк. В нём 10 рублей.

Сумма мешка этих чисел равна десяти. 1 2

+

2 5

22

1 2

 = 1 + 2 + 2 + 5 = 10

Сумма пустого мешка равна нулю.

21

Произведение мешка таких чисел равно 20.

23

+

 = 0

2 5

·

 = 1 · 2 · 2 · 5 = 20

Произведение пустого мешка равно 1.

·

 = 1

Одинаковые мешки. Разные мешки М1 В мешке М1 две красные треугольные бусины и одна жёлтая круглая. В мешке М2 тоже две красные треугольные бусины и одна жёлтая круглая. Это одинаковые мешки.

М2

В мешке Т1 есть синяя треугольная бусина, а в мешке Т2 — нет. Это разные мешки.

T2

В мешке А1 две бусины, а в мешке А2 — три. Эти мешки — разные.

A1

В каждом из мешков К1 и К2 K1 по 3 рубля. Но эти мешки — разные: в мешке К1 есть монета в 2 рубля, а в мешке К2 — нет.

T1

A2

K2

Все пустые мешки — одинаковые.

22

23

24

Сокращение произведений Решим задачу. Вставь число в окошко так, чтобы получилось верное равенство. 60 · 72 · 108 = 90 · 96 · 27 · 

60

·  = 

72 108

90

·

96 27

Если разделить оба произведения на одно и  то же число, равенство останется верным. Числа 60 и 90 делятся на 30. Разделим каждое из них на 30, а результаты запишем в  мешках. Мы сократили произведения на 30. 2 3 60 · 72 · 108 = 90 · 96 · 27 · 

60 2

 = 

72 108

Числа 72 и 96 делятся на 24. Сократим произведения на 24.

60 2 72 3

3 4 2 · 72 · 108 = 3 · 96 · 27 · 

108

Число 108 делится на 27. Сократим произведения на 27.

60 2 72 3

4 2 · 3 · 108 = 3 · 4 · 27 · 

·

108 4

90 3

·

96 27

·

90 3  =  96 4

·

27

·

90 3  =  96 4

·

27

Если при сокращении остаётся единица, её можно не писать в мешке. В левом мешке остались числа 2, 3 и 4. В правом мешке тоже есть числа 3 и 4. · · 60 2 Сократим оба произведения на 3 и на 4. 90 3  =  Тогда в левом мешке останется 2, 72 3 96 4 а  в  правом  — окошко. Впишем в него число 2. 2 108 4 27 2 · 3 · 4 = 3 · 4 ·  2

23

24

25

Циклы Л

Вот цикл Л из шести бусин. Другими словами, это цикл длины 6. В цикле нет ни первой, ни последней бусины. У каждой бусины есть предыдущая бусина. У каждой бусины есть следующая бусина.

Цепочки устроены по-другому: у первой бусины нет предыдущей, у  последней бусины нет следующей.

Циклы и цепочки По любой цепочке можно построить цикл. Для этого нужно просто склеить начало и конец цепочки.

понедельник

воскресенье



понедельник

вторник

воскресенье

вторник

суббота



среда

суббота



среда

пятница



четверг

пятница



четверг

24

25

26

Цикл можно разрезать между любыми двумя соседними бусинами, получится цепочка. Направление при этом сохраняется. Ц

Ц1

Вот все цепочки, которые можно получить разрезанием цикла Ц: Ц1



Ц2

Ц3



Ц4

Одинаковые циклы Вот цикл: зима А осень





лето

Вот такой же цикл: лето Б весна



весна





зима

осень

Циклы А и Б — одинаковые. Цикл А получается склеиванием начала и конца цепочки ЦА. Цикл Б получается склеиванием начала и конца такой же цепочки ЦБ. зима лето ЦБ осень весна весна осень ЦА лето зима

25

26

27

Если циклы можно разрезать так, чтобы получились одинаковые цепочки, то эти циклы — одинаковые. Вот три одинаковых цикла: М1 Р А К И



М2 К И Р А



М3 И Р А К

Если разрезать цикл М1 между буквами И и Р, получится цепочка РАКИ.

Р А К И

Если разрезать цикл М2 между буквами И и Р, тоже получится цепочка РАКИ.

К И  

Если разрезать цикл М3 между буквами И и Р, снова получится цепочка РАКИ.

И  

Р А

Р А К

Эти два цикла — одинаковые.

    Каждый из этих циклов можно разрезать так, чтобы получилась такая цепочка:

Если склеить пустую цепочку, получится пустой цикл. Все пустые циклы — одинаковые.

26

27

28

Разные циклы Вот два разных цикла: Я1

Я2

В цикле Я1 — три яблока, а в цикле Я2 — четыре. Ф

У

Эти циклы тоже разные: В цикле У вторая бусина после квадратной — треугольная, а в цикле Ф вторая бусина после квадратной — круглая. Вот ещё два разных цикла:

Д 

И К Р А

Ж 



Р А К И

В цикле Д буква Р следует за буквой К, а в цикле Ж буква Р следует за буквой И. Эти циклы — разные.

К

Н

В первом цикле есть три фиолетовые бусины подряд, а во втором — нет.

Из двух разных циклов нельзя разрезанием сделать одинаковые цепочки.

27

28

29

Двоичное дерево Вот двоичное дерево:

лист ветка развилка

развилка

ветка корневая ветка

У дерева есть ветки, развилки и листья. Дерево начинается с корневой ветки. Каждая ветка, кроме корневой, начинается в развилке. Каждая ветка заканчивается следующей развилкой или листом. Из каждой развилки двоичного дерева растут ровно две новые ветки. (Именно поэтому такое дерево и называется двоичным.) Каждый лист растёт только на одной ветке. лист

развилка

ветка

ветка лист

ветка

развилка

лист развилка

корневая ветка

28

29

30

Вот ещё двоичные деревья:

Д1

Д2

Д3

Д4

У дерева Д1 есть только одна ветка — корневая — и один лист. Корневая ветка или заканчивается листом (как у дерева Д1), или приходит в развилку. У дерева Д2 три ветки, одна развилка и два листа — красный и зелёный.

Д5

29

30

Д6

31

Д7

В таблице показано, сколько веток, развилок и листьев у каждого из деревьев. Д1

Д2

Д3

Д4

Д5

Д6

Д7

веток

1

3

11

17

15

11

19

развилок

0

1

5

8

7

5

9

листьев

1

2

6

9

8

6

10

Обрати внимание: количество веток дерева равно сумме количества листьев и количества развилок. Как ты думаешь, почему так получается? Это не двоичные деревья.

   

   

У дерева с красными листьями из развилки вырастает не две ветки, а пять. У дерева с оранжевыми листьями две развилки, и из каждой вырастает по три ветки. У дерева с зелёными листьями есть развилка, из которой выходит три ветки.

30

31

32

Влево и вправо по двоичному дереву Жук полз по ветке. Он дополз до первой развилки и увидел два пути — влево и вправо.

влево вправо

Он пополз вправо (сокращённо п).

вправо влево

лл

На второй развилке он пополз влево (сокращённо л).

Путь к этому листу мы будем записывать так: вправо влево или сокращённо пл.

31

32

33

лп пп

пл

На этом рисунке возле каждого листа написан путь от корня дерева к этому листу. плпл плпп

л п п

плл л л лп

пп

лплп лплл

п п

п

л

п

л лл

л Д6

ллл

плп

лпп л

ллп

п

л

п л

пллп

пллл

л

п п л

п л

л

п

ппл л

п

п ппп

Д7

Чтобы из корня дерева Д6 попасть в красный лист, нужно пройти влево вправо Путь к красному листу сокращённо записывается так: лп Чтобы из корня дерева Д7 попасть в красный лист, нужно пройти вправо влево влево вправо Этот путь сокращённо записывается так: пллп А путь к фиолетовому листу записывается так: ллп Когда мы говорим о пути в дереве, мы всегда имеем в виду путь от корня к листу.

32

33

34

Мешок путей дерева п п

пп

Возле каждого листа п дерева Д мы написали путь к этому листу*. М — мешок путей дерева Д. У дерева Д шесть листьев. В мешке М шесть цепочек из букв и п.

ппп

п М

п п п пп ппп п

Д

Длиной пути к листу мы будем называть длину соответствующей цепочки из букв и п. В дереве Д один путь длины 1, один путь длины 2 и четыре пути длины 4. Обычно при выписывании пути мы не рисуем значки начала и конца цепочки. Но есть случай, когда без этих значков не обойтись, — пустая цепочка. В дереве Д0 один-единственный лист. В дереве Д0 нет развилок, поэтому путь к листу — это пустая цепочка букв. М0 — мешок путей дерева Д0. В мешке М0 только один путь — пустая цепочка. Длина этого пути равна нулю.

Д0

п Д1

М1 — мешок путей дерева Д1. В мешке М1 два пути длины 1.

М1 п п пп

М2 — мешок путей дерева Д2. В мешке М2 четыре пути длины 2. Других цепочек длины 2 из букв и п не бывает.

М0

Д2

М2

*  Иногда вместо слов «лист, к которому ведёт путь п» мы будем говорить «лист п».

33

34

35

Имена веток дерева Жук полз по дереву от корневой ветки к листу. На первой развилке жук повернул направо. Ветку, на которой оказался жук, назовём п.

п

Жук прополз ветку п и повернул налево. Ветку, на которой теперь оказался жук, назовём п .

п п

п п

В конце ветки п жук опять повернул налево. Ветку, на которую попал жук, назовём п . и попал на лист п . Жук прополз ветку п

Возле каждой ветки дерева Д мы написали её имя чёрным цветом. Возле каждого листа дерева Д мы написали его имя зелёным цветом. Если ветка заканчивается листом, то у этой ветки такое же имя, как у этого листа. Чтобы не возникало путаницы, имена листьев мы будем писать зелёным цветом, а имена веток дерева — чёрным цветом.

п п п

п

п п

п

п п

п

пп

п пп п

корневая Д

34

35

36

Добавление листа в дерево На любую ветку дерева можно добавить лист. Эти красные листы добавлены:

слева на корневую ветку

слева на ветку



слева на ветку п п

справа на ветку

справа на ветку п п

Эти красные листы добавлены:

справа на корневую ветку

35

36

37

Задание. Вот дерево Д. Ниже изображена его копия. Добавь к копии дерева Д левый лист на  ветку п и раскрась его красным. Получившееся дерево назови Д1. Заполни таблицу. лист

путь в  дереве Д

путь в  дереве Д1

Д

—

Результат: лист

Д

путь в  дереве Д

путь в  дереве Д1

пп

пп

п

п п

п п

п пп

—

п

Д1

36

37

38

Одинаковые деревья. Разные деревья Вот два дерева:

Д1

Д2

Эти два дерева — разные: у дерева Д1 есть лист, к которому ведёт путь , а у дерева Д2 нет такого листа. п п

М3

п

п п п пп

п

п п

пп

Д3

М4

п п п пп

пп

Д4

Вот ещё два дерева. Эти два дерева — одинаковые: у каждого из них четыре листа, к которым ведут пути , п , п п и пп. М3 — мешок путей дерева Д3. М4 — мешок путей дерева Д4. Мешки М3 и М4 — одинаковые.

37

38

39

Все эти деревья — одинаковые. Каждый следующий рисунок отличается от  предыдущего только тем, что мы немного повернули одну из веток.

38

39

40

Вот 5 одинаковых деревьев:

Вот ещё 5 одинаковых деревьев:

Здесь тоже все деревья одинаковые:

39

40

41

Чтобы найти одинаковые деревья, иногда красят листья при помощи таблицы.

Д5

Д6

Когда мы красили листья деревьев, оказалось, что у дерева Д7 нет листа п п — нечего красить голубым цветом. Поэтому деревья Д5 и Д7 — разные. А деревья Д5 и Д6 — одинаковые. У  них одинаковые мешки путей, ведущих к листьям: в левом столбце таблицы перечислены все пути к листьям дерева Д5, и такие же пути ведут к листьям дерева Д6.

Д7 путь к  листу

цвет листа красный

п

оранжевый

пп

жёлтый

п

зелёный

п п

голубой

п пп

синий

пп

фиолетовый

ппп

чёрный

40

41

42

Левая часть дерева, правая часть дерева Вот дерево Д. Если убрать корневую ветку и развилку в конце этой ветки, дерево Д распадётся на две части — левую часть дерева Д и правую часть дерева Д.

п

Д

Ветка дерева Д — корневая ветка его левой части. Ветка п дерева Д — корневая ветка его правой части. Для обозначения левой части дерева мы будем приписывать к имени дерева букву . Д — левая часть дерева Д. Аналогично для обозначения правой части дерева мы будем к имени дерева приписывать букву п. Дп — правая часть дерева Д.

41

42

43

Д

Дп

Не всегда просто увидеть, где в дереве левая часть, а где правая.

Здесь все листья левой части раскрашены синим цветом, все листья правой части — красным.

42

43

44

Вот деревья Д1, Д2 и Д3. Посмотрим, есть ли среди них одинаковые.

Д1 Д2

Д3

У этих трёх деревьев одинаковые левые части.

Д2

Д1

     

    Д3

Правые части тоже одинаковые.

Д3п

    

Д1п

Д2п    

Значит, деревья Д1, Д2 и Д3 — одинаковые.

43

44

45

Вот деревья Д11 и Д12.

Д11

  

Д12

Чтобы понять, одинаковы ли эти два дерева, сравним их левые части.

Д11      

Д12

Левые части — одинаковые. Теперь сравним правые части деревьев Д11 и Д12.

Д11п

Д12п     

Правые части — разные: в дереве Д11п справа 3 листа, а слева 1, а в дереве Д12п слева и справа по 2 листа. Значит, деревья Д11 и Д12 — разные.

44

45

46

Алфавитный указатель ветка дерева......................................... 29 взаимно простые числа.................. 19

мешок путей дерева........................ 34 наибольший общий делитель....... 18

двоичное дерево................................ 29 дерево перебора................................ 15 длина пути к листу........................... 34 длина цикла.......................................... 25

общие делители.................................. 18 одинаковые циклы............................ 26

имена веток дерева......................... 35 корневая ветка дерева................... 29 левая часть дерева........................... 42 лист дерева........................................... 29

45

46

47

правая часть дерева......................... 42 развилка дерева................................. 29 разные циклы...................................... 28 сокращение произведений............ 24 цепочки......................................................3 цикл........................................................... 25

Содержание Цепочки......................................................3 Одинаковые цепочки...........................4 Разные цепочки.....................................5 Дерево перебора.................................. 7 Общий делитель двух чисел........ 18 Взаимно простые числа ............... 19 Разность и общий делитель ....... 20 Мешок...................................................... 22 Одинаковые мешки. Разные мешки ............................. 23 Сокращение произведений........... 24

Одинаковые циклы............................ 26 Разные циклы...................................... 28 Двоичное дерево............................... 29 Влево и вправо по двоичному дереву................. 32 Мешок путей дерева........................ 34 Имена веток дерева......................... 35 Добавление листа в дерево......... 36 Одинаковые деревья. Разные деревья............................. 38 Левая часть дерева, правая часть дерева................... 42

Циклы....................................................... 25 Циклы и цепочки............................... 25

46

47

48

учебно-методическое издание Сопрунова Наталия Александровна Посицельская Мария Алексеевна Посицельский Семён Ефимович Рудченко Татьяна Александровна Михайлова Татьяна Владимировна Математика и информатика учебник 4-й класс В шести частях. Часть 6 В соответствии c Федеральным законом № 436 от 29 декабря 2010 издание маркируется знаком Дизайн книги — И. Э. Бернштейн Вёрстка — Д. А. Кобринский Художник — Е. В. Гаврилова Корректор — С. Б. Кобринская Подписано в печать 22.01.2019 Формат 84×108/16. Бумага офсетная Гарнитура PT Sans. Усл. печ. л. 5,04 Издательство МЦНМО 119002, Москва, Б. Власьевский пер., 11 Тел. (499) 241-08-04 Отпечатано в ООО «ТДДС-Столица-8» Тел.: (495) 363-48-86

47

48

6+