Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Prolog
Перезагрузить страницу 4. Написать программу, которая возвращает список
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Roper21 Roper21 вне форума
Новичок
 
Сообщений: 2
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 18.12.2017
По умолчанию 4. Написать программу, которая возвращает список - 18.12.2017, 14:55

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

Как это реализовать? помогите пожалуйста
Ответить с цитированием
  (#2 (permalink)) Старый
aag aag вне форума
А.А.Г.
 
Аватар для aag
 
Сообщений: 3,397
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
Адрес: Адмиралтейская)))
По умолчанию 18.12.2017, 15:12

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


импортирован с progz.ru
Ответить с цитированием
  (#3 (permalink)) Старый
Roper21 Roper21 вне форума
Новичок
 
Сообщений: 2
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 18.12.2017
По умолчанию 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
Подскажите пожалуйста
Ответить с цитированием
  (#4 (permalink)) Старый
Винитарх Винитарх на форуме
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,930
Сказал(а) спасибо: 2
Поблагодарили 298 раз(а) в 298 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 18.12.2017, 19:33

Цитата:
Сообщение от Roper21 Посмотреть сообщение
exsistlist(X,Y):-sort(X,[H1,H2,H3|_]),
//как добавить элемент H1 H2 H3 в Y,!.
exsistlist(X,[H1,H2,H]):-sort(X,[H1,H2,H3|_]).
Ответить с цитированием
  (#5 (permalink)) Старый
SergeMukhin78 SergeMukhin78 вне форума
Member
 
Сообщений: 534
Сказал(а) спасибо: 17
Поблагодарили 33 раз(а) в 33 сообщениях
Регистрация: 28.03.2012
По умолчанию 19.12.2017, 01:28

я думаю, что задание не планировало использовать sort. т.е. надо три раза вызвать предикат получить_максимум_и_остальной_список
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
aag aag вне форума
А.А.Г.
 
Аватар для aag
 
Сообщений: 3,397
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
Адрес: Адмиралтейская)))
По умолчанию 19.12.2017, 17:09

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


импортирован с progz.ru
Ответить с цитированием
  (#7 (permalink)) Старый
SergeMukhin78 SergeMukhin78 вне форума
Member
 
Сообщений: 534
Сказал(а) спасибо: 17
Поблагодарили 33 раз(а) в 33 сообщениях
Регистрация: 28.03.2012
По умолчанию 19.12.2017, 17:23

Цитата:
Сообщение от aag Посмотреть сообщение
Или удалять из списка минимумы, пока не останется три искомых максимума?!)))
это хуже, мой алгоритм O(N), а этот O(N**2)
Ответить с цитированием
  (#8 (permalink)) Старый
aag aag вне форума
А.А.Г.
 
Аватар для aag
 
Сообщений: 3,397
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
Адрес: Адмиралтейская)))
По умолчанию 19.12.2017, 19:37

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


импортирован с progz.ru
Ответить с цитированием
  (#9 (permalink)) Старый
SergeMukhin78 SergeMukhin78 вне форума
Member
 
Сообщений: 534
Сказал(а) спасибо: 17
Поблагодарили 33 раз(а) в 33 сообщениях
Регистрация: 28.03.2012
По умолчанию 19.12.2017, 20:32

Цитата:
Сообщение от aag Посмотреть сообщение
собрались поусложнять?
почему? алгоритм с сортировкой O(N ln(N)), т.е. мой алгоритм самый быстрый, всего за три прохода (а можно и за один).
Ответить с цитированием
  (#10 (permalink)) Старый
aag aag вне форума
А.А.Г.
 
Аватар для aag
 
Сообщений: 3,397
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
Адрес: Адмиралтейская)))
По умолчанию 19.12.2017, 21:38

Цитата:
Сообщение от SergeMukhin78 Посмотреть сообщение
т.е. мой алгоритм самый быстрый, всего за три прохода (а можно и за один).
Я не про скорость, я про путанницу для студента...

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

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


импортирован с progz.ru
Ответить с цитированием
  (#11 (permalink)) Старый
Винитарх Винитарх на форуме
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,930
Сказал(а) спасибо: 2
Поблагодарили 298 раз(а) в 298 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 19.12.2017, 22:39

Цитата:
Сообщение от SergeMukhin78 Посмотреть сообщение
всего за три прохода (а можно и за один).
Да, можно и за один, но в нём всё равно будет проверка очередного элемента с тремя кандидатами (в худшем случае).
Поэтому как было три быстрых прохода (3*N), так и останется (3*N) при одном, но медленном. Имхо.
Ответить с цитированием
  (#12 (permalink)) Старый
SergeMukhin78 SergeMukhin78 вне форума
Member
 
Сообщений: 534
Сказал(а) спасибо: 17
Поблагодарили 33 раз(а) в 33 сообщениях
Регистрация: 28.03.2012
По умолчанию 19.12.2017, 23:01

Цитата:
Сообщение от aag Посмотреть сообщение
сортировка вставкой
сортировка вставкой это O(N**2) Точнее на прологе O(N^2). Это не интересно.

Цитата:
Сообщение от Винитарх Посмотреть сообщение
как было три быстрых прохода (3*N), так и останется (3*N)
O(N) == O(3*N)

Один медленный проход может быть существенно лучше, чем три быстрых прохода, например если весь список не вмещается в оперативную память или в кеш какого-то уровня.
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
aag aag вне форума
А.А.Г.
 
Аватар для aag
 
Сообщений: 3,397
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
Адрес: Адмиралтейская)))
По умолчанию 19.12.2017, 23:04

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


импортирован с progz.ru
Ответить с цитированием
  (#14 (permalink)) Старый
SergeMukhin78 SergeMukhin78 вне форума
Member
 
Сообщений: 534
Сказал(а) спасибо: 17
Поблагодарили 33 раз(а) в 33 сообщениях
Регистрация: 28.03.2012
По умолчанию 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х элементов, но это ещё проще

Последний раз редактировалось SergeMukhin78; 19.12.2017 в 23:11 Причина: форматирование
Ответить с цитированием
  (#15 (permalink)) Старый
aag aag вне форума
А.А.Г.
 
Аватар для aag
 
Сообщений: 3,397
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
Адрес: Адмиралтейская)))
По умолчанию 19.12.2017, 23:12

Цитата:
Сообщение от SergeMukhin78 Посмотреть сообщение
странно, кажется это более чем просто.

как-то так:
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] чего выдаст?


импортирован с progz.ru
Ответить с цитированием
Ответ

Опции темы
Опции просмотра

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Дан список. Написать функцию, которая возвращает количество уровней сложного списка н Елизавета Яросевич Задания за деньги 0 03.11.2013 20:42
Написать функцию,которая по двум числам формирует список Marishe Lisp 1 13.10.2010 11:37
Написать программу которая разделит исходный список denis120 Lisp 3 22.05.2010 00:19
Определить рекурсию, которая возвращает список hattation Lisp 3 10.02.2010 20:21
Написать функцию, которая по списку lst и атому obj возвращает множество klava Lisp 1 22.12.2009 14:05
Нужно написать рекурсивную функцию, которая возвращает t Bender266 Lisp 6 06.05.2009 14:40
Написать функцию, которая возвращает истину Bender266 Lisp 0 06.05.2009 13:47
Написать функцию ,которая добавляет в список по одному элементу Mozgolom Lisp 2 14.05.2008 03:22
Написать функцию, которая возвращает количество вершин Adebayor Lisp 11 16.12.2007 22:58
Написать функцию LAST1, которая возвращает предпоследний элемент списка Sw1ft Lisp 9 17.05.2007 20:25
Написать функцию, которая оращает многоуровневый список super_girl Lisp 2 13.04.2007 07:25
Написать программу которая закрывает любую программу из автозагрузки без перезагрузк Anonymous C++ Builder 1 07.10.2003 11:24



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов