Основы программирования на языке Turbo Prolog

   repeat:-repeat.

 

   % выход из цикла для точки  (0,0)

   pos_point(0,0,_):-!.

   pos_point(X,Y,R):-      

      out_sqr(X,Y,R),!,

      write(" вне квадрата"), nl,

      fail.          

   pos_point(X,Y,R):-              

      in_circ(X,Y,R),!,

      write("внутри круга"), nl,

      fail.

  pos_point(_,_,_):-      

      !,

      write("вне круга и внутри квадрата"),

      nl, fail.

 

   out_sqr(X,Y,R):-     % условие  вне квадрата

      abs(X)>R;

      abs(Y)>R.

              

  in_circ(X,Y,R):-      % условие  внутри круга

     X*X+Y*Y<R*R.            

/*           Конец программы                   */

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

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

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

Подобным же образом в правиле можно использовать более одного правила повтора. Ниже приведено правило, включающее два правила повтора:

do_two_things :-

   repeat1,

   <повторяемое тело>,

   <условие выхода 1>,!,

   repeat2,

   <повторяемоу тело>,

   <условие выхода 2>,!.

 

repeat1.

repeat1 :- repeat1.

 

repeat2.

repeat2 :- repeat2.

Упражнение 4.3.

На числовую прямую с тремя отмеченными областями (от —¥ до —1, от —1 до 2 и от 2 до +¥). Показать, куда падает точка.

Упражнение 4.4.

Имеется база данных о результатах партий теннисного матча. Результаты представлены в программе в виде фактов типа:

win(tom,john).

Определить отношение class, которое будет распределять игроков по категориям:

profi — победитель всех сыгранных им матчей;

player —выигравший и проигравший хотя бы одну игру;

user — проигравший все матчи.

Если игрок отсутствует в базе, программа должна выдавать соответствующее сообщение.

ГЛАВА 5. МЕТОДЫ ОРГАНИЗАЦИИ РЕКУРСИИ

1. ПРОСТАЯ РЕКУРСИЯ

Правило, содержащее само себя в качестве компоненты, называется ПРАВИЛОМ РЕКУРСИИ. Правила рекурсии так же, как правила повтора, реализуют повторное выполнение задач. Они весьма эффективны, например, при формировании запросов к базе данных, а также при обработке таких доменных структур, как списки. Этот метод подходит для целого ряда применений, начиная с обработки файлов и кончая математическими вычислениями.

Если рекурсивное правило не генерирует указателей возврата, и последняя подцель правила является рекурсивным вызовом самого правила, то Турбо-Пролог устранит дополнительные расходы, вызываемые рекурсией.

Этот процесс называется УСТРАНЕНИЕМ ХВОСТОВОЙ РЕКУРСИИ.

Пример простого правила рекурсии:

write_string :-   /* выдать строку */

   write("У ПОПА БЫЛА СОБАКА..."),

   nl,

   write_string.

Это правило будет бесконечно вызывать само себя.

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

Формулировка условия выхода на русском языке для правила write_string может иметь вид: «Продолжать печать строки до тех пор, пока счетчик печати не превысит число 7. После чего остановить процесс».

Правило read_a_char демонстрирует простое правило рекурсии, в которое включено условие выхода. Программа циклически считывает символ, введенный пользователем: если этот символ не #, то он выдается на экран, если этот символ — #, то программа завершается.

Простое правило рекурсии с условием выхода:

read_a_char :-

   readchar(Ch),

   Ch <> '#',

   write(Ch),

   read_a_char.

2. МЕТОД ОБОБЩЕННОГО ПРАВИЛА РЕКУРСИИ

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

Тело правила состоит из утверждений и правил, определяющих задачи, которые должны быть выполнены. Ниже в символическом виде дан общий вид правила рекурсии:

<имя  правила рекурсии> :-

   (1)    <список предикатов>,

   (2)    <предикат условия  выхода>,

   (3)    <список предикатов>, 

   (4)    <имя правила рекурсии>, 

   (5)    <список предикатов>.

Данное правило рекурсии имеет пять компонент. Первая — это группа предикатов. Успех или неудача любого из них на рекурсиию не влияет.

Следующая компонента — предикат условия выхода. Успех или неудача этого предиката либо позволяет продолжить рекурсию, либо вызывает ее остановку. Третья компонента — список других предикатов. Аналогично, успех или неудача этих предикатов на рекурсию не оказывает влияния.

Четвертая группа — само рекурсивное правило. Успех этого правила вызывает рекурсию.

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

Правила, построенные указанным образом, являются обобщенными правилами рекурсии (ОПР), а метод называется ОПР-методом.

Например, вы хотите написать правило генерации всех целых чисел, начиная с 1 и кончая 7. Пусть имя правила будет write_number(Number).

write_number(8).

write_number(Number) :-

   Number < 8,

   write(Number), nl,

   Next_Number = Number + 1,

   write_number(Next_number).

Для этого примера первая компонента структуры общего правила рекурсии не используется. Второй компонентой, т.е. предикатом выхода, является Number < 8. Когда значение Number равно 8, правило будет успешным и программа завершится.

Третья компонента правила оперирует с числами. В этой части правила число выдается на экран и затем увеличивается на 1.

Для увеличенного числа будет использоваться новая переменная Next_Number. Четветая компонента — вызов самого правила рекурсии write_number(Next_number). Пятая компонента, представленная в общем случае, здесь не используется.

Программа начинается с попытки вычислить подцель write_number(1). Заметим, что необязательно вызывать правило, используя то же имя переменной, что используется в голове правила. Это всего лишь позиция в списке параметров, имеющая значение при передаче значений. Фактически, если не передавать значение Next_Number, то приращение основного числа программы невозможно. При рекурсивном вызове головы правила, программа снова пытается выполнить подцель write_number(8). Программа продолжает выполнять цикл сопоставления, присвоения и выдачи значений Number до тех пор, пока значение Number не станет равным 8. В этот момент цель выполнена, правило успешно и программа завершается.

Упражнение 5.1.

Измените правило рекурсии write_string так, чтобы результатом программы была семикратная печать строки

Используем правило рекурсии для вычисления суммы ряда целых чисел от 1 до 7:

S(7) = 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28

Правило рекурсии программы выполняет вычисления по обычной схеме сложения:

частичная сумма + следующее значение.

Правило 1 рекурсии имеет вид:

sum_series(1,1).         /* сумма1 ряда */

sum_series(Number,Sum) :-

   Number > 1,

   Next_number = Number — 1,

   sum_series(Next_number,Partial_Sum),

   Sum = Number + Partial_Sum.

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

Программа Сумма1 начинается с попытки выполнить подцель sum_series(7,Sum). Сначала программа пытается сопоставить подцель с подправилом sum_series(1,1). Сопоставление неудачно. Затем она пытается сопоставить подцель с sum_series(Number,Sum). На этот раз сопоставление завершается успешно с присвоением переменной Number значения 7. Затем программа сравнивает значение Number, которое равно 7, с 1 т.е. проверяется условие выхода. Так как 7 больше 1, то сопоставление успешно, программа переходит к следующему подправилу. Для этого подправила переменной Next_number присвоено значение 6, т.е. значение Number — 1. Затем правило вызывает само себя в виде sum_series(6,Partial_Sum). Следующим подправилом является правило Sum, содержащее свободную переменную Partial_Sum. Оно не может быть вызвано до тех пор, пока Partial_Sum не получит значения.

Теперь программа пытается сопоставить факт sum_series(1,1) с sum_series(6,Partial_Sum). Процесс сопоставления неуспешен, поскольку несопоставим ни один из параметров.

В результате программа переходит к следующему правилу с головой sum_series(Number,Sum), присваивая переменной Number значение 6. Этот циклический процесс сопоставления продолжается до тех пор, пока не будет получено sum_series(1,Partial_Sum). Теперь это правило сопоставляется с sum_series(1,1), а Partial_Sum приписывается значение 1. Переменная Sum получает, наконец, значение 3 (1+2).

Во время процесса сопоставления переменная Partial_Sum была свободна, а программа запоминала значения Number для последующего использования. Теперь эти значения извлекаются из стека, а Sum получает последовательно значения 6,10,15,21 и 28. Конечное значение Sum есть 28.

При возвратах, когда цель sum_series(1,Partial_Sum) сопоставится с правилом sum_series(Number,Sum) условие Number > 1 не даст

Next_number получить значение —1, а программе войти в бесконечную рекурсию.

/* Программа 5.1 «Сумма ряда». Назначение:*/

/*демонстрация  использования рекурсивного */

/*предиката  подсчета суммы S(N) ряда S,   */

/* где N положительное целое число         */

domains

   number, sum = integer

 

predicates

   sum_series(number, sum)

           

goal

   sum_series(7,Sum),

   write("Сумма ряда:"),nl,nl,

   write("   S(7) =  ", Sum), nl.

           

clauses

       

   sum_series(1,1).       /* сумма1 ряда */

   sum_series(Number,Sum) :-

      Number > 0,

      Next_number = Number — 1,

      sum_series(Next_number,Partial_Sum),

            Sum = Number + Partial_Sum.

/*           Конец программы                   */

Заменим правило sum_series на правило sum_series2. Правило sum_series2 является модификацией правила sum_series. Модификация выполнена посредством удаления условия выхода Number > 1 и введения правила

sum_series2(1,1) :- !.

вместо факта

sum_series(1,1).

Правило sum_series2 рекурсии:

sum_series2(1,1) :- !.   /* сумма2 ряда */

sum_series2(Number,Sum) :-

   Next_number = Number — 1,

   sum_series2(Next_number,Partial_Sum),

   Sum = Number + Partial_sum.

Результаты работы этих правил идентичны. Их следует рассматривать как альтернативные варианты. Сразу возникает вопрос: где во втором правиле условие выхода?

3. ГРАНИЧНОЕ УСЛОВИЕ РЕКУРСИИ. НИСХОДЯЩАЯ  И ВОСХОДЯЩАЯ РЕКУРСИИ

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

Решить ее позволит утверждение, называемое ГРАНИЧНЫМ УСЛОВИЕМ.

В задаче о вычислении суммы таким условием является

sum_series2(1,1) :- !.

Для ответа на запрос sum_series2(4,X) последовательно вычислялись sum_series2(3,S1), sum_series2(2,S2), sum_series2(1,S3) (граничное условие).

Такая рекурсия называется НИСХОДЯЩЕЙ.

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

Такая рекурсия называется ВОСХОДЯЩЕЙ.

В таком методе правило sum_series3 должно иметь два дополнительных параметра:

1) указание  на размер решенной к данному  моменту задачи (число уже просуммированных слагаемых);

2) запись  промежуточного решения (уже подсчитанной частичной суммы).

Запрос

sum_series3(1,1,7,X)

включает старое граничное условие, как уже решенную к настоящему моменту задачу.

Новое граничное условие выглядит так:

sum_series3(N,X,N,X):-!.

Правило 3 рекурсии:

/* M-текущее  слагаемое, S-частичная сумма, N-последнее слагаемое, X-окончательная сумма */

sum_series3(M,S,N,X):-

   M1=M+1,

   S1=S+M1,

   sum_series3(M1,S1,N,X).

Упражнение 5.2.

Вычислить и напечатать факториал числа 5 с помощью восходящей и нисходящей рекурсии.

4. ПРОГРАММА О ПОДСЧЕТЕ ЧИСЛА ТОЧЕК

/* Программа 5.2 «Подсчет точек». Назначение:  */

/*демонстрация  использования восходящей рекурсии */

constants

   r=2

domains

   i=integer

   r=real

predicates

   show_point

   culc_point(i,i,i,i,i,i)

   pos_point(i,i,i,r,r,i,i,i)

   out_sqr(r,r)

   in_circ(r,r)

goal

   show_point.

 

clauses

 

   show_point:-          

      clearwindow,

      % запрос с обнуленными счетчиками  точек

      culc_point(0,0,0,Sum1,Sum2,Sum3),

      write("вне квадрата ",Sum1,

            "внутри круга ",Sum2,

            "в квадрате вне круга ",Sum3).

 

   % рекурсивное правило

   culc_point(C1,C2,C3,Sum1,Sum2,Sum3):-

      write(" X? "),readreal(X),

      write(" Y? "),readreal(Y),

      pos_point(C1,C2,C3,X,Y,S1,S2,S3),!,nl,

   % вызов с новыми значениями  счетчиков

      culc_point(S1,S2,S3,Sum1,Sum2,Sum3). 

 

   %  выход из рекурсии с накопленными  счетчиками   

   culc_point(C1,C2,C3,C1,C2,C3).          

           

   % окончание запросов и отказ  процедуры 

   % pos_point      

   pos_point(_,_,_,0,0,_,_,_):-!,fail.

 

   % увеличение первого счетчика

   pos_point(C1,C2,C3,X,Y,S1,C2,C3):-

      S1=C1+1,      

      out_sqr(X,Y),!,

      write(" вне квадрата").          

 

   % увеличение второго счетчика

   pos_point(C1,C2,C3,X,Y,C1,S2,C3):-

      S2=C2+1,               

      in_circ(X,Y),!,

      write("внутри круга").

 

   % увеличение третьего счетчика

   pos_point(C1,C2,C3,_,_,C1,C2,S3):-

      S3=C3+1,      

      write("вне круга и внутри квадрата").

                

   % условие для точки вне квадрата

   out_sqr(X,Y):-

      abs(X)>r;

      abs(Y)>r.

   % условие для точки внутри  круга 

   in_circ(X,Y):-

      X*X+Y*Y<r*r.            

/*            Конец программы              */

Программа 5.2 содержит восходящую рекурсивную процедуру culc_point, благодаря которой происходит подсчет точек.

Первый вызов ее из цели верхнего уровня —

culc_point(0,0,0,Sum1,Sum2,Sum3), где первые три аргумента — текущие значения счетчиков, оставшиеся — конечные значения (сейчас они не имеют никакого значения и являются свободными переменными).