Материал: Терёхин В. В. Turbo Prolog

Листинг 4.9

_______________________________________________________________

/* Программа: Сумма ряда 1 */ /* Назначение: Демонстрация использования рекурсивного */

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). /* сумма ряда */ sum_series(Number,Sum) :-

Number > 0,

Next_number = Number - 1, sum_series(Next_number, Partial_Sum), Sum = Number + Partial_Sum.

____________________________________________________________

Программа Сумма ряда 1 (листинг 4.9) использует правило рекурсии для вычисления суммы ряда целых чисел от 1 до 7:

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

или

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

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

1Начальное значение

+2 Следующее значение

___

3Частичная сумма

+3 Следующее значение

___

6Частичная сумма

91

Number > 0,

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, с 0, т.е. проверяется условие выхода. Так как 7 больше 0, то сопоставление успешно, программа переходит к следующему подправилу.

Для этого подправила переменной Next_number присвоено значение 6, т.е. значение Number - 1. Затем правило вызывает само себя в виде sum_series(6,Partial_Sum). Следующим подправилом является правило Sum, содержащее свободную переменную Partial_Sum. Так как только что был вызван рекурсивный процесс, то правило 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 получает значение 1. Так как сопоставление продолжается дальше, то Next_number получает значение 0 (1 - 1). При следующем цикле сопоставления переменная Number получает значение 0. Во время сопоставления с условием выхода правило оказывается неуспешным, и сопоставление "прыгает" к правилу

Sum.

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

* Упражнения

92

4.13.Модифицируйте программу Сумма ряда 1 так, чтобы ее результатом была сумма следующего ряда нечетных чисел:

S(15) = 1 + 3 + 5 + . . . + 15

4.14.Постройте таблицу обрабатываемых значений для программы Сумма ряда 1, показывающую работу правила рекурсии.

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) :- !. /* сумма ряда */ sum_series(Number,Sum) :-

Next_number = Number - 1, s um_series(Next_number, Partial_Sum),

Sum = Number + Partial_sum.

______________________________________________________

Программа Сумма ряда 2 (листинг 4.10) является модификацией программы Сумма ряда 1. Модификация выполнена посредством

удаления условия выхода Number > 0 и введения правила sum_series(1,1) :- !.

вместо sum_series(1,1).

Сравним вид правила рекурсии в предыдущей программе с модифицированным правилом рекурсии в программе Сумма ряда 2:

Правило рекурсии Сумма ряда 1 sum_series(1,1). /* сумма ряда */ sum_series(Number,Sum) :-

Number > 0,

Next_number = Number - 1, sum_series(Next_number, Partial_Sum),

93

Результаты работы этих правил идентичны. Использование отсечения

(!) в Сумме ряда 2 не улучшает работы правила рекурсии. Эти два правила следует рассматривать как альтернативные варианты.

*Упражнения

4.15.Модифицируйте программу Сумма ряда 2 так, чтобы она вычисляла сумму следующего ряда целых четных чисел:

S(16) = 2 + 4 + 6 + 8 + 10 + 12 + 14 + 16.

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

Листинг 4.11

_______________________________________________________________

domains

number, product = integer

predicates

factorial(number, product)

goal

factorial(7,Result),

write(" 7! = ",Result),nl.

clauses

factorial(1,1) :- !. factorial(Number,Result) :-

Next_number = Number -1, facto-rial(Next_number, Partial_factorial),

Result = Number * Partial_factorial.

_______________________________________________________________

94

Программа Факториал (листинг 4.11) использует правило рекурсии для вычисления и печати факториала целого числа. (Факториал числа N записывается как N!. Восклицательный знак это распространенное обозначение факториала и его не следует путать с символом для отсечения). N! есть произведение всех целых чисел от 1 до N:

N! = N * (N-1) * (N-2) * ... 2 * 1

Примеры:

1! = 1 2! = 2 * 1 = 2

3! = 3 * 2 * 1 = 6 4! = 4 * 3 * 2 * 1 = 24

5! = 5 * 4 * 3 * 2 * 1 = 120 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720

7! = 7 * 6 * 5 * 4 * 3 * 2 * 1 = 5040

Основополагающая структура правила рекурсии для вычисления факториала точно такая же как и для правила рекурсии предыдущей программы. Для суммирования ряда использовалось последовательное суммирование.

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

factorial(1,1) :- !. factorial(Number,Result) :-

Next_number = Number -1, facto-rial(Next_number, Partial_factorial),

Result = Num-ber*Partial_factorial.

В результате работы программы получим 7! = 5040.

*Упражнение

4.17.Измените программу Факториал так, чтобы она вычисляла и выдавала на экран факториал 10. Факториал 10 равен 3 628 800. Предупреждение: Для вычисления используйте домен действительных чисел. Результат слишком велик для того, чтобы его хранить в переменной целого типа. Это объясняется тем, что в Турбо-Прологе верхний предел для значения целого числа равен 32 767.

4.6 Обзор содержания главы

В данной главе были рассмотрены четыре метода построения правил: метод отката после неудачи (ОПН), метод отсечения и отката (ОО), метод повтора (МП), определяемый пользователем и обощенное правило рекурсии

(ОПР).

95