Основная цель этой главы заключается в исследовании рекурсивных программ и структур данных как практических инструментов. ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Седжвик Р.N. Фундаментальные алгоритмы на с++ Части1-4


Основная цель этой главы заключается в исследовании рекурсивных программ и структур данных как практических инструментов. Вначале исследуется взаимосвязь между математической рекурсией и простыми рекурсивными программами и приводится ряд примеров применения рекурсии. Затем рассматривается фундаментальная рекурсивная схема, известная под названием разделяй и властвуй, которая используется для решения задач общего характера в нескольких последующих разделах этой книги. После этого приводится общий подход к реализации рекурсивных программ, называемый динамическим программированием, который предоставляет эффективные и элегантные решения для обширного класса задач. Затем подробно рассматриваются деревья, их математические свойства и связанные с ними алгоритмы, в том числе базовые методы обхода дерева ( tree traversal), которые лежат в основе рекурсивных программ обработки деревьев. В завершение будут анализироваться тесно связанные с рекурсией алгоритмы обработки графов - в частности, особое внимание будет уделяться фундаментальной рекурсивной программе поиска в глубину ( depth-first search), которая служит основой для многих алгоритмов обработки графов.

(cкачать страницу)

Смотреть книгу на libgen

Основная цель этой главы заключается в исследовании рекурсивных программ и структур данных как практических инструментов.  Вначале исследуется взаимосвязь между математической рекурсией и простыми рекурсивными программами и приводится ряд примеров применения рекурсии.  Затем рассматривается фундаментальная рекурсивная схема,  известная под названием разделяй и властвуй,  которая используется для решения задач общего характера в нескольких последующих разделах этой книги.  После этого приводится общий подход к реализации рекурсивных программ,  называемый динамическим программированием,  который предоставляет эффективные и элегантные решения для обширного класса задач.  Затем подробно рассматриваются деревья,  их математические свойства и связанные с ними алгоритмы,  в том числе базовые методы обхода дерева ( tree traversal),  которые лежат в основе рекурсивных программ обработки деревьев.  В завершение будут анализироваться тесно связанные с рекурсией алгоритмы обработки графов  -  в частности,  особое внимание будет уделяться фундаментальной рекурсивной программе поиска в глубину ( depth-first search),  которая служит основой для многих алгоритмов обработки графов.