Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Этот принцип состоит в том, чтобы разбить задачу на случаи, относящиеся к двум группам:
(1) тривиальные, или "граничные" случаи;
(2) "общие" случаи, в которых решение получается из решений для (более простых) вариантов самой исходной задачи.
Этот метод мы использовали в Прологе постоянно. Рассмотрим еще один пример: обработка списка элементов, при которой каждый элемент преобразуется по одному и тому же правилу. Пусть это будет процедура
преобрспис(Спис, F, НовСпиc)
где Спис — исходный список, F — правило преобразования (бинарное отношение), а НовСпиc — список всех преобразованных элементов. Задачу преобразования списка Спис можно разбить на два случая:
(1) Граничный случай: Спис = []
Если Спис = [], то НовСпиc = [], независимо от F
(2) Общий случай: Спис = [X | Хвост]
Чтобы преобразовать список вида [X | Хвост], необходимо:
преобразовать список Хвост; результат — НовХвост;
элемент X по правилу F; результат — НовХ;
результат преобразования всего списка — [НовХ | НовХвост].
Тот же алгоритм, изложенный на Прологе:
преобрспис([], _, []).
преобрспис([X | Хвост], F, [НовХ | НовХвост]:-
G =.. [F, X, НовХ],
саll(G),
пpeoбpcпиc(Хвост, F, НовХвост).
Одна из причин того, что рекурсия так естественна для определения отношений на Прологе, состоит в том, что объекты данных часто сами имеют рекурсивную структуру. К таким объектам относятся списки и деревья. Список либо пуст (граничный случай), либо имеет голову и хвост, который сам является списком (общий случай). Двоичное дерево либо пусто (граничный случай), либо у него есть корень и два поддерева, которые сами являются двоичными деревьями (общий случай). Поэтому для обработки всего непустого дерева необходимо сначала что-то сделать с его корнем, а затем обработать поддеревья.
Дата публикования: 2015-10-09; Прочитано: 164 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!