Влюбленные юноши и девушки (Turbo и SWI Prolog)

      Комментарии к записи Влюбленные юноши и девушки (Turbo и SWI Prolog) отключены

В этой теме 6 ответов, 3 участника, последнее обновление  Васильев Владимир Сергеевич 7 мес., 1 неделя назад.

  • Автор
    Сообщения
  • #2419

    PROger4ever
    Участник

    Здравствуйте.
    Помогите, пожалуйста, решить задачу на языке программирования Turbo-Prolog:

    Трое юношей: Коля, Дима и Юра влюблены в трех девушек: Аню, Лену, Вику. Но эта любовь без взаимности. Коля любит девушку, влюбленную в юношу, который любит Лену. Дима любит девушку, влюбленную в юношу, который любит Вику. Лена не любит Юру.

    Пока есть такой код, получаю переполнение стека:

    PREDICATES
    male(string) /*Парни*/
    female(string) /*Девушки*/
    love(string,string)
    sol(string, string, string, string, string, string) /*решение*/
    print.
    
    CLAUSES
    /*заполняем людей*/
    male("Kolya").
    male("Dima").
    male("Yura").
    female("Anya").
    female("Lena").
    female("Vika").
    
    love(X, Y):- male(X), female(Y).
    love(Y, X):- male(X), female(Y).
    
    love("Kolya", Y):-love(Y, X), love(X, "Lena").
    love("Dima", Y):-love(Y, X), love(X, "Vika").
    love("Lena", X):- male(X), not (X="Yura").
    
    sol(X1, X2, X3, Y1, Y2, Y3):-
    male(X1), male(X2), male(X3),
    female(Y1), female(Y2), female(Y3),
    love(X1, Y1),
    not(love(Y1,X1)),
    love(X2, Y2),
    not(love(Y2,X2)),
    love(X3, Y3),
    not(love(Y3,X3)),
    /*Каждый человек должен быть только один раз*/
    X1<>X2,
    X1<>X3,
    X2<>X3,
    Y1<>Y2,
    Y1<>Y3,
    Y2<>Y3.
    
    /*Печать результатов.*/
    print:- sol(X1, X2, X3, Y1, Y2, Y3),
    write(X1, " - ", Y1, ". ",
    X2, " - ", Y2, ". ",
    X3, " - ", Y3, ". ").

    Не знаю как задать отношение “любит” в терминах функционального программирования.

    Что я делаю не так? Как подойти к решению этой задачи?
    Заранее большое спасибо.

  • #2421

    Вы не оформили исходный в соответствии с соглашением о кодировании, поэтому Ваш код тяжело читать (все эти переменные X1, Y1, … мало о чем мне говорят). Поэтому я напишу новый код на SWI-Prolog, а Вы уже самостоятельно перепишите его на Turbo Prolog (по возможности результат выложите на форум).

    Не понятен вопрос в задаче, т.е. что именно требуется решить или доказать? — догадываюсь, что надо выяснить кто кого любит. Тогда нам для начала надо задать информацию о мальчиках и девочках при помощи фактов пролога:

    male(kolya).
    male(dima).
    male(yura).
    
    female(anya).
    female(lena).
    female(vika).

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

    solve_love_problem(Solution):-
      % решение должно представлять собой шесть пар, показывающих кто кого любит
      Solution = [
        love(kolya, KolyaGirl),
        love(dima, DimaGirl),
        love(yura, YuraGirl),
        
        love(anya, AnyaBoy),
        love(lena, LenaBoy),
        love(vika, VikaBoy)
      ],
      
      % генерация всех возможных вариантов
      female(KolyaGirl), female(DimaGirl), female(YuraGirl),
      male(AnyaBoy), male(LenaBoy), male(VikaBoy).

    Если мы запустим такой код, то на экране получим следующее (приведен фрагмент):

    ?- solve_love_problem(X).
    X = [love(kolya, anya), love(dima, anya), love(yura, anya), love(anya, kolya), love(lena, kolya), love(vika, kolya)] ;
    X = [love(kolya, anya), love(dima, anya), love(yura, anya), love(anya, kolya), love(lena, kolya), love(vika, dima)] ;
    X = [love(kolya, anya), love(dima, anya), love(yura, anya), love(anya, kolya), love(lena, kolya), love(vika, yura)] ;

    В первой строке видно, что пролог перебирает вариант, когда все мальчики любят Аню и считает его верным (ведь мы еще не задали никаких ограничений). В коде программы который вы приводили исключались повторы имен, я делаю это с помощью функции unique, для этого после генерации вариантов надо добавить следующее:

    Girls = [KolyaGirl, DimaGirl, YuraGirl],
    Boys = [AnyaBoy, LenaBoy, VikaBoy],
      
    unique(Girls), unique(Boys).

    Мы помещаем все переменные, соответствующие девушкам и юношам в списки и требуем уникальность их элементов. Теперь после запуска программы мы увидим, что все переменные в решении инициализированы уникальным именем (приведен фрагмент):

    ?- solve_love_problem(X).
    X = [love(kolya, anya), love(dima, lena), love(yura, vika), love(anya, kolya), love(lena, dima), love(vika, yura)] ;
    X = [love(kolya, anya), love(dima, lena), love(yura, vika), love(anya, kolya), love(lena, yura), love(vika, dima)] ;

  • #2422

    Теперь мы видим, что пролог считает правильным решение, когда Коля любит Аню, а Аня — Колю, однако в условии задачи говорится, что любовь должна быть без взаимности. Добавить такое ограничение можно следующим образом:

    \+ (
        member(love(Boy, Girl), Solution), 
        member(love(Girl, Boy), Solution)
      ).

    Тут мы требуем, чтобы в решении не было двух таких пар, в которых мальчик и девочка любят друг друга. При этом используется функция member для выбора элемента из списка. В данном случае, первый вызов member пытается инициализировать переменные Boy и Girl, всеми вариантами, содержащимися в списке Solution, а второй вызов member проверяет взаимность отношения. Чтобы переписать этот фрагмент на Turbo Prolog — фрагмент проверяющий взаимность надо будет поместить в отдельный предикат, а вместо оператора \+ использовать NOT.

    Теперь при запуске на экране мы увидим следующие варианты решения (фрагмент):

    ?- solve_love_problem(X).
    X = [love(kolya, anya), love(dima, lena), love(yura, vika), love(anya, dima), love(lena, yura), love(vika, kolya)] ;
    X = [love(kolya, anya), love(dima, lena), love(yura, vika), love(anya, yura), love(lena, kolya), love(vika, dima)] ;

  • #2423

    Остается лишь добавить логических условий о том, кто кого любит чтобы в задаче остался лишь один вариант решения:

      % Коля любит девушку, влюбленную в юношу, который любит Лену.
      member(love(BoyLoveLena, lena), Solution), 
      member(love(GirlLoveBoyLoveLena, BoyLoveLena), Solution), 
      member(love(kolya, GirlLoveBoyLoveLena), Solution), 
      
      % Дима любит девушку, влюбленную в юношу, который любит Вику.
      member(love(BoyLoveVika, vika), Solution), 
      member(love(GirlLoveBoyLoveVika, BoyLoveVika), Solution),
      member(love(dima, GirlLoveBoyLoveVika), Solution),
      
      \+ member(love(lena, yura), Solution).

    Чтобы на языке Prolog написать, что «Коля любит девушку, влюбленную в юношу, который любит Лену», мы должны сначала найти в варианте решения юношу, который любит Лену, затем аналогичным образом найти девушку, которая любит его, и наконец, при помощи все того же предиката member задать ограничение — потребовать чтобы в решении Коля любил именно эту девушку:

    Вложения:
  • #2430

    PROger4ever
    Участник

    Спасибо большое Владимиру за решение задачи и написание на двух диалектах.

    domains
    	love_d=love(string, string)
    	love_list_d=love_d*
    	string_list_d=string*
    predicates
    	nondeterm male(string) % мальчики
    	nondeterm female(string) % девочки
    
    	% Решение задачи
    	nondeterm solve_love_problem(love_list_d)
    	nondeterm printPairs(love_list_d)
    	nondeterm printPair(love_d)
    	print
    
    	unique(string_list_d)
    
    	not_reciprocity(love_list_d)
    
    	nondeterm member(love_d, love_list_d)
    	nondeterm member(string, string_list_d).
    
    clauses
    	male("Kolya").
    	male("Dima").
    	male("Yura").
    
    	female("Anya").
    	female("Lena").
    	female("Vika").
    
    	not_reciprocity(Solution):-
    		member(love(Boy, Girl), Solution), 
    		member(love(Girl, Boy), Solution), !, fail; !.
    
    	solve_love_problem(Solution):-
    		% переменные для девушек парней
    		female(KolyaGirl), female(DimaGirl), female(YuraGirl),
    		% переменные для парней девушек
    		male(AnyaBoy), male(LenaBoy), male(VikaBoy),
    
    		/* задаём пары, где первый элемент - парень/девушка,
    		а второй - искомая перемнная.*/
    		Solution = [
    			love("Kolya", KolyaGirl),
    			love("Dima", DimaGirl),
    			love("Yura", YuraGirl),
    
    			love("Anya", AnyaBoy),
    			love("Lena", LenaBoy),
    			love("Vika", VikaBoy)
    		],
    		% генерация всех возможных вариантов
    		Girls = [KolyaGirl, DimaGirl, YuraGirl],
    		Boys = [AnyaBoy, LenaBoy, VikaBoy],
    
    		% не даём любить нескольким одну и ту же девушку/парня.
    		unique(Girls), unique(Boys),
    
    		% оставляем только не взаимные варианты
    		not_reciprocity(Solution),
    
    		% Добавляем условия.
    		% Коля любит девушку, влюбленную в юношу, который любит Лену.
    		member(love(BoyLoveLena, "Lena"), Solution), 
    		member(love(GirlLoveBoyLoveLena, BoyLoveLena), Solution), 
    		member(love("Kolya", GirlLoveBoyLoveLena), Solution), 
    
    		% Дима любит девушку, влюбленную в юношу, который любит Вику.
    		member(love(BoyLoveVika, "Vika"), Solution), 
    		member(love(GirlLoveBoyLoveVika, BoyLoveVika), Solution),
    		member(love("Dima", GirlLoveBoyLoveVika), Solution),
    
    		% Лена не любит Юру.
    		NOT(member(love("Lena", "Yura"), Solution)).
    
    	unique([]):-!.
    	unique([Head|Tail]):-
    		member(Head, Tail), !, fail;
    		unique(Tail).
    
    	member(Elem, [Elem|_Tail]).
    	member(Elem, [_Head|Tail]):-
    		member(Elem, Tail).
    	
    	printPairs([]):-!.
    	printPairs([Head|Tail]):-
    		printPair(Head),
    		printPairs(Tail).
    
    	printPair(love(Human1, Human2)):-
    		write(Human1, " lybit ", Human2), nl.
    
    print:-
    	% Решаем задачу
    	solve_love_problem(X),
    	printPairs(X).

  • #3208

    krigg
    Участник

    Здравствуйте! Можно привести код на swi prolog полностью?

    • #3209

      Содержимое раздела clauses — это и есть исходный код для SWI Prolog. Различий тут почти не будет, ну можно предикат member удалить, т.к. в SWI Prolog он встроенный.

Для ответа в этой теме необходимо авторизоваться.