В этом видео мы рассмотрим еще один важный пример применения правила суммы — рекурсивные подсчеты. Давайте посмотрим на следующую задачу. Пусть у нас есть несколько точек, и они соединены стрелками, как нарисовано на картинке. Есть начальная точка s (называемая источником), и есть конечная точка t (называемая стоком). Сколько есть различных способов добраться из точки s в точку t по стрелкам? Есть несколько способов дойти из точки s в точку t. Например, мы можем сначала пойти наверх, потом вернуться в центр, потом пойти в точку t. Или мы можем пойти сначала вниз, потом продолжить движение внизу, потом попасть снова в точку t. Как посчитать все эти способы и быть уверенными, что мы ничего не пропустили? Оказывается, мы можем просто посчитать это рекурсивно: для всякой точки мы посчитаем число путей, ведущих в данную точку из точки s, и при этом мы будем пользоваться правилом суммы. Давайте постепенно начнем. Начать лучше всего с самой точки s. Количество способов попасть из точки s в точку s — такой способ есть только один: надо стоять на месте. Хорошо, продолжим с точкой сверху. В нее можно попасть одним способом: только перейдя из вершины s. Продолжим с нижней точкой. В нее тоже можно попасть только одним способом: только перейдя из вершины s. Посмотрим на точку в центре. С ней уже становится интересно: в нее можно попасть двумя разными способами. Есть два типа путей, ведущие в эту точку: через верх и через низ. Каждого из типов путей — один, и поэтому есть один плюс один — два способа попасть в центральную точку. Давайте рассмотрим точку сверху. Опять же, есть два способа попасть в верхнюю точку, есть два типа путей: есть пути, которые ведут из верхней точки, и такой путь один; и есть пути, которые ведут из центра, таких путей два. По правилу суммы, общее число путей один плюс два — три. Можно рассмотреть еще одну нижнюю точку. Тут все просто: есть только один способ попасть сюда, и такой путь, попадающий в предыдущую нижнюю точку, тоже один, поэтому здесь будет один путь. Наконец, последняя точка. Есть три способа попасть в точку t: можно попасть через верх, через центр или через низ. Есть три пути первого типа, два пути второго типа и один путь третьего типа. Применяя правило суммы дважды, мы получаем, что общее количество путей — это три плюс два плюс один — шесть путей. Итак, мы посчитали общее количество путей, и оказалось, что есть всего шесть путей, как пройти из точки s в точку t. Хорошо, но как могут возникать подобные задачи? На самом деле они возникают часто, но давайте рассмотрим простой пример: пусть у нас есть программа, и вершины на этой картинке — это на самом деле ее блоки, и при этом запуск каждого блока также запускает те блоки, в которые из этой вершины ведет стрелка. Например, пусть мы запустили блок в вершине s. Тогда он запускает также блоки в вершинах правее (сверху и снизу). Те, в свою очередь, запускают следующие блоки. Например, вершина в центре — в ней этот блок уже будет запущен дважды, потому что один раз он будет запущен вершиной через верх, и второй раз он будет запущен нижней вершиной. И так далее, блоки запускаются один за другим. Но давайте попробуем задаться таким вопросом: а сколько всего раз будет запущен блок t, если мы запустили блок s? Давайте проанализируем. Для каждого запуска блока t можно проследить его происхождение (откуда взялся этот запуск). Действительно, если мы запустили блок t, то он был запущен благодаря какому-то из предыдущих блоков, например, центральному, то есть мы запустили центральный блок, и он затребовал запуск блока t. Центральный блок, в свою очередь, был запущен кем-то предыдущим, например, верхней вершиной: мы запустили верхнюю вершину, и она вызвала запуск блока t. И так далее, мы можем для каждого запуска вершины t проследить, откуда он взялся. Это на самом деле просто путь из вершины s. Такая цепочка последовательных запусков, которая привела к запуску вершины t, — это некий путь из вершины s. Что осталось заметить? Запусков оказывается столько же, сколько путей из вершины s в вершину t. Таким образом могут возникать задачи о рекурсивных подсчетах. Итак, правило суммы очень простое, но оказывается, что даже его уже достаточно, чтобы делать нетривиальные подсчеты. На самом деле рекурсивные подсчеты могут быть очень полезны, и мы еще не раз увидим примеры этого позже в этом курсе.
