Шумихин / Шумихин / Лабораторная работа №1 - Таран Е. Ю.

Одесский национальный университет им. И.И.Мечникова

Министерство науки и образования Украины

Лабораторная работа №1

по курсу: «Специализированые

языки программирования»

выполнил студент III курса

гр. МОКС, Таран Евгений Юрьевич

Одесса 2012

Цель работы: приобретение практических навыков использования

отсечения; составления и отладки программ с использованием

рекурсии в Пролог-программах.

1. Найти сумму целых последовательных чисел в интервале от

М до N (M<=N).

В данной задаче мы будем считать сумму только тех чисел, которые лежат внутри интервала, не учитывая границы, т. е. для значение 5, 6, или 5, 5 результатом будет 0.

Код программы:

sequsum(X,X,0):-!.

sequsum(X,X+1,0):-!.

sequsum(X,Y,Z) :- Y > X, X1 is X+1,

sequsum(X1,Y,Z1), Z is X+Z1.

calc(X,X,0):-!.

calc(X,Y,Z):- X1 is X+1,sequsum(X1,Y,Z).

Основную работу выполняет рекурсивный предикат sequsum. Целью его работы является последовательное вычисление суммы чисел входящих в интервал. Мы с помощью рекурсивных вызовов, сначала посчитаем значения для sequsum(Y-1,Y,Z), потом sequsum(Y-2,Y,Z), и т. д. накапливая полученную сумму. В конце мы получим значение, которое будет включать нижнюю границу, для этого будем вызывать данный предикат с началом отрезка на единицу большим, чем ввел пользователь.

Результаты тестирования:

2. Просуммировать целые положительные числа, следующие друг за другом с шагом d, и заканчивающиеся числом n. Значения d и n вводятся по запросу программы. (Например, n=11, d=3, суммируются числа 11+8+5+2=26). В случае d>=n сумма равна n.

Постановка задачи ясна, код программы:

sequsum(D,N,R):- N =< D, R = N,!.

sequsum(D,N,R):- N1 is N-D, sequsum(D,N1,R1),

R is N+R1.

start:- writef("Enter d << "),read(D),

writef("Enter n << "),read(N),

sequsum(D,N,R),write(R).

По вызову start, программа даст возможность пользователю ввести значения D и N. Далее вызывается рекурсивный предикат, который вначале раскрутит рекурсию до минимально значения n>0, и потом будет накапливать значение суммы, пока не вернется в первоначальный вызов.

Результаты тестирования:

3. Возвести вещественное число a в целую степень n (n может

быть положительной, нулевой или отрицательной).

Указания:

а) использовать рекурсивное выражение aⁿ =a*a^n-1.

б) использовать возможность вычислений для четной степени по формуле

a²ⁿ = aⁿ * aⁿ

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

degree(A,0,1):-!.

degree(A,1,A):-!.

degree(A,N,R):- N =< 0, N1 is (-N), degree(A,N1,R1), R is 1/R1,!.

degree(A,N,R):- (N mod 2) =:= 0, N1 is N/2, degree(A,N1,R1), R is (R1*R1),!.

degree(A,N,R):- N1 is N-1, degree(A,N1,R1), R is A*R1.

Мы имеем 2 тривиальных случая, когда степень равна 1 или 0, и 3 случая в которых мы рекурсивно вызываем предикат.

1). Если степень отрицательная, то значение возведение в степень будет

1 / a^-n , где n < 0.

2). Если степень кратная 2 то мы согласно условию б). раскладываем её.

3). И если мы дошли то последнего случая, мы уменьшаем степень на 1, и продолжаем считать возведение в степень для показателя на единицу меньшего.

Результат мы постоянно накапливаем и берем из 3-ей переменной предиката degree.

Результаты тестирования:

4. Найти N-ое число Фибоначчи. Ряд Фибоначчи 0, 1, 1, 2, 3,

5, 8, 13, 21, …

Код программы:

fib3(0,1,1):-!.

fib3(K,N1,N2):-

K1 is K-1,

fib3(K1, M1, M2),

N2 is M1,

N1 is M1 + M2.

fib(K,N):-fib3(K,N1,N).

Для вычисления чисел Фибоначчи пользователь будет вызывать функцию fib(K,N), где K – номер числа, а N – значение, которое необходимо найти. Для оптимизации решения мы используем предикат от 3-ех переменных, одновременно считая 2 числа, что позволит нам не вызывать предикаты, для нахождения 2-ух предыдущих чисел, для вычисления, следующего после них. Результаты тестирования:

5. Вычислить значение функции sin x, используя её разложение в ряд Маклорена. Вычисления проводить с заданной точностью E.

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

Код программы:

mysin(X,E,LASTVALUE,PREVRES,FACTN,SIGN,RES):-

abs(RES - PREVRES) < E,

writef("mysin = "),write(RES),

REALSIN is sin(X),writef("\nSWIsin= "),write(REALSIN),!.

mysin(X,E,LASTVALUE,PREVRES,FACTN,SIGN,RES):-

X1 is X*X,

PREVRES1 is RES,

FACT is (FACTN+1)*(FACTN+2),

FACTN1 is FACTN+2,

SIGN1 is SIGN * (-1),

LASTVALUE1 is LASTVALUE*X1/FACT,

RES1 is RES + SIGN1*LASTVALUE1,

mysin(X,E,LASTVALUE1,PREVRES1,FACTN1,SIGN1,RES1).

start(X,E):-

LASTVALUE is (X*X*X)/(2*3),

PREVRES is X,

FACT is 6,

FACTN is 3,

SIGN is -1,

RES is PREVRES + SIGN*LASTVALUE,

mysin(X,E,LASTVALUE,PREVRES,FACTN,SIGN,RES).

go(X,E):-

abs(X)<10,start(X,E),!.

go(X,E):-

X > 0, X1 is X - 2 * 3.14159265358979323,

calc(X1,E),!.

go(X,E):-

X < 0, X1 is X + 2 * 3.14159265358979323,

calc(X1,E).

calc(X,E):-

go(X,E).

Для того чтобы код был более понятен, и разделить алгоритмы, сделаны несколько вложенных предикатов. Для расчета синуса пользователь использует предикат calc(X,E) где X – точка в которой необходимо посчитать синус, Е – заданная точность. В ней используется предикат go(X,E), его задача подготовить точку для вычисления значения синуса. Дело в том, что для больших значений Х ( примерно abs (X) > 40 ), мы не может верно посчитать значение синуса, используя компьютерную алгебру ( при возведение больших чисел в высокие показатели степени, к примеру 40¹⁰⁰, нам не хватает допустимых значений переменных. Чтоб избежать этого, используем свойство периодичности синуса, и если точка Х больше 10, то отнимаем 2*PI, пока не получим небольшое число ( < 10 по модулю), если меньше 10, то прибавляем.

Далее вызывается функция start(X,E), которая подготавливает необходимые значения для 1-ой итерации.

LASTVALUE - значение последнего члена ряда Маклорена ,

PREVRES – результат предыдущей итерации для сравнение с последующей,

FACTN – накапливаем значение факториала ,

SIGN – определяем прибавляем или отнимаем последующий член

RES – результат данной итерации, который мы в начале 1 раз считаем по простой формуле. Далее мы вызываем рекурсивный предикат mysin, который вычисляет последующие члены ряда, вычисляет сумму ряда, и если достигнута заданная точность, выходит. Результаты тестирования:

Вывод

В данной лабораторной работе были получены базовые навыки работы со средой программирования SWI Prolog. Были написаны 5 программ, в которых использовались рекурсивные алгоритмы, и использовались отсечения. При выполнении этих заданий, были освоены методы организации рекурсивных предикатов в пролог – языке программирования, и использование отсечений, для правильности выполнения, и оптимизации пролог-программ. Также при написании пролог-программ, появились навыки трассировки (в SWI прологе – trace, predicate(…)), которые необходимы для исправления ошибок в работе программ.