Компьютерный форум

Компьютерный форум (http://www.hardforum.ru/)
-   Prolog (http://www.hardforum.ru/f141/)
-   -   4. Написать программу, которая возвращает список (http://www.hardforum.ru/t128775/)

Roper21 18.12.2017 14:55

4. Написать программу, которая возвращает список
 
Написать программу, которая возвращает список (m1 m2 m3), состоящий из трех наибольших элементов исходного числового списка s: m1>=m2>=m3. Исходный список содержит не менее трех элементов.

Как это реализовать? помогите пожалуйста

aag 18.12.2017 15:12

Исходный -> Отсортированный в обратку
[A, B, C | _ ] = Отсортированный в обратку
Out = [ A, B, C ]

Roper21 18.12.2017 15:50

Вот что смог написать
Я отсортировал список по убыванию
prolog Код:
domains
i=integer
il=i*
predicates
max(i,i,i)
maxl(il,i)
del(i,il,il)
sort(il,il)
exsistlist(il,il)
clauses
max(X,Y,X):-X>=Y,!.
max(_,Y,Y).
maxl([X],X):-!.
maxl([X|T],R):-
maxl(T,R1),max(X,R1,R).
del(X,[X|T],T):-!.
del(X,[Y|T],[Y|L]):-del(X,T,L).
sort([],[]):-!.
sort(L,[El|R2]):-
maxl(L,El),del(El,L,R1),sort(R1,R2).
exsistlist(X,Y):-sort(X,[H1,H2,H3|_]),
//как добавить элемент H1 H2 H3 в Y,!.

goal
exsistlist([1,2,3,4,5,6],K).
Теперь проблема, как добавить первые три элемент в список Y
Подскажите пожалуйста

Винитарх 18.12.2017 19:33

Цитата:

Сообщение от Roper21 (Сообщение 859907)
exsistlist(X,Y):-sort(X,[H1,H2,H3|_]),
//как добавить элемент H1 H2 H3 в Y,!.

exsistlist(X,[H1,H2,H]):-sort(X,[H1,H2,H3|_]).

SergeMukhin78 19.12.2017 01:28

я думаю, что задание не планировало использовать sort. т.е. надо три раза вызвать предикат получить_максимум_и_остальной_список

aag 19.12.2017 17:09

Или удалять из списка минимумы, пока не останется три искомых максимума?!)))

SergeMukhin78 19.12.2017 17:23

Цитата:

Сообщение от aag (Сообщение 859965)
Или удалять из списка минимумы, пока не останется три искомых максимума?!)))

это хуже, мой алгоритм O(N), а этот O(N**2)

aag 19.12.2017 19:37

Дык вроде собрались поусложнять?!)))

SergeMukhin78 19.12.2017 20:32

Цитата:

Сообщение от aag (Сообщение 859969)
собрались поусложнять?

почему? алгоритм с сортировкой O(N ln(N)), т.е. мой алгоритм самый быстрый, всего за три прохода (а можно и за один).

aag 19.12.2017 21:38

Цитата:

Сообщение от SergeMukhin78 (Сообщение 859974)
т.е. мой алгоритм самый быстрый, всего за три прохода (а можно и за один).

Я не про скорость, я про путанницу для студента...

Всего за три прохода?! А как это за один проход выцепить максимум и вернуть список без этого максимума? Заранее благодарен)))

Можно и за один проход - это ж ведь сортировка вставкой получится? Нет?

Винитарх 19.12.2017 22:39

Цитата:

Сообщение от SergeMukhin78 (Сообщение 859974)
всего за три прохода (а можно и за один).

Да, можно и за один, но в нём всё равно будет проверка очередного элемента с тремя кандидатами (в худшем случае).
Поэтому как было три быстрых прохода (3*N), так и останется (3*N) при одном, но медленном. Имхо.

SergeMukhin78 19.12.2017 23:01

Цитата:

Сообщение от aag (Сообщение 859975)
сортировка вставкой

сортировка вставкой это O(N**2) Точнее на прологе O(N^2). Это не интересно.

Цитата:

Сообщение от Винитарх (Сообщение 859977)
как было три быстрых прохода (3*N), так и останется (3*N)

O(N) == O(3*N)

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

aag 19.12.2017 23:04

Повторяюсь)))
Цитата:

Сообщение от aag (Сообщение 859975)
Всего за три прохода?! А как это за один проход выцепить максимум и вернуть список без этого максимума? Заранее благодарен)))


SergeMukhin78 19.12.2017 23:10

странно, кажется это более чем просто.

как-то так:
A = maxP(List, upperBound(integer)),
B = maxP(List, A),
C = maxP(List, B),
Result = [A, B, C].

где maxP пробегает по списку и выдаёт максимальное в списке, но меньше второго параметра.
Эту ф-ию трудно написать?

ps
нет проверки, что список как мин из 3х элементов, но это ещё проще

aag 19.12.2017 23:12

Цитата:

Сообщение от SergeMukhin78 (Сообщение 859983)
странно, кажется это более чем просто.

как-то так:
A = maxP(List, upperBound(integer)),
B = maxP(List, A),
C = maxP(List, B),
Result = [A, B, C].

где maxP пробегает по списку и выдаёт максимальное в списке, но меньше второго параметра.
Эту ф-ию трудно написать?

ps
нет проверки, что список как мин из 3х элементов, но это ещё проще

Не, не пойдёт... Могут быть одинаковые... А могут и не быть... Удалять таки придётся максимум всякий раз...

[5,5,3,3,3] чего выдаст?


Часовой пояс GMT +4, время: 14:22.

Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.