Логическое программирование

       

Олимпиадная задача


 Международная олимпиада по математике, 1963 год.

Ученики A,B,C,D и E  участвовали в одном конкурсе. Пытаясь угадать результаты соревнований, некто предполагал, что получится последовательность A,B,C,D,E. Но оказалось, что он не указал верно ни место какого-либо из участников и никакой пары следующей непосредственно друг за другом учеников. Некто другой, предполагая результат D,A,E,C,B, угадал правильно места двух учеников, а также две пары (непосредственно следующих друг за другом учеников).

Каков был на самом деле результат конкурса?.

% правильная расстановка участников (представленных в виде  место-имя)

rezult:-

    inicial(M1,M2,M3,M4,M5,[1,2,3,4,5]),

    pos([M1-a,M2-b,M3-c,M4-d,M5-e],0),

    para([M1-a,M2-b,M3-c,M4-d,M5-e],0),

    pos([M4-d,M1-a,M5-e,M3-c,M2-b],2),

    para([M4-d,M1-a,M5-e,M3-c,M2-b],2),

    write(M1-a/M2-b/M3-c/M4-d/M5-e).

% инициализация переменных элементами списка

inicial(X1,X2,X3,X4,X5,L):-



                 member(X1,L),

                 select(L,X1,S2),

                 member(X2,S2),

                 select(S2,X2,S3),

                 member(X3,S3),

                 select(S3,X3,S4),

                 member(X4,S4),

                 select(S4,X4,[X5]).

% N - количество правильных мест элементов в списке L

pos(L,N):-

     pos(L,N,0,1).

pos(_,N,N,6).

pos(L,N,S,I):-

     I<6,

     nth1(I,L,I-_),

     S1 is S+1,

     I1 is I+1,

     pos(L,N,S1,I1).

pos(L,N,S,I):-

     I<6,

     nth1(I,L,J-_),

     I=\=J,

     I1 is I+1,

     pos(L,N,S,I1).

% N - количество правильных пар непосредственно следующих друг за

% другом элементов в списке L

para(L,N):-   para(L,N,0,1).

para(_,N,N,5).

para(L,N,S,I):-

    I<5,

    nth1(I,L,A1-_),

    I1 is I+1,

    nth1(I1,L,A2-_),

    A2 =:= A1+1,

    S1 is S+1,

    para(L,N,S1,I1).

para(L,N,S,I):-

    I<5,

    nth1(I,L,A1-_),

    I1 is I+1,

    nth1(I1,L,A2-_),

    A2 =\= A1+1,

    para(L,N,S,I1).

        

?- rezult.

3 - a / 5 - b / 4 - c / 2 - d / 1 - e

Yes

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

А. Дж. Перлис, первый лауреат премии Тьюринга, 1966 год



Содержание раздела