Олимпиадная задача
Международная олимпиада по математике, 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 год
