Тема «Структуры данных: бинарные деревья. Основные

Работы со списками. Решение задач с помощью списков.

Тема «Структуры данных: списки. Основные предикаты

Задачи, решаемые с помощью перебора»

Тему можно начать с того, что при решении некоторого класса задач построение баз данных является слишком громоздким и утомительным занятием. Задача будет записана в более кратком виде, если воспользоваться структурой — списком. После того как будет дано определение списка (рекурсивное), следует вывести и записать на Прологе некоторые предикаты, получившие название основных. Для полного понимания работы со списками рекомендуется исполнить эти программы в режиме ручной трассировки.

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

Задание. Сдвинуть циклически элементы списка вправо.

Эта задача является обратной к более простой (на Прологе) задаче о циклическом сдвиге элементов списка влево и занимает одну строчку:

сдвиг_вправо(L,R):- сдвиг_влево(R,L).

В рамках темы рекомендуется решить такие классические задачи, как «Ханойские башни», «Задача о восьми ферзях», «Задача о перестановках», которые есть в ряде руководств.

предикаты. Решение задач с помощью бинарных деревьев»

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

Запись этой структуры на Прологе особенного труда не составит, но следует учитывать ее громоздкость, поэтому при выделении левых поддеревьев, корней и правых поддеревьев следует Придерживаться определенной системы, например использование Различных строк для каждой части дерева с отступами.

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

Выбор задач определяется главным достоинством бинарных Деревьев — эффективностью поиска, но результаты решения на прологе нагляднее в виде списков.

Дата добавления: 2014-12-27