Форум программистов, компьютерный форум, киберфорум
Наши страницы
Prolog
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
kib
0 / 0 / 1
Регистрация: 25.09.2010
Сообщений: 22
1

Работа со списками в Prolog (задача на отрезки; есть наработки)

23.03.2014, 10:42. Просмотров 766. Ответов 5
Метки нет (Все метки)

Здравствуйте!
Изучаю пролог недавно, и передо мной встала следующая задача: упорядочить список отрезков (O1(X1_1,X2_1),O2(X2_1,X2_2),..,ON(X1_N,X2_N) и найти отрезки с с минимальной и максимальной длиной. Подумал решать так: вычислять длину отрезков, затем сортировать эти длины методом пузырька, для минимума выводить "голову" полученного списка, затем делать инверсию списка и для максимума вывести "голову". Правила работают, например при запросе ?-min_max([4,1,6,3,9,7],Min,Max). Ответ: Min = 1, Max = 9. (SWI-Prolog)

Вопрос следующий: как задать список отрезков? Ведь число неограничено и пользователь может вводить сколько пожелает. И как связать это с правилами, которые я уже написал (чтобы вычислялялись длины->образовывался список для дальнейшей сортировки)?
Форум просмотрел, не смог разобраться самостоятельно.

Заранее спасибо!

Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
%как задать отрезок?
/*может как список с подсписками?*/
 
%длина отрезка
leng([X1,X2],Res):- Res is abs(X2-X1).
 
%сортировка длин отрезков (пузырьком)
reverse([X,Y|L],[Y,X|L]):-X>Y.
reverse([X|L],[X|LRes]):-reverse(L,LRes).
 
bubble(L,Res):-reverse(L,Res1), !, bubble(Res1,Res).
bubble(L,L).
 
%инверсия списка
inv(L1, L2):-invert(L1, [], L2).
invert([ ], L2, L2).
invert([H|T], L, L2):- invert(T, [H|L], L2).
 
%нахождение отрезков минимальной и максимальной длин
min_max(L,Min,Max):-bubble(L,Z),Z = [H|_],Min is H,inv(Z,[H2|_]),Max is H2.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.03.2014, 10:42
Ответы с готовыми решениями:

Задача со списками (SWI-Prolog)
Доброго времени суток, Есть 2 задачи на списки: 1. Разделить список на две...

Prolog. Работа со списками
У кого-нибудь есть какие-то идеи насчет этой задачи? :) Или хотя бы натолкните,...

Работа со списками (Turbo Prolog 2.0)
Срочно нужна помощь с задачкой по прологу. Зачет на носу. все задачи решила, а...

Работа со списками в Visual Prolog 7.2
Доброго времени. После пары суток бесплодного поиска, обращаюсь к вам за...

Работа со списками в Turbo Prolog
Доброго времени суток тем кто посетил этот топ. Дело собственно вот в чем: ...

5
rrrFer
Заблокирован
23.03.2014, 12:31 2
в swi есть готовые функции сортировки.
в функцию predsort (как-то так называется, могу ошибатьяс) можно передать функцию сравнения отрезков. Можно даже лямбду.

Соответственно, тебе надо вызвать предсорт, а затем получить первый и последний элементы (это и будут отрезки наибольшей и наименьшей длины). Чтобы получить последний - используй встроенный last. Короче задача решается полностью стандартными функциями.

Вопрос следующий: как задать список отрезков? Ведь число неограничено и пользователь может вводить сколько пожелает
запрашивай у юзера терм - это ведь язык с динамической типизацией. Юзер введет
[(0,0,1,3), (10, 7,4,3)] - значит будет 2 отрезка, и пролог об этом догадается сам.
Не знаю как вам, а мне по запросу "Ввод терма в SWI Prolog" вывалился нормальный результат.
1
kib
0 / 0 / 1
Регистрация: 25.09.2010
Сообщений: 22
23.03.2014, 13:00  [ТС] 3
Цитата Сообщение от rrrFer Посмотреть сообщение
в swi есть готовые функции сортировки.
в функцию predsort (как-то так называется, могу ошибатьяс) можно передать функцию сравнения отрезков. Можно даже лямбду.

Соответственно, тебе надо вызвать предсорт, а затем получить первый и последний элементы (это и будут отрезки наибольшей и наименьшей длины). Чтобы получить последний - используй встроенный last. Короче задача решается полностью стандартными функциями.


запрашивай у юзера терм - это ведь язык с динамической типизацией. Юзер введет
[(0,0,1,3), (10, 7,4,3)] - значит будет 2 отрезка, и пролог об этом догадается сам.
Не знаю как вам, а мне по запросу "Ввод терма в SWI Prolog" вывалился нормальный результат.
Благодарю за быстрый ответ!

По поводу стандартных функций - в задании их желательно не использовать, а описать самостоятельно. По поводу встроенных функций сортировки не знал еще, спасибо, посмотрю.

Я все равно не могу понять, как решить вопрос, объясните, если несложно.
?-[(0,0,1,3), (10, 7,4,3)]. Здесь вы имеете ввиду координаты по X и Y? Я думаю, в задании подразумеваются отрезки на прямой, а не на плоскости, поэтому я описал правило вычисления длины только по координате конца отрезка (X2) и начала (X1).
Перепишем правило нахождения минимальной и максимальной длин. Добавив length([X1,X2],L), Пролог ведь поймет, что в список L запишутся длины отрезков для дальнейшей сортировки? Т.е. если я задам в запросе два отрезка с координатами (-2;-7) и (-1;0), то сначала создастся список L = [5,1], а затем отсортируется в Z = [1,5]?
Prolog
1
2
%нахождение отрезков минимальной и максимальной длин
min_max(L,Min,Max):-length([X1,X2],L),bubble(L,Z),Z = [H|_],Min is H,inv(Z,[H2|_]),Max is H2.
Как все же задать правило ввода списка отрезков? Как в последнем правиле min_max будет формироваться список? Если нетрудно, подскажите.
0
Грымзик
2481 / 1457 / 35
Регистрация: 14.09.2009
Сообщений: 2,742
23.03.2014, 23:34 4
У Вас в задании конкретно сказано, что нужно как-то вводить список, а не задавать в самом запросе? Не нужно генерить список длин, просто надо на месте использовать предикат length. Сортировка реализована не правильно, вот например вставкой
Prolog
1
2
3
4
5
6
insert(X,[],[X]).
insert(X,[H|Tail],[X,H|Tail]):-length(X,Len1),lenght(H,Len2),Len=<Len2,!.
insert(X,[H|Tail],[H|Tail1]):-insert(X,Tail,Tail1).
 
sort([],[]).
sort([H|Tail],Ans):-sort(Tail,Tail1),insert(H,Tail1,Ans).
1
kib
0 / 0 / 1
Регистрация: 25.09.2010
Сообщений: 22
24.03.2014, 00:12  [ТС] 5
Грымзик, конкретно не сказано, но удалось решить задачу с помощью read. Сегодня/завтра выложу окончательное решение.
И больше спасибо за пример сортировки со вставкой! Только вопрос, в чем неправильность реализации сортировки пузырьком?
0
Грымзик
2481 / 1457 / 35
Регистрация: 14.09.2009
Сообщений: 2,742
24.03.2014, 11:21 6
По поводу пузырька. Я из-за названия предиката reverse просто вчитываться в него не стала. Вообще такая сортировка конечно будет работать, но порядок сравнения странный получится. И главное, что тут время работы будет O(http://www.cyberforum.ru/cgi-bin/latex.cgi?{n}^{3}), а не O(http://www.cyberforum.ru/cgi-bin/latex.cgi?{n}^{2})
0
24.03.2014, 11:21
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.03.2014, 11:21

Задачка со списками Prolog
Помогите, пожалуйста решить задачку! Есть список, например нужно написать...

Помогите со списками (Visual Prolog)
Доброго времени суток. Если кто может, помогите, пожалуйста реализовать: 1)...

В Turbo-Prolog есть возможность описать Goal. Как это реализовано в SWI-Prolog
Здравствуйте. в Turbo-Prolog есть возможность описать Goal: Goal ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru