Рекурсия и деревья - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Рекурсия и деревья. Доклад-сообщение содержит 14 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Рекурсия и деревья Лекция №8

Слайд 2

Описание слайда:

Рекурсия

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

Рекурсия и поисковые задачи С помощью рекурсии легко решаются задачи, связанные с поиском, основанном на полном или частичном переборе возможных вариантов. Принцип рекурсивности заключается здесь в следующем: Процесс поиска разбивается на шаги; На каждом выбирается и проверяется очередной элемент из множества; Алгоритм поиска повторяется, но уже для «оставшихся» данных. При этом вовсе не важно, каким образом цепочка шагов достигнет цели и сколько вариантов будет перебираться.

Слайд 5

Описание слайда:

Результат рекурсивной функции Если рекурсивная функция имеет результат void, то она не может повлиять на характер протекания процесса поиска и реализуемый алгоритм будет выполнять полный перебор всех возможных вариантов; Если рекурсивная функция выполняет поиск первого попавшегося варианта, то результатом ее является как правило логическое значение (в Си - 0/1). При этом «ИСТИНА» соответствует успешному завершению поиска, а «ЛОЖЬ» - неудачному. Общим для всех алгоритмов поиска является: если рекурсивный вызов возвращает «ИСТИНУ», то она должна быть немедленно «передана наверх», то есть текущий вызов также должен быть завершен со значением «ИСТИНА». Если рекурсивный вызов возвращает «ЛОЖЬ», по поиск должен быть продолжен. При завершении полного перебора всех вариантов рекурсивная функция также должна возвратить «ЛОЖЬ»; Если в процессе поиска производится более сложный анализ и сравнение вариантов, то рекурсивная функция и, соответственно, шаг процесса должны производить выбор между подходящими вариантами, в целью выбора наиболее оптимального. Обычно для этого используется минимум или максимум какой-либо характеристики выбираемого варианта. Тогда рекурсивная функция возвращает значение, которое является оценкой для оставшихся не просмотренных элементов, а текущий рекурсивный вызов выбирает из них минимум или максимум с учетом данных текущего шага.

Слайд 6

Описание слайда:

Рекурсивная структура данных По аналогии с рекурсивным вызовом функции существуют структуры данных, допускающие рекурсивное определение: элемент структуры данных содержит один или несколько указателей на элементы такого же типа. Формально это соответствует тому факту, что в определении структурированного типа содержится указатель на себя самого. Из подобных структур данных были рассмотрены списки. Однако функции, работающие с ними, не были рекурсивными.

Слайд 7

Описание слайда:

Деревья Определение дерева имеет исключительно рекурсивную природу. Элемент этой структуры данных называется вершиной (узлом). Дерево представляет собой либо отдельную вершину, либо вершину, имеющую ограниченное число указателей другие деревья (ветвей). Нижележащие деревья для текущей вершины называются поддеревьями, а их вершины – потомками. По отношению к потомкам текущая вершина называется предком.

Слайд 8

Описание слайда:

Деревья

Слайд 9

Описание слайда:

Работа с деревьями

Слайд 10

Описание слайда:

Бинарные деревья

Слайд 11

Описание слайда:

Бинарные деревья. Структура и обход

Слайд 12

Описание слайда:

Добавление нового элемента в бинарное дерево

Слайд 13

Описание слайда:

Удаление элемента из дерева

Слайд 14

Описание слайда:

Пример. Сортировка элементов массива с помощью дерева Написать программу, подсчитывающую частоту встречаемости слов входного потока. Поскольку список слов заранее не известен, мы не можем предварительно упорядочить его. Неразумно пользоваться линейным поиском каждого полученного слова, чтобы определять, встречалось оно ранее или нет, т.к. в этом случае программа работает слишком медленно. Один из способов — постоянно поддерживать упорядоченность уже полученных слов, помещая каждое новое слово в такое место, чтобы не нарушалась имеющаяся упорядоченность. Воспользуемся бинарным В дереве каждый узел содержит: указатель на текст слова; счетчик числа встречаемости; указатель на левого потомка; указатель на правого потомка.

Теги Рекурсия деревья

Похожие презентации