%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Exemplo 4.1 %% selecionado(?X, ?L, ?R) is nondet % % Verdadeiro se R é a lista L sem o elemento X. % % Veja o predicado pré-definido select/3. :- begin_tests(selecionado). test(t0, all(r(X, R) == [ r(4, [2, 6]), r(2, [4, 6]), r(6, [4, 2])])) :- selecionado(X, [4, 2, 6], R). :- end_tests(selecionado). selecionado(X, [X|XS], XS). selecionado(X, [Y|YS], [Y|R]) :- selecionado(X, YS, R). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Exemplo 4.2 %% permutacao(+L, ?P) is nondet % % Verdadeiro se P é uma permutação de L. Se P não estiver instanciado, o % predicado gera todas as permutações de L em P. % % Veja o predicado pré-definido permutation/2. :- begin_tests(permutacao). test(permutacao, all(P == [[a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, a, b], [c, b, a]])) :- permutacao([a, b, c], P). :- end_tests(permutacao). permutacao([], []). permutacao(L, [X|T]) :- select(X, L, R), permutacao(R, T). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Exemplo 4.3 %% natural(-N) is nondet % % Verdadeiro se N é um número natural. Este predicado é um gerador. A cada fez % que ele é satisfeito ele gera um número. % % Veja o predicado pré-definido between/3. % % Exemplos % ?- natural(N). % N = 0 ; % N = 1 ; % N = 2 ; % .... :- begin_tests(natural). % Pergunta: como testar um gerador infinito? % Resposta: usando corte com fail e ou ... Tente entender este teste. test(t0, all(N == [0, 1, 2, 3])) :- natural(N), (N >= 4, !, fail ; true). :- end_tests(natural). natural(0). natural(N) :- natural(N0), N is N0 + 1. %% naturalx(?N) is nondet % % Versão do predicado natural/1 que funciona com argumento instanciado ou não. :- begin_tests(naturalx). test(t0) :- naturalx(8). test(t1, fail) :- naturalx(a). test(t2, fail) :- naturalx(-1). test(t3, all(N == [0, 1, 2, 3])) :- naturalx(N), (N >= 4, !, fail; true). :- end_tests(naturalx). naturalx(N) :- nonvar(N), !, integer(N), % predicado pré-definido que é verdadeiro se N é inteiro. N > 0. naturalx(N) :- natural(N). %% nat(-N) is nondet % % Versão eficiente do predicado natural/1. :- begin_tests(nat). test(t0, all(N == [0, 1, 2, 3])) :- nat(N), ( N >= 4, !, fail; true). :- end_tests(nat). nat(N) :- nat(0, N). nat(N, N). nat(N, X) :- N1 is N + 1, nat(N1, X). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Exemplo 4.4 %% aprova(?A) is nondet % % Verdadeiro se o aluno A foi aprovado. :- begin_tests(aprovado). test(t0, all(A == [jose, andre])) :- aluno(A), aprovado(A). :- end_tests(aprovado). aprovado(A) :- faltas(A, F), F > 25, !, fail. aprovado(A) :- media(A, M), M >= 6, !. aprovado(A) :- media(A, M), exame(A, E), (M + E)/2 >= 5. aluno(jose). aluno(paulo). aluno(andre). faltas(jose, 10). faltas(paulo, 30). faltas(andre, 0). media(jose, 7). media(paulo, 8). media(andre, 4). exame(andre, 6.5). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Exemplo 4.5 %% primeiro_primo(+N, ?P) is semidet % % Verdadeiro se P é o primeiro primo maior ou igual a N. :- begin_tests(primeiro_primo). test(t0, P == 17) :- primeiro_primo(14, P). test(t0, P == 7) :- primeiro_primo(7, P). :- end_tests(primeiro_primo). primeiro_primo(N, P) :- nat(N, P), % gerar um candidado primo(P), % testa o candidado !. % interrompe o processo após achar uma solução %% primo(+X) is semidet % % Verdadeiro se X é um número primo. primo(X) :- menor_divisor(X, 2, Y), X =:= Y. %% menor_divisor(+X, +D, ?Y) is semidet % % Verdadeiro se Y é o menor divisor de X maior ou igual a D. % X é o menor divisor de X començando com X menor_divisor(X, X, X) :- !. % D é o menor divisor de X començando com D se X é divisível por D. menor_divisor(X, D, D) :- divisivel(X, D), !. % D não é divisor de X menor_divisor(X, D, Y) :- \+ divisivel(X, D), D1 is D + 1, D1 =< X, menor_divisor(X, D1, Y). %% Divisivel(+X, +Y) is semidet % % Verdadeiro se X é divisível por Y. divisivel(X, Y) :- X rem Y =:= 0. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Exemplo 4.6 %% grafo(+N, -G, -Cs) % % N é o número do grafo G. grafo(1, grafo([a, b, c, d, e], [[a,b], [b,a], [b,e], [b,d], [c,b], [d,c], [e,d], [e,c]])). grafo(2, grafo([a, b, c, d, e, f, g, h, i, j, k, l], [[b,a], [c,b], [d,c], [e,d], [f,e], [g,f], [h,g], [i,h], [j,i], [k,j], [l,k]])). :- begin_tests(caminho_hamiltoniano). test(caminho_hamiltoniano, all(C == [[a, b, e, d, c], [e, d, c, b, a]])) :- grafo(1, G), caminho_hamiltoniano(G, C). % Este teste é muito lento! %test(caminho_hamiltoniano, all(C == [[l, k, j, i, h, g, f, e, d, c, b, a]])) :- % grafo(2, G), % caminho_hamiltoniano(G, C). test(caminho_hamiltoniano2, all(C == [[a, b, e, d, c], [e, d, c, b, a]])) :- grafo(1, G), caminho_hamiltoniano2(G, C). test(caminho_hamiltoniano2, all(C == [[l, k, j, i, h, g, f, e, d, c, b, a]])) :- grafo(2, G), caminho_hamiltoniano2(G, C). :- end_tests(caminho_hamiltoniano). %% caminho_hamiltoniano(+G, ?C) is nondet % % Verdadeiro se C é um caminho hamiltoniano em G. Se C não for especificado, % o predicado encontrada todos os caminhos hamiltonianos. caminho_hamiltoniano(G, C) :- grafo(V, _) = G, permutacao(V, C), caminho(G, C). %% caminho_hamiltoniano(+G, ?C) is nondet % % Verdadeiro se C é um caminho hamiltoniano em G. Se C não for especificado, % o predicado encontrada todos os caminhos hamiltonianos. % % Versão eficiente do predicado caminho_hamiltoniano/2. caminho_hamiltoniano2(G, C) :- grafo(V, _) = G, same_length(V, C), caminho_hamiltoniano2(G, C, 1, V). %% caminho_hamiltoniano(+G, ?C, I, V) is nondet % % Verdadeiro se C é um caminho hamiltoniano em G com todos os vértices em V % dispostos a partir do índice I (considerando que o primeiro elemento de C % está no índice 1). caminho_hamiltoniano2(_, _, _, []). caminho_hamiltoniano2(G, C, I, V) :- select(U, V, R), nth1(I, C, U), subcaminho(C, I, Sub), caminho(G, Sub), I1 is I + 1, caminho_hamiltoniano2(G, C, I1, R). %% subcaminho(+C, +T, -Sub) is semidet % % Verdadeiro se Sub é o subcaminho no início de C de tamanho T. subcaminho(C, T, Sub) :- length(Sub, T), prefix(Sub, C). %% caminho(+G, C) is semidet % % Verdadeiro se C é um caminho em G. caminho(G, [U]) :- vertice(G, U), !. caminho(G, [U, V | R]) :- aresta(G, U, V), !, caminho(G, [V | R]). %% aresta(+G, ?U, ?W) is nondet % % Verdadeiro se (U, W) é uma aresta de G. aresta(grafo(_, A), U, W) :- member([U, W], A). %% aresta(+G, ?U) is nondet % % Verdadeiro se U é um vértice de G. vertice(grafo(V, _), U) :- member(U, V). % vim: set ft=prolog spell spelllang=pt_br: