Одесский национальный университет им. И.И.Мечникова Министерство науки и образования Украины
Лабораторная работа №2
по курсу «Специализированные языки программирования»
выполнил студент III курса гр. МОКС
Свиридов Артём
Одесса 2012
Цель работы: приобретение навыков работы со списками в Прологпрограммах.
Вариант: 1.
Задание 1.
Вводится список целых. Последний элемент списка 0.
1.Найти номер наибольшего элемента списка.
2.Удалить из введенного списка первое вхождение наибольшего элемента.
3.Вычислить среднее арифметическое первоначального списка.
4.Вычислить моду исходного списка.
5.Разбить первоначальный список на два. В первый включить элементы исходного списка с нечётными номерами, во второй – с чётными.
Код программы на Visual Prolog 7.3:
implement main open core, console
constants
className = "main". classVersion = "".
clauses
classInfo(className, classVersion).
domains
list = integer*.
class predicates
readlist : (list) procedure(o). writelist : (list) procedure(i).
findmaxnum : (list, integer) procedure(i,o). findmax : (list, integer, integer) procedure(i,i,o).
findelnum : (list, integer, integer, integer) procedure(i,i,i,o). delmax : (list,list) procedure(i,o).
del_el : (list, list, integer) procedure(i,o,i). findaver : (list,real) procedure(i,o).
findsum : (list,integer,integer) procedure(i,i,o). findnum : (list,integer,integer) procedure(i,i,o). sort : (list, list) procedure(i,o).
bubble : (list, list) procedure(i,o). findmode : (list, integer) procedure(i,o).
buildfreqlist : (list, integer, integer, list) procedure(i,i,i,o). buildnorepeat : (list,list) procedure(i,o).
onlyonemax : (list,integer) procedure(i,o).
findel : (list,integer,integer,integer) procedure(i,i,i,o). builduneven : (list,list) procedure(i,o).
buildeven : (list,list) procedure(i,o).
clauses
readlist([H|T]) :- H=read(), H <> 0, readlist(T), !. readlist([]).
writelist([H|T]) :- write(H," "), writelist(T),!. writelist([]).
findmaxnum([H|T],N) :- findmax([H|T],H,MAX), findelnum([H|T],MAX,1,N), !. findmaxnum([],0).
findmax([H|T],K,M) :- K<H, K2=H, findmax(T,K2,M), !.
findmax([_|T],K,M) :- findmax(T,K,M), !. findmax([],K,K).
findelnum([H|T],EL,N,NUM) :- H <> EL, N1=N+1, findelnum(T,EL,N1,NUM),!. findelnum(_,_,N,N).
delmax([H|T],L) :- findmax([H|T],H,MAX), del_el([H|T],L,MAX), !. delmax([],[]).
del_el([H|T],[H|L],EL) :- H <> EL, del_el(T,L,EL),!. del_el([_|T],T,_) :- !.
del_el([],[],_).
findaver([],0):-!.
findaver(L,AVER) :- findsum(L,0,SUM), findnum(L,0,N), AVER=SUM/N.
findsum([H|T],K,SUM) :- K1 = K + H, findsum(T,K1,SUM), !. findsum([],K,K).
findnum([_|T],K,NUM) :- K1 = K + 1, findnum(T,K1,NUM), !. findnum([],K,K).
sort(L,S) :- bubble(L,M), L <> M, sort(M,S),!. sort(L,L).
bubble([X,Y|R],[Y,X|R1]):- X>Y, bubble(R,R1),!. bubble([X|R],[X|R1]) :- bubble(R,R1),!. bubble([],[]).
findmode([],0):-!.
findmode(L,E):- sort(L,L1), buildfreqlist(L1,0,0,M),findmaxnum(M,N), buildnorepeat(L1,R), findel(R, 1, N- 1,F), onlyonemax(M,O), E = F * O.
buildfreqlist([],_,N,[N]) :- !.
buildfreqlist([H|T],K,N,[N|L]) :- H <> K, K1 = H, N1 = 1, buildfreqlist(T,K1,N1,L),!. buildfreqlist([_|T],K,N,L) :- N1 = N + 1, buildfreqlist(T,K,N1,L).
buildnorepeat([H,I|T],[H|L]) :- H <> I, buildnorepeat([I|T],L), !. buildnorepeat([_,I|T],L) :- buildnorepeat([I|T],L). buildnorepeat([L],[L]).
buildnorepeat([],[]).
onlyonemax([H|T],1) :- findmax([H|T],H,MAX1), delmax([H|T],L), findmax(L,H,MAX2), MAX1 <> MAX2, !. onlyonemax(_,0).
findel([_|T],K,N,E) :- K<>N, findel(T,K+1,N,E),!. findel([H|_],_,_,H) :- !.
findel([],_,_,0).
builduneven([H1,_|T],[H1|T1]) :- builduneven(T,T1), !. builduneven([H],[H]).
builduneven([],[]).
buildeven([_,H2|T],[H2|T1]) :- buildeven(T,T1), !. buildeven([_],[]).
buildeven([],[]).
clauses run():-
console::init(),
readlist(L),
findmaxnum(L,X),
write("number of a max-element: ",X),nl,
delmax(L,L1),
write("list where max-element is deleted: "), writelist(L1),nl,
findaver(L,A), write("average: ",A),nl,
findmode(L,M), write("mode: ",M),nl,
builduneven(L,E1),
write("List with uneven-numbered elements: "), writelist(E1),nl,
buildeven(L,E2),
write("List with even-numbered elements: "), writelist(E2),nl, console::clearInput(),
_=readline(). end implement main
goal mainExe::run(main::run).
Рассмотрим функции по порядку:
Общие функции.
readlist(L) – считывает список с клавиатуры поэлементно, до тех пор пока не введён 0 (аргумент L – полученный список);
writelist(L) – выводит список на экран (аргумент L – выводимый список).
Задача 1.
findmaxnum(L,N) – получает номер максимального элемента в списке (если их несколько – номер первого максимального элемента), где L – данный список, N – номер макс. элемента.
В процессе функция findmaxnum вызывает вспомогательные функции findmax (нахождение максимума) и findelnum (нахождение номера первого вхождения элемента с заданным значением, в данном случае – максимального элемента списка).
Задача 2.
delmax(L1,L2) – принимает список L1, находит максимальный элемент, создаёт список L2 с удалённым первым вхождением максимального элемента.
В процессе функция delmax вызывает вспомогательные функции findmax (вспом. функция из задачи 1) и del_el (удаление первого вхождения элемента в списке, в данном случае – максимального элемента).
Задача 3.
findaver(L,A) – находит среднее арифметическое A заданного списка L.
В процессе функция findaver вызывает вспомогательные функции findsum (сумма всех элементов списка) и findnum (количество всех элементов списка).
Задача 4.
findmode(L,M) – находит моду M заданного списка L; если в списке несколько элементов с одинаковой частотой, мода равна 0.
Алгоритм следующий: заданный список сортируется, по нему строится частотный список (например, для отсортированного списка [1 1 2 3 4 4 4 6] частотный список будет [2 1 1 3 1]). Находится номер максимального элемента частотного списка (в нашем примере элемент 3 – его номер 4).
Исключаем из отсортированного списка повторения, и находим элементмоду по полученному номеру. Если в частотном списке было несколько максимумов, мода равна нулю.
В процессе функция findmode вызывает вспомогательные функции sort (сортировка списка методом Пузырька – в свою очередь с помощью функции bubble), buildfreqlist (построение частотного списка), findmaxnum (функция-
решение задачи 1), buildnorepeat (исключает повторения из отсортированного списка), findel (нахождение элемента по номеру) и onlyonemax (проверка на несколько максимумов в списке).
Задача 5.
builduneven(L,L1) – строит список L1 из элементов с нечётными номерами списка L. Вспомогательных функций нет.
buildeven(L,L1) – строит список L1 из элементов с чётными номерами списка L. Вспомогательных функций также нет.
Результаты работы:
Задание 2.
Вводится два списка символов S1 и S2. Последний элемент списка ‘.’ Выяснить, является ли S2 подсписком S1. Если является, то найти список,
являющийся «разностью» этих списков
Код программы на Visual Prolog 7.3:
implement main open core, console
constants
className = "main". classVersion = "".
clauses
classInfo(className, classVersion).
domains
list = char*.
class predicates
readlist : (list) procedure(o). writelist : (list) procedure(i).
do_it : (list,list,list) procedure(i,i,o).
find : (list,list,integer,integer) procedure(i,i,i,o). contains : (list,list,integer) procedure(i,i,o).
delete_this : (list,integer,integer,integer,list) procedure(i,i,i,i,o). clearlist : (list,list) procedure(i,o).
findnum : (list,integer,integer) procedure(i,i,o).
clauses
readlist([H|T]) :- H=readChar(), H <> '.', readlist(T), !. readlist([]).
writelist([H|T]) :- write(H), writelist(T),!. writelist([]).
do_it(L1,L2,L3) :- find(L1,L2,1,C), C<>0, findnum(L2,0,N), delete_this(L1,C,C+N,1,L3), !. do_it(_,_,['0']):-!.
find([H|T],[H2|T2],N,K):-H<>H2, find(T,[H2|T2],N+1,K),!. find(L1,L2,N,N):-contains(L1,L2,Q),Q<>0,!. find([_|T],L2,N,K):-find(T,L2,N+1,K),!.
find([],_,_,0).
contains(_,[],1):-!. contains([],_,0):-!. contains([H|_],[H2|_],0):-H<>H2,!.
contains([_|T],[_|T2],C):-contains(T,T2,C).
delete_this([H|T],NUM,NUM2,N,[H|T3]):-N<NUM, delete_this(T,NUM,NUM2,N+1,T3),!. delete_this([_|T],NUM,NUM2,N,T3):-N>=NUM, N<NUM2-1, delete_this(T,NUM,NUM2,N+1,T3),!. delete_this([_|T],_,_,_,T):-!.
delete_this(_,_,_,_,[]).
clearlist([],[]):-!. clearlist([H|T],T1):-H='\n',clearlist(T,T1),!. clearlist([H|T],[H|T1]):-clearlist(T,T1).
findnum([],N,N):-!.
findnum([_|T],N,NUM) :- N1=N+1, findnum(T,N1,NUM).
clauses run():-
console::init(),
readlist(X1),
readlist(X2),
clearlist(X1,L1),
clearlist(X2,L2), do_it(L1,L2,L3), write("Result:"),nl, writelist(L3),nl, console::clearInput(), _=readline().
end implement main
goal mainExe::run(main::run).
Рассмотрим функции по порядку:
Общие функции.
readlist(L) – считывает список с клавиатуры поэлементно, до тех пор пока не встретит символ «.» (аргумент L – полученный список);
writelist(L) – выводит список на экран (аргумент L – выводимый список). clearlist(L,L1) – удаляет все символы переноса строки из списка L (для
удобства ввода – чтобы можно было вводить или каждый список в одной строчке, или посимвольно, по желанию пользователя).
Результирующая функция:
do_it(L1,L2,L3) – находит, является ли L2 подсписком L1. Если да – находит их разность в L3, если нет – L3 принимает значение [0].
Вспомогательные функции:
find – находит номер элемента, с которого начинается первое вхождение L2 в L1 – таким образом: ищет среди элементов L1 те, что равны элементу-голове L2, затем вызывает функцию contains, проверяющую, все равны ли последующие элементы L1 элементам L2;
сontains – описана выше;
findnum – находит количество символов списка;
delete_this – удаляет первое вхождение L2 в L1; аргументы: L1 – первый список, NUM – номер элемента, с которого начинается первое вхождение, NUM2 – номер элемента, которым заканчивается первое вхождение (NUM2 = NUM + количество элементов L2), L3 – результирующий список.
Результаты работы:
(результат – не 0, т.к. пустой список является подсписком пустого списка, их разность также пустой список)