Предикаты ввода-вывода. Организация диалоговых программ. Решение задач на поиск в базах знаний с использованием
операторов сравнения и арифметических операторов»
В данной теме дается расширение языка введением перечисленных в заголовке темы операторов и предикатов. При рассмотрении арифметических операторов и операторов сравнения следует обратить внимание на различия в их написании и работе между стандартом языка и конкретной системой программирования (в особенности Турбо Прологом).
Тема «Рекурсия на Прологе (нисходящая стратегия). Ручная трассировка рекурсивных программ. Решение задач на символьную арифметику. Рекурсия: восходящая стратегия»
На Прологе рекурсивный метод является единственным способом решения задач с помощью минимального количества определений, повторяющихся в процессе поиска утверждений (подобно команде повторения в процедурных языках). Трудность в его понимании объясняется недостаточной методической проработкой. Как правило, в руководствах метод не объясняется, а показывается на примере единственной функции факториал (кстати, почти не используемой в школьном курсе математики).
Суть метода можно разъяснить следующим образом: если решение исходной задачи может быть сведено к решению другой (как правило, более простой) подзадачи, причем эта подзадача есть уменьшенный вариант исходной задачи (с таким же количеством исходных данных и результатов) и также сводима к другой подзадаче, то этот процесс называется рекурсией. Надо заметить, что способ разбиения и решения подзадачи идентичен примененному к исходной задаче.
|
|
|
Для того чтобы описанный метод был результативным, он должен привести к задаче, решаемой непосредственно (декларативно). Декларативное решение задачи называется граничным условием.
Из этого объяснения следует, что для того чтобы решить зада-ЧУ рекурсивно, необходимо:
а) определить связь между исходной и вспомогательной задачей;
б) определить граничное условие.
Пример. Найти сумму первых N натуральных чисел рекурсивным методом.
Заметим, что результат есть функция, зависящая от количества натуральных чисел S(N), которая выражается так:
Первые (N — 1) слагаемых есть результат такой же функции от (N - 1) членов. Значит, это — вспомогательная задача, которая удовлетворяет условиям рекурсивного метода. Граничное условие запишется так: S(1) = 1. Таким образом, математическая формулировка задачи имеет вид:
Теперь решение задачи нетрудно записать на Прологе:
сумма(1,1):-!. /* Граничное условие, S(N)=1 */
сумма(N,S):-M is N-l, /* M=N-1 */
сумма(M,S), /* Вспомогательная задача */
S is C+N. /* Связь между задачами */
Стратегия, использованная при решении данной задачи, имеет название восходящей. Для полного понимания метода рекомендуется исполнять некоторые программы в режиме ручной трассировки. Кроме того, необходимо на первых этапах усвоения материала записывать на Прологе функции, выраженные в математической форме. В рамках темы можно решить ряд задач, получивших название «Символьная арифметика». При этом преследуют следующие цели: во-первых, более глубоко понять природу рекурсивных функций, во-вторых, уяснить, что в определении арифметических операций лежит рекурсивный метод.
|
|
|
Восходящая стратегия является разновидностью рекурсивного метода. В основе лежит следующая идея: от граничного условия решать задачи большего размера. Для этого вводятся два дополнительных параметра — размер решенной задачи и промежуточный результат. С помощью этой стратегии, как правило, решаются переборные задачи.
Дата добавления: 2015-12-21; просмотров: 15; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!