Смешно. Понятно, так здорово! Мне кажется, я ожил. Насколько давно я умер? Я столько всего рассказать успел. Да, всем привет! Короче, вот, ребята пришли, 50, 150. Я понял. Я короче рассказал, всё рассказал, подвёл к нужной точке, такой пам, и такой вот так вот. Вот такие пироги.

Значит, короче, всё рассказал, всё объяснил, всё уже прям дал, и такой удивляюсь, что вы в чат не пишете. Я такой: "Друзья, напишите в чат, если вы такие". Не пишите? Я такой: "Ну блин, а вас там тупо нет, вы в чате отсутствуете, и я просто не вижу". А 150 уверен. Да, была фраза, значит, ответ, конечно, так. Ладно, всё заново начинаем.

Чёрт, сейчас я заново всё расскажу. Но в этот раз я расскажу лучше, потому что я по сути вернулся в прошлое, правильно? Для того чтобы мне не понравилось, просто как я рассказал. Поэтому весь этот кусок, который вы сейчас, который я рассказал, вы его сейчас не видели, я его стёр, вырезал, вот так вот, и сейчас расскажу нормально.

Итак, значит, я даже не такую программу напишу, я напишу вот такую программу: Print ижи. И вопрос будет: сколько пар будет выведено на экране? Ответ, конечно, 50, а не 150. Там написали мне 50, ответ: нет, 150. Да, хорошо. Видите, такой ответ стоил вам аж нескольких каких-то этих, нескольких минут трансляции.

Значит, смотрите, сколько пар будет выведено. Вот такая задачка. Для того чтобы её решить, вам надо понимать, как работают вложенные циклы и как считать пары. Если у вас есть комбинация из двух множеств, то есть две вещи, сразу надо понимать, чтобы эту задачку решить. Причём вторая конкретно задача, её можно сформулировать вообще без проги. А вот задача про вложенные циклы формулируется строго с прогой. Как по-другому сформулировать задачу, да, чтобы получилось объяснить, что такое вложенные циклы?

И значит, смотрите, как вторую задачу сформулировать. У вас есть обезьянки. А можете писать что-нибудь в чат время от времени, чтобы я видел, что вы живы и чат живой, всё хорошо. То есть чтобы не было такого, что я очень много говорю, а вы в чате ничего не пишите. И тогда я хотя бы буду знать, что всё в порядке.

Вот, значит, есть обезьянки, и есть, значит, люди. И значит, встретилось пять обезьянок: 0, 1, 2, 3 и 4. Пять обезьянок встретилось, и встретилось 10 человек, то есть 0, 1, 2, 3 и так далее. И все обезьянки пожали руку всем людям. И тогда, сколько было рукопожатий? И сейчас задача совершенно не про вложенные циклы получилась. То есть задача в итоге получилась про типа математическая комбинаторная задача.

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

И из-за того, что ты вообще не можешь понять, что здесь надо делать, ты сидишь и тупишь. И может быть, ты тупишь над синтаксисом, может быть, ты тупишь над тем, что не понимаешь, как цикл вложить внутрь другого. Может быть, ты тупишь. Короче, существует столько разных штук, над которыми здесь можно тупить, и кажется, что чем больше из них ты смог пройти в отдельном упрощённом виде, тем лучше.

То есть как выглядит изучение вот этого вот вложенных циклов, когда ты не знаешь, как посчитать количество рёбер в двудольном графе, в котором ты знаешь объёмы каждой половинки. Вот это вот пять вершин, это 10 вершин. Сколько рукопожатий между пятью и десятью вершинами? Тебе надо сначала понять, что для каждого будут перебираться все возможные G, и ты такой про прогу думаешь: "Как так, возьмём тут, но и ра".

Ну, дальше G ра. Ну, но потом и ра. Ну, G ра 1 и ра. Ну, G ра 2. Так оно напишет, а видимо, оно напишет все числа. А потом такой: "Нет, не все, какие-то". Короче, тебе надо будет в процессе изучения вот этого дела понять вот это дело. А как выглядит изучение вот этого дела, если ты уже знаком вот с этой конструкцией? Я тебе дам сначала несколько таких разных задачек, а потом начну объяснять те вложенные циклы.

Кажется, что в таком случае ты увидишь во вложенных циклах быстрее знакомую тебе математическую задачку и поймёшь, что это на самом деле оно, и поймёшь, что это вот так работает. Ну, то есть давайте другую задачку вам дам, чтобы вы поняли, что это не тривиальная какая-то штука. И эту задачку уже кто-то решит, а кто-то, наверное, нет. Ну, сейчас посмотрим.

Вот, давайте я, например, напишу так: не знаю, 10, 4G от I П 1 до 10. И вот здесь я сделаю K п ра 1, здесь K ра. Ну и вот принт K. Что выведет данная программа, не запуская данную программу? Как вообще посчитать, что она выведет? Вот типа математик начнёт тыкать, как-то пробовать, что делает эта прога, потом догадается, что она делает. А то математически, что она делает, зная, как это работает, тот, кто не знает соответствующую математическую конструкцию, здесь даже если поймёт, что в итоге прога делает, затруднит правильно.

Сколько в итоге получится число K? Давайте вопрос к вам в чат, что вы видите, данная прога for 10 от П до 10, П ра 1. Мы с вами подошли к первой теме. Я сейчас буду очень подробно разворачивать на разных примерах. С вами заниматься, тий, но связанно с программированием. 11 факториал. 11 факториал знаете, сколько это? Дофига! 11 факториал - это 39 916 800. Я когда написал здесь И П 1 вместо нуля, я значительно уменьшил, значительно уменьшил количество операций во втором Клем. Обм выведет меньше, чем for Range 10, for Range 10, for Range 10, for Range 10. Э, программа выведет 100, а здесь она должна вывести что-то меньше 100, наверное.

Программист не работает. Стоит ли смотреть не программисту? Я думаю, да. Сегодня будет не очень много программирования, конкретно всё программирование будет довольно простое, но будет много прикольных математических конструкций, которые дальше вам позволят как-то понять что-то в программировании в будущем. Если вы когда-то хотели бы в жизни столкнуться с прогой, посмотреть, понять, как прога вообще, то, конечно, стоит посмотреть этот стрим.

А также два других стрима, которые у меня по ссылочке в описании есть. Канал в ВК, видео с остальными стримами или нет канала в ВК, видео, но есть чат в телеге по ссылочке в описании. А там в закрепе есть канал ВК, видео. В общем, ищущий, да, найдёт. Значит, ответ: да, 10 на 11 пополам только 10 ли? Ну да, нет. Нет, не 10 на 11 пополам, конечно. Не 55. Вот как раз пример, в котором не посчитали. Вот П 11. Откуда вы взяли, например, когда будет K плюс равно 11 сделано на каком из циклов вот этих типа при самом первом I равном нулю J?

Ну, вообще, с какого, как оно считается? Более того, сумма от одного до 11 - это не 11 у 10 пополам. Паскаль, смотрите, у вас несколько ошибок. Во-первых, сама сумма исходная не та, которая реально будет посчитана. Во-вторых, ответ в итоге, который вы посчитали, сумму вы неправильно её посчитали. Сумма от одного до оди на самом деле равна 66, а не 55. 55 - это сумма от одного до 10. Ну и так далее. 90 тоже неправильно.

И в итоге вот смотрите, какая прикольная штука. Да, я очень-очень недалеко отошёл от самых базовых элементов синтаксиса. То есть я просто вложенный цикл сделал, но в нём взял и какой-то элемент чуть-чуть поправил. У нас нарисовалась сложная математическая задача, на которую в чате ещё пока никто не дал правильный ответ. Просто ни один человек. Я подозреваю при этом, что вы уже сколько-то времени занимаетесь программированием и уже знакомы с какими-то конструкциями. И 50 тоже неправильный ответ. Смотрите, как прикольно. А казалось бы, да, точной наукой занимаемся, всё такое.

Ну, типа как эта штука себя вообще ведёт? Давайте сначала попробуем просто осознать, как она себя ведёт. Когда, в какой момент я прибавляю единичку? В момент, когда у меня одновременно сработало два цикла. Я зашёл Ирик по I, Ирик по J. И то есть я, допустим, давайте на нулевом шаге просто проделаем эту прогу. Да, I равно нулю. Сначала посмотрим. Теперь давайте попробуем, что дальше происходит. Появляется какой-то там J, который равен J, получается перебирает значение от I П 1 до 10, то есть 1, 2, 3, 4, 5, 6, 7, 8, 9.

И я получается, грубо говоря, представьте себе, что я здесь напишу вместо K п ра 1, я напишу вот такую вот конструкцию: Print и G. Тогда получается, что у меня при I равном нулю будут выведены следующие пары: 0, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8 и 0, 9. Потом, когда I будет равно 1, то есть ещё одна точка есть, я вывожу следующий набор пар: 1 и что там J уже бежит по циклу от 2 до 10, типа 1, 2, 1, 3, 1, 1, 1, 7, 1, 8, 1.

А здесь я напишу 2, 0, 2, 1. Я в общем выпишу все 100 вариантов: 2, 3, 2, 4, 25, 26, 27, 28, 29. В каждом столбце у меня первая цифра одинаковая, в каждой строчке у меня вторая цифра одинаковая. 3, 0. Ладно, я не буду на самом деле всё выписывать, но я хотя бы третий столбец допишу, чтобы было понятно, что я дальше буду делать. 38, 39. Когда я все-все-все выпишу и закончу вот так вот 90, 91 и так далее, 99, сколько я всего пар выписал получается?

Ну, если все-все-все я выпишу до конца, до упора, говорят, убираем повтор, делим пополам. Говорит, я чус, чтобы всели здесь посчитал 9х10 - это количество протянуты рук. То есть смотрите, что такое 90? Вот челик с номером ноль протянул руку, протянул руку девять раз. Челик с номером один, он тоже протянул руку девять раз, у него всего девять таких хвостиков. Челик с номером два тоже протянул руку девять раз. Челик с номером три протянул руку тоже только девять раз, у него девять хвостиков.

И у челика с номером четыре девять хвостиков, и у челика с номером пять. Или представьте себе, что эти все люди были на самом деле не людьми, а инопланетянами, и они все были девяти инопланетянами и взялись за руки одновременно, чтобы получился полный граф. Они все одновременно сцепились за руки, взяли друг друга вот так вот за руки, и каждый протянул девять своих рук своим товарищам. Тогда 0 - это ответ на какой вопрос? Девять рук у каждого из них, 10 товарищей. 90 - это что? Вот на этой картинке они все растопырят свои руки, чтобы сделать такое единое большое плотное рукопожатие.

90 - это количество рук, получается, протянуты в воздухе. Вот так вот каждый протянул девять рук к своим друзьям, и они начинают приближаться, чтобы схватиться этими руками. Что происходит, когда мы связываем двух людей, например, шестого и нулевого в рукопожатие? Мы тратим две руки и получаем рукопожатие. Вот здесь вот они связались, и у них рукопожатие произошло. Минус две руки, плюс одно рукопожатие. То есть количество рукопожатий в два раза меньше, чем количество рук. Поэтому 9 у 10 пополам - это количество рёбер в полном графе.

То есть нам нужно посчитать количество вершин, 10 штук, умножить на степень каждой вершины, девять, и делим пополам, чтобы учесть вот эти повторы. Давайте мы здесь поймём, что происходит. Если я во всей таблице всех возможных пар, тут, кстати, я спросил, сколько, а никто не ответил. Может, у меня опять трансляция упала? Нет, ладно, сам напишу в чат 100. Я у вас спросил, сколько будет всего написано вот здесь вот пар. Ответ 100. Что значит 100? Значит, 10 столбцов по 10 элементов в каждом столбце.

Но если я исключу в первом столбце 0-0, во втором столбце 1:1, в третьем столбце 2:2, то есть пары сам с собой, на этой картинке это соответствует вот такому дурацкому рукопожатию: ноль к нолику, один к единички. Я их исключил, эти рукопожатия, их нет. А да, вроде бы стрим не упал. Или это у вас стрим упал? У меня не упал, у меня работает, я прямо вижу. Нет, я прям сам вижу свой стрим через. Так что нет, вот всё, да, у меня нормально.

Если я уберу 0, 0, 2, 2, 3, 3, 9, то есть диагональные элементы, я оставлю вместо этого там дырки вот такие. То сколько я элементов убрал? Я убрал их по диагонали, получается, я выкинул 10 элементов. Таким образом, если я сделаю вот тут вот 100 пар и я выкинул только что 10 пар, получается, оставил я 90 пар. Вот эти вот 90, которые посчитаны с помощью 9 у 10 пополам, это все пары, но я не убрал повторы. Повторы - это что такое? Это вот смотрите, третий пожал руку первому, а чуть раньше первый уже жал руку третьему.

Они как бы два раза рукопожатие сделали. То есть первый подошёл к третьему и сказал: "Здорово, третий". А потом третий через 5 минут подошёл к первому и сказал: "Здорово, первый". А первый такой: "Ты что, мы уже здоровались, дурак что ли?" И вот тут получается, что все рукопожатия, которых больший, более старший, подошёл к более младшему, они уже повторные. Типа сначала все, кто младше, подошли ко всем, кто старше. Например, нулевой подошёл ко всем. Потом первый подошёл ко всем. Потом второй подошёл ко всем, кто старше него. Да, и тогда получается, что со всеми старшими уже поздоровались.

То есть второму не надо здороваться с нулевым, нулевой с ним уже поздоровался. Третьему не надо здороваться с первым, первый с ним уже поздоровался. И все эти старшие, они все находятся сверху от диагонали. Таким образом, 9, которые мы получили, реть ещё. Всё, что сверху от диагонали, это целая половина. У нас останется только вот такой вот нижний треугольник. То есть их в два раза меньше, потому что они ровно все один к одному. Вот это деление пополам.

То есть итоговый ответ 45. И я это показал несколькими разными способами на нескольких разных картинках. Теперь представьте, что вы это всё уже знали. Представьте, что я вам это уже рассказывал. А, ну, во-первых, да, поставьте плюсик в чат, если всё понятно, если это не было сложностей, проблем, если я достаточно нормально объяснил и всё такое. Бахте, пожалуйста, плюс в чат. Теперь представьте на секунду, что вы с этим уже знакомы были, потому что прошли это на каком-то уроке математики.

Это сейчас было не про программирование вообще. Мы с вами считали количество рёбер в полном графе на десяти вершинах. Это стандартная тема графы, полные графы. Математика - это прямо в олимпиадной математике встречается. Я вам говорю, за пятый-шестой класс олимпиадную математику пройдёте. Если вы всё это знали, представьте себе, потом вы встретили бы вложенный цикл вот такой. Не понятно, он делает, что он делает, что за вложенный цикл, как он работает. Вы как бы не знакомы с программированием, вы только начинаете, да, у вас синтаксис в голове появился.

Вы такие: "Для каждого I от нуля до десяти перебираем значение 0, 2, 3, 4 до десяти". Потом J перебирает значение большее I, то есть для I равного, например, 6 будет перебирание 7, 8. Даже вот это, получается, это полный граф. Всё, ответ 45. Вы бы знали ответ сразу. Мало того, вы бы не только знали ответ сразу, у вас бы в голове это структурировалось как конструкция, в которой много точек, и эти точки все друг с другом взаимосвязаны.

И вы бы вот на вложенный цикл потом стали смотреть совершенно по-другому. Вы его как только изучили, вот именно такой, где второй вложенный цикл перебирает индексы от I П 1 до конца, вы такие: "Прикольно, это перебор всех пар внутри какого-то множества без повторов". То есть, например, если бы вместо а там и ж, я бы здесь использовал какой-нибудь там массив, и в нём бы брал иты элемент и тый элемент какой-то список, да, то получается, что данный вложенный цикл позволяет перебрать все пары элементов из какого-то списка.

Типа у нас есть какой-то список, и мы перебираем все возможные пары элементов. Вот такая конструкция, прикольно получается. Мы можем с помощью математики лучше осмысливать какие-то программистские, ну, типа какие-то заранее, получается, знать какие-то темы, которые нам потом в проге помогают. Одна из таких тем - это графы. Вот мы, собственно, давайте к ней и перейдём. Слово графы. А кто слышал это слово до сегодняшнего дня и до моего стрима? Поставьте плюс.

Граф, я имею в виду, не граф Монтекристо, а граф - математическая конструкция, в которой точки, линии, вот эти вершины, рёбра. Можно поставить минус, если вы не слышали раньше слово граф. Все поставили плюс? Фига се, ладно. А значит, ну что такое граф? Это вершины и рёбра. Вот граф какой-то, вот не знаю, нарисовал вот такой граф. У каждой вершины есть степень, это количество исходящих рёбер. Здесь вот, например, четыре рёбра: 1, 2, 3, 4. Здесь одно, здесь два, здесь одно, здесь два - это степень вершины.

А вершинами могут быть, ну, любые объекты, а рёбрами могут быть любые взаимосвязи между этими объектами. Классические задачи с графами - это города и дороги. Вот у вас есть пять городов, и дороги их так связывают. Найдите какой-нибудь маршрут куда-нибудь, что-нибудь такое. А или, например, люди, и вот дружба между ними. Пять человек, и между ними вот эти дружат, вот эти дружат, а вот эти двое не дружат. Да, вот у этого четверо друзей, а у этого двое, у этого один, у этого два, у этого один. Сколько всего дружб? Ответ: 4 + 2 + 1 + 2 + 1 раз на 2.

Почему разделить на 2? Только что проходили. Потому что когда я сложил степени всех вершин, я посчитал количество протянуты рук. Смотрите, а прикол, видите, я прямо на ходу, прямо в речи перепрыгиваю концепции на концепцию, а разные способы представления одного и того же. Я буду говорить про дороги, а потом я вдруг внезапно перейду и буду говорить про друзей и про рукопожатие. И это нормально, математика так и работает. Ты типа видишь в одном и том же разное или наоборот, в разном видишь одно и тоже.

Вот тут и есть как раз самый главный математический скилл, который вам надо познать. Как граф записывается, например, внутри программы? Ну, вариант номер один. Да, если у нас все эти вершинки будут перенумерованы, список рёбер. То есть сказать, что есть ребро, а есть ребро B, есть ребро BD, BC и CE. Всё это как бы граф, я перечислил дружбы. Другой вариант представить граф - это матрица смежности. Что такое матрица смежности? Про матрицы чуть позже тоже поговорим.

Но в самом простом виде матрица вам надо знать, потому что это двумерные списки, по факту. Покажу. Матрица вообще - это какое-то очень сложное слово, но на самом деле матрица - это просто таблица такая. То есть это просто такой двумерный объект. Смотрите, список - это линейный объект, например, три, кошка, 7, 25. А матрица - это типа то же самое, только у вас объект не в одну линию, а в несколько линий. То есть это как можно вть как несколько списков, как типа P списков, каждый список размером P. Получилась матрица 5 на 5, в ней пять строк, пять столбцов. Каждая строка - это список, и у вас таких списков пять штук.

Вот и на пересечениях двух строки и столбца я буду ставить единичку, если между ними есть ребро. Например, A ребро существует, поэтому я поставлю вот здесь единичку. Ребро тоже существует, поэтому я поставлю здесь единичку. Ребро A не существовать не может, поэтому я поставлю здесь нолик. Его не может быть, тоже не может быть CC, тоже не может быть DD, тоже не может быть. А все остальные рёбра могут быть, но я отмечу только те, которые реально есть.

B, BD, BC, а также, соответственно, из вершины B приходит ребро из C, из D и из E. Дальше аналогично. Из вершины D мы уже нарисовали всё, и только ребро CE осталось. CE вот здесь, и EC тоже его отметим. У нас всего пять рёбер. Внимание, вопрос: сколько единичек, нулями? Ну, короче, чему равна сумма всех элементов в этой таблице? Не считайте пальцем количество единиц, просто ответьте как-то по-другому, по-хитрому. Подумайте, если у нас всего пять рёбер, раз, два, три, четыре, пять, то сколько единиц в этой таблице?

В этой матрице это называется матрица смежности, потому что две вершины графа, между которыми есть ребро, называются смежными. Ответ: 10. Да, потому что за каждое ребро я оставил две единички. Например, BC и CB. Видите, две единички за каждое ребро. Поэтому если R, P, то единиц должно быть 10, в два раза больше, они у нас относительно вот этой вот диагонали. Ну, продублированы. Как выглядит матрица смежности полного графа? В ней все единицы, кроме диагонали. Все единицы.

Это значит, что все рёбра проведены. Если я проведу ещё CD, например, то у меня на пересечении C и D появится единичка, на чени D и тоже появится единичка. Это матрица смежности графа. Граф может быть вам подан в виде матрицы смежности, а может в виде списка рёбер. Хорошая программистская задача - это уметь переделывать матрицу смежности в список рёбер и наоборот. Неплохо бы знать про графы разные вещи.

Вот мы сейчас представление графа разобрали. Что нужно знать? Первая вещь, которую надо знать про графы, это то, что в графах бывают пути. Путь в графе - это когда вы из одной вершины добираетесь до другой. Можете напрямую, а можете через кого-то. Например, из D в A существует путь. D, вот он, в этом графе существует путь от любой вершины до любой другой, где-то напрямую, где-то не напрямую.

Могут быть графы, в которых не существует маршрута от любой до любой, то есть некоторые вершины друг до друга не добираются никак, в принципе. А такой граф называется несвязанным. Я сейчас, например, нарисую A, B, C, D, E, F, G, H, там ABCD, G, H, I, J. Да, забыл, I, J, K. Вот и значит, такой граф будет вот такой граф. Он не связанный, потому что в этом графе невозможно добраться от вершины D до вершины K. Просто не существует маршрута. Это видно, потому что в этом графе можно как бы разнести в разные стороны.

То есть сказать, что это одна сторона, это другая сторона. Из одной стороны в другую сторону просто дороги отсутствуют. Такие графы называются несвязанными. Ещё раз: связанный граф - это тот, в котором от любой вершины можно добраться до любой другой с помощью какого-то пути. Вот из C, например, в J нельзя прийти, а из C в G можно прийти. C, E, да, по дорогам приехать.

Можно представить себе это как, допустим, узлы в интернете и маршрутизацию между ними, как пакетами, что можно обмениваться, установленные соединения. Там связаны несвязанные графы. Понятная тоже конструкция. Что у меня в одной локальной сети трафик ходит, в другой ходит, а между ними связи нет, потому что там одна из них не подключена к интернету, например. Вот, связанность графа. Следующая концепция в графе - это циклы. Цикл в графе - это когда у вас есть маршрут какой-то, который начинается в какой-то вершине и заканчивается в ней же, при этом содержит больше одной вершины.

То есть типа CC - это не цикл, а вот C, B, C - это цикл. Это путь, который позволяет из C добраться в C по другим вершинам. Здесь ещё есть цикл. Ижк, понятно, что такое связанность, что такое циклы. Вроде да, хорошо. Теперь давайте дадим определение: дерево - это связанный граф без циклов. Связанный граф без циклов. Кто слово дерево применительно к графам или к программированию может быть уже даже раньше слышал? Поставьте плюсик в чат.

Интересно, что вы поставили плюсик в чат по отношению к графам, а где вы слышали слово граф раньше? В школьной программе графы вообще-то обычно не проходят. Просто этого не существует. Это есть в олимпиадной математике, но отсутствует в обычной школьной математике. Вероятно, вы слышали слово граф, уже когда занимались программированием. Дерево тоже слышали. Интересно, дерево - это связанный граф без циклов.

Ну хорошо, это дерево или нет? Ну, просто тупой вопрос. Чисто так я нарисовал какой-то граф. Является ли он деревом? Нет, потому что в нём есть цикл. Хорошо, а вот это дерево или нет? То есть дерево не обязательно должно выглядеть как дерево, а в плане, как реальное настоящее дерево, типа как корень из него там что-то растёт и так далее и так далее. Главное, чтобы он так понималось.

Хорошо, о'кей. А это дерево? Новый граф какой-то нарисовал. Является ли этот граф деревом? Тоже нет, потому что граф не связанный. Правильно, он не связанный, потому что в нём есть две компоненты связанности, раздельно. Вот это сверху, да, вот это снизу. Что мы сейчас делаем? Мы с вами оперируем понятиями, которые могут для кого-то, но это дерево всё. Вот это дерево - связанный граф без циклов. Чем нам так интересны деревья? Тем, что очень много конструкций в реальной жизни - это деревья.

Это такие штуки, в которых невозможно пройти по циклу. Или есть такая вещь, как остовное дерево. Это значит, берём граф и выделяем внутри этого графа только те дороги, которые в итоге сделают его деревом. То есть убираем цикличность. Короче, дерево - это штука, часто встречающаяся. Например, давайте посмотрим на вот какое дерево. Берём родителя самого главного, это будет корень дерева. Я просто выбрал одну вершину и выделил её как главную.

Давайте представим, что у этой вершины есть два соседа, да, две смежные вершины. Этих соседей назовём детьми: левый ребёнок и правый ребёнок. У каждого из этих соседей тоже сделаем двух детей. То есть у них степень вершины три, потому что раз, два и наверх три. У этих тоже два ребёнка. Вот такие деревья - это прямо вообще особая большая любовь в программировании, потому что это бинарное дерево. Называется бинарное, потому что би. Да, у него у каждой вершины два ребёнка, два ребёнка, два ребёнка, два ребёнка.

Очень много конструкций, структур данных и так далее базируется вот на таких деревьях. Соответственно, было бы неплохо научиться как-то понимать, что такое деревья вообще и как они работают, что с ними там можно делать, что с ними нельзя делать. Вот эти вершины, которые в самом низу находятся, называются висячие вершины, потому что у них степень только один. Висячая вершина, вершина степени один. Да, давайте я её напишу. Или лист называется ещё лист.

Вот здесь, например, очень много листьев. Давайте так, это слой номер ноль, номер один, номер два, номер три и номер четыре. Сколько здесь листьев? Не считая пальцами, головой подумать. Сколько листьев в этом дереве? Вот такое бинарное дерево я нарисовал. На каждом шаге увеличивается количество элементов в два раза. Это типа была бактерия, разделилась на две, потом они такие потусуются. Через четыре итерации 2 в четвёртой, 16, а на предыдущем уровне восемь вершин. А на предыдущем уровне четыре, а тут две, тут одна.

Если я сделал бы дерево, в котором был бы, не знаю, по три ребёнка, по четыре ребёнка, но бинарные деревья - это прямо вообще суперчастая конструкция. Это у тебя и в куче используется, и алгоритм в бинарных деревьях поиска и так далее. Вообще дофига где. Вот поэтому просто быть знакомым хотя бы с этой конструкцией, да, видеть её хотя бы раз. Давайте мы ещё в этой конструкции пару вещей проделаем, например, с нумерацией интересные вещи.

Вот это для кучи потом полезно будет. Я сейчас перенумерую, номер 0, а потом буду нумеровать слева направо. Это будет 1, это будет 2, будет 3, это будет 4, это будет 5, это будет 6, это будет 7, это будет 8, это будет 9, это будет 10, это будет 11, это будет 12, это будет 13, это будет 14. Дальше 15, 16. Внимание, вопрос: последний вершина, какой номер будет иметь? Неожиданно вы думали, я нумеровать буду, а я не буду. Я у вас попросил последний номер сразу.

А какой будет последний номер? Сколько всего вершин в бинарном дереве в этом? Интересный вопрос. 32, Александра говорит. 30, говорит Камиль. Что, вы готовы подраться за свои ответы? Аленд и Камиль в углу ринга. Александра Куликова верит в правом углу ринга. Камиль Гарипов, они готовы защищать свой ответ от крови потом до победного конца. Кто выиграет в этой битве? Внимание, вопрос. Ну, выиграет, естественно, тот, кто прав. Поэтому мы сейчас узнаем, кто прав.

17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29. Последний номер оказался 30. А 32 было хорошей попыткой, но нет. 32 - это D в P. А всего на последнем слое 2 в четвёртой элементов. А казалось бы, что номер 32, но у нас нумерация с нуля. Так что с нуля до 32, это значило бы, что у нас во всём графе 33 вершины. Это, кстати, тоже важный принцип, но он совсем базовый, поэтому я ему очень мало времени уделил. Называется принцип плюс минус один.

Он постоянно повсюду встречается. Смотрите, 0, 1, 2 и так далее 100. Сколько чисел тут написано? Ответ: 101 число. То есть от нуля до 100 101 чисел, потому что ноль включается. Следующий вопрос: я сделал 1, 2, 3, 4, 5, 6, 7 распилов. Сколько кусочков получилось? Если вы не будете считать пальцем, ответ восемь. Странная штука: семь распилов, восемь кусков. Почему? Потому что 1, 2, 3, 4, 5, 6, 7, 8. Я знаю, что я сказал не считать пальцем, но каждый распил слева от себя имеет кусочек, и последний тоже слева имеет кусочек.

Сем распилов, значит, семь стрелочек, нам кусочков сейчас нарисована стрелочка, кроме одного последнего. Один лишний кусок имеет. Это принцип плюс минус один. Он постоянно повсюду встречается. Сколько чисел на отрезке от 66 до 100 целых чисел? То есть смотрите, я написал числа 66, 67, 68 и так далее 100. Ну, там давайте 99, 100. Посчитайте, сколько здесь чисел без пальцев.

Попробуйте, как ваша интуиция вам подсказывает, почитать. Да, при этом я хитрый жук, который задаёт сложные вопросы в плане, может быть, я вас пытаюсь подловить. Может быть, я вас пытаюсь подловить на неправильном ответе. Наоборот, вот смотрите, вы пишете 100 - 66 П 1. А вы же понимаете, что ваше вот это вот знание, что надо сделать плюс один в конце, знание, что надо сделать 35, это не ваше интуитивное знание. Это вы именно раньше где-то такое научились делать.

Вы такое видели, понимали и почерпнули математическую способность какую-то. То есть это типа хитрый математический трюк из какого-то там на самом деле достаточно базированный посыл в том, что таких маленьких трюков их очень много. И теперь представьте, что вы сталкиваетесь с задачей, в которой вам вот это уже надо бы как бы понимать, а вам надо как бы заново этому учиться. И вот тут вот получается прикол.

То есть люди, которые занимаются программированием с нуля без математической базы, какой бы то ни было вообще, они с такими вещами первый раз сталкиваются, но уже сразу на какой-то сложной задаче. То есть уже задача сама сложная, а в ней ещё есть вот этот маленький момент, который как бы их мозг просто не схватывает. Вот также и ваш мозг не схватывает какие-то маленькие моментики, потому что не знаком с огромным каким-то математическим пластом, который под этим под всем стоит.

Здесь 31 элемент в этом графе, 31 вершина. Уровень один элемент, на следующем уровне два элемента, на следующем уровне четыре элемента, на следующем уровне во, и на следующем уровне 16. Интересный факт: сумма степеней двойки, кстати, единичка - это тоже степень двойки. 2 в нулевой, 2 в первой, 2 в четвёртой и так далее. Если сложить до двойки, например, в сотой степени, то это будет 2 в 101 минус 1. Поставьте плюсик в чат, кто этот факт знает.

Если сложить все степени двойки от одного до двух в какой-то степени, получится двойка в следующей степени. Но минус один. Поставьте минус в чат, если вы этот факт не знаете. Я его сейчас покажу, расскажу красиво. Да, в математике одно в другое перетекает. Просто связь разных вещей друг с другом безумная, просто неадекватно. Минус, много минусов, один плюс от Николая. Хорошо, ну Николай, машина дикая, что я могу сказать.

1 + 2 + 4 + 8 + 16 + 32 + 64 + 128. Утверждается, что ответ будет 256. Докажем. Я знаете, что сделаю? Возьму розовый маркер и напишу вот здесь вот плюс один. Просто от балды написал. Сколько получится? 1 + 1 - это сколько? Два, правильно? Молодцы. 2 + 2 - это сколько? 4, молодцы. 4 + 4 - это сколько? 8. 8 + 8 - 16. Волшебство. Да, 16 + 16 - 32. 32 + 32 - 64. 64 + 64 - 128. 128 + 128 - 256. Получилось 256.

Но вот этот плюс один, я же его лишний дописал, поэтому тут надо минус один сделать. Вот прикольно, просто запомните, красивая конструкция, приятно её. Ну, то есть там степени двойки складываются в следующую степень двойки. Соответственно, если у меня много этажей, каждый из них - это степень двойки, то ответ общая сумма от одного до 16 - это 32 - 1. То есть 31 нумерация с нуля, значит, последний номер 30. Паскаль, вероятно, посчитал по-другому.

Он подумал: "Так, начинаем с пятнадцати, а на последнем этаже 16 элементов". Значит, 15 + 16 должно было быть 31, но он не забыл вычесть единичку и написал 30, потому что Паскаль поставил минус про количество элементов. Получается, в дереве во всём, что их там 31 вершина. Это, кстати, тоже важный принцип, но он совсем базовый, поэтому я ему очень мало времени уделил. Называется принцип плюс минус один.

Он тоже изучается прямо в маленьком детстве. Смотрите, 0, 1, 2 и так далее 100. Сколько чисел тут написано? Ответ: 101 число. То есть от нуля до 100 101 чисел, потому что ноль включается. Следующий вопрос: я сделал 1, 2, 3, 4, 5, 6, 7 распилов. Сколько кусочков получилось? Если вы не будете считать пальцем, ответ восемь. Странная штука: семь распилов, восемь кусков. Почему? Потому что 1, 2, 3, 4, 5, 6, 7, 8. Я знаю, что я сказал не считать пальцем, но каждый распил слева от себя имеет кусочек, и последний тоже слева имеет кусочек.

Get Our Mobile App

Математика, Которую Должен Знать Каждый Программист

Transcription