Представление бинарных деревьев

Недетерминирванное программирование

Представление многочленов в Турбо-Прологе

Использование языка Турбо-Пролог для решения задач

Для представления многочленов в Турбо-Прологе используются составные термы и списки. Любой многочлен может быть представлен формулой P(x)= a₀+a₁x+a₂x²+…+a_nxⁿ.

Использование составного терма fun = x (integer, integer), где первый аргумент означает коэффициент a_i, а второй аргумент означает степень i переменной x, позволяет представить любое слагаемое полинома. Весь полином может быть представлен в виде списка слагаемых, то есть в виде списка термов типа fun.

Пример 52:

Пусть дан многочлен P(x)= 2-3x+5x²:

Опишем многочлен функцией вида fun:

Р = [x (a₀, 0), x (a₁, 1), x (a₂, 2)], то есть Р = [x(2, 0),x(-3, 1),x(5, 2)].

Пример 53: написать программу сложения двух полиномов.

domains

fun= x (integer, integer)

list=fun*

predicates

add_mn (list, list, list)

clauses

add_mn ([], Q, Q).

add_mn (P, [], P).

add_mn ([x(Pc, Pp)\ Pt], [x(Qc, Qp)\ Qt], [x(Pc, Pp)\ Rt]):-

Pp<Qp, add_mn(Pt, [x{Qc, Qp)| Qt], Rt).

add_mn ([x(Pc, Pp)\ Pt], [x(Qc, Qp)\ Qt], [x(Qc, Qp)\ Rt]):-

Pp>Qp, add_mn([x(Pc, Pp)\Pt], Qt, Rt).

add_mn ([x(Pc, Pp)\ Pt], [x(Qc, Qp)\ Qt], [x(Rc, Pp)\ Rt]):-

Rc= Pc + Qc, Rc<>0, add_mn(Pt, Qt, Rt).

add_mn ([x(Pc, Pp)\ Pt], [x(Qc, Qp)\ Qt], Rt):-

Rc= Pc + Qc, Rc=0, add_mn(Pt, Qt, Rt).

Граничные условия предиката выражены двумя первыми фактами: если один из многочленов равен 0, то результатом будет второй многочлен.

Рекурсивные правила 3, 4, 5 и 6 означают следующее:

Если степень первого элемента в P меньше степени первого элемента в Q, то первым элементом R будет первый элемент P, а хвост R получается сложением хвоста P и полинома Q.

Если степень первого элемента в P больше степени первого элемента в Q, то первым элементом R будет первый элемент Q, а хвост R получается сложением полинома P и хвоста Q.

Если степени первых элементов в P и Q равны, а сумма их коэффициентов отлична от 0, то коэффициент первого элемент в R будет равен сумме коэффициентов первых элементов из P и Q, а хвост R получается сложением хвостов P и Q.

Если степени первых элементов в P и Q равны, а сумма их коэффициентов тоже равна 0, то R получается сложением хвостов P и Q.

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

Представление бинарных деревьев основано на определении рекурсивной структуры данных, использующей функцию типа tree (Left, Top, Right), где Top - вершина дерева, Left и Right - соответственно левое и правое поддерево. Пустое дерево обозначим термом nil.

Пример 54:

Пусть дано дерево следующего вида:

a

b c

d e

Такое дерево может быть задано следующим образом:

1. tree (tree (nil, d, nil), b, tree (nil, e, nil)).

2. tree (nil, c, nil).

3. tree (tree (tree (nil, d, nil), b, tree (nil, e, nil)), a, tree (nil, c, nil)).

Типовое определение бинарного дерева можно выразить следующими двумя правилами:

binary_tree (nil).

binary_tree (tree (Left, Top, Rigth)):- binary_tree (Left), binary_tree (Rigth).

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

Пример 55: написать программу печати вершин бинарного дерева, начиная от корневой и следуя правилу левого обхода дерева.

domains

treetype = tree(treetype, symbol, treetype);nil()

predicates

print_all_elements(treetype)

clauses

print_all_elements(nil).

print_all_elements(tree(X, Y, Z)):-

write(Y), nl,

print_all_elements(X),

print_all_elements(Z).

goal

print_all_elements(tree(tree(nil, b, nil), a,

tree(tree(nil, d, nil),

c, tree(nil, e, nil)))).

Пример 56: написать программу проверки изоморфности двух бинарных деревьев.

domains

treetype = tree(treetype, symbol, treetype);nil()

predicates

isotree (treetype, treetype)

clauses

isotree (T, T).

isotree (tree (L1, X, R1), tree (L2, X, R2)):- isotree (L1, R1), isotree (L2, R2).

isotree (tree (L1, X, R1), tree (L2, X, R2)):- isotree (L1, R2), isotree (L2, R1).

Дата добавления: 2015-06-27