198 lines
6.5 KiB
Prolog
198 lines
6.5 KiB
Prolog
%
|
|
% PROJET DE LOGIQUE : Monsieur Somme et Madame Produit.
|
|
% Magistère Stic, Module Logique. 2002-2003.
|
|
% Cours de R. Treinen et H.Comon
|
|
%
|
|
%-------------------------------------------------------------------%
|
|
%
|
|
% Projet de Glenn ROLLAND
|
|
%
|
|
% pour plus de détails au sujet du raisonnement, voir le
|
|
% fichier README.enonce
|
|
%
|
|
% pour la compilation et execution du projet, veuillez
|
|
% vous référer au fichier README.compilation
|
|
%
|
|
%*******************************************************************%
|
|
% QUELQUES OUTILS POUR PLUS TARD...
|
|
%*******************************************************************%
|
|
|
|
% racine(N,P) est vrai si P est la racine du premier carré
|
|
% suppérieur à N.
|
|
racine(N,S) :- racine_aux(N, 0, 1, 1, S).
|
|
racine_aux(N, Sqrt, Pair, Somme, Ans) :-
|
|
Somme =< N,
|
|
Sqrt1 is Sqrt + 1,
|
|
Pair1 is Pair + 2,
|
|
Somme1 is Somme + Pair,
|
|
racine_aux(N, Sqrt1, Pair1, Somme1, Ans).
|
|
racine_aux(N, Sqrt, Pair, Somme, Sqrt) :- Somme > N.
|
|
|
|
% est_premier(N) est vrai si N est un nombre premier.
|
|
est_premier(2).
|
|
est_premier(N):-
|
|
N > 1,
|
|
racine(N,J),
|
|
U is J+1,
|
|
est_premier(2, U, N).
|
|
|
|
est_premier(I, I, _):-!.
|
|
est_premier(I, J, N):-
|
|
N mod I > 0,
|
|
I1 is I + 1,
|
|
est_premier(I1, J, N).
|
|
|
|
% est_diviseur(Nombre,Diviseur) est vrai si Diviseur divise Nombre.
|
|
est_diviseur(Nombre,Nombre).
|
|
est_diviseur(Nombre,1) :- Nombre > 0.
|
|
est_diviseur(Nombre,Diviseur) :- Nombre > 0,
|
|
Diviseur>0,
|
|
NNb is Nombre - Diviseur,
|
|
est_diviseur(NNb,Diviseur).
|
|
|
|
%*******************************************************************%
|
|
% FONCTIONS PERMETTANT D'ENUMERER LES NOMBRES QUI
|
|
% ONT LA MEME SOMME
|
|
%*******************************************************************%
|
|
|
|
asc_somme_liste_aux([],[],Debut,Final) :-
|
|
Debut > (Final // 2).
|
|
% On s'arrete si l'on dépasse la borne (Final / 2) car sinon
|
|
% on retrouvera la même liste de chiffres chiffres que AList,
|
|
% à l'envers dans la liste DList
|
|
|
|
asc_somme_liste_aux([Debut|AList],[Diff|DList],Debut,Final) :-
|
|
Debut =< (Final // 2),
|
|
Diff is Final - Debut,
|
|
Mid is Debut+1,
|
|
asc_somme_liste_aux(AList,DList,Mid,Final),!.
|
|
|
|
% On énumère les nombres de facon décroissante
|
|
somme_liste(Somme,AList,DList) :-
|
|
asc_somme_liste_aux(AList,DList,2,Somme).
|
|
|
|
|
|
% AList et DList contiennent à la fin les listes tel que si on
|
|
% prend le ieme élèment de AList et le ieme élément de DList,
|
|
% alors leur somme est Somme
|
|
|
|
%*******************************************************************%
|
|
% FONCTIONS PERMETTANT D ENUMERER LES NOMBRES QUI
|
|
% ONT LE MEME PRODUIT
|
|
%*******************************************************************%
|
|
|
|
|
|
|
|
prod_liste(Final,AList,DList) :-
|
|
prod_liste_aux(AList,DList,2,Final).
|
|
prod_liste_aux([],[],Debut,Final) :-
|
|
racine(Final,V), Debut > V.
|
|
|
|
prod_liste_aux(AList,DList,Debut,Final) :-
|
|
racine(Final,V), Debut =< V,
|
|
(\+ est_diviseur(Final,Debut)),
|
|
Suivant is Debut+1,
|
|
prod_liste_aux(AList,DList,Suivant,Final).
|
|
|
|
prod_liste_aux([A|AList],[D|DList],Debut,Final) :-
|
|
racine(Final,V), Debut =< V,
|
|
est_diviseur(Final,Debut),
|
|
A is Debut, D is (Final // A),
|
|
Suivant is Debut+1,
|
|
prod_liste_aux(AList,DList,Suivant,Final),!.
|
|
|
|
|
|
%*******************************************************************%
|
|
% GENERATION DE LA LISTE DES PRODUITS
|
|
%*******************************************************************%
|
|
|
|
% gen_prod_liste(A,D,P) est vrai lorsque P[i]=A[i]*D[i] pour tout i.
|
|
|
|
gen_prod_liste([],[],[]).
|
|
gen_prod_liste([A|AList],[D|DList],[P|ProdList]) :- P is A*D,
|
|
gen_prod_liste(AList,DList,ProdList).
|
|
|
|
%*******************************************************************%
|
|
% GENERATION DE LA LISTE DES SOMMES
|
|
%*******************************************************************%
|
|
|
|
% gen_somme_liste(A,D,S) est vrai lorsque S[i]=A[i]+D[i] pour tout i.
|
|
|
|
gen_somme_liste([],[],[]).
|
|
gen_somme_liste([A|AList],[D|DList],[S|SommeList]) :- S is A + D,
|
|
gen_somme_liste(AList,DList,SommeList).
|
|
|
|
%*******************************************************************%
|
|
% VERIFICATIONS SUR LES PRODUITS
|
|
%*******************************************************************%
|
|
|
|
prod_non_unique(P) :- prod_liste(P,PL1,PL2),
|
|
length(PL1,Longueur1),
|
|
Longueur1 > 1.
|
|
|
|
tous_non_uniques([]).
|
|
tous_non_uniques([P|ListP]) :- prod_non_unique(P),
|
|
tous_non_uniques(ListP).
|
|
|
|
%******************************************************************%
|
|
% VERIFICATION QU'UNE VALEUR DE SOMME PEUT CORRESPONDRE
|
|
% A UNE SOLUTION
|
|
%******************************************************************%
|
|
|
|
% les sommes paires ne sont pas validees
|
|
valide_somme(S,[]) :- M is S mod 2, M = 0,fail.
|
|
|
|
% les sommes impaires égales à un premier plus 2 ne sont pas
|
|
% validees
|
|
valide_somme(S,[]) :- M is S mod 2, M=1,
|
|
U is S-2, est_premier(U), fail.
|
|
% pour le reste des sommes, on calcule.
|
|
valide_somme(S,ProdList) :- M is S mod 2, M=1,
|
|
somme_liste(S,S1,S2),
|
|
gen_prod_liste(S1,S2,ProdList),
|
|
tous_non_uniques(ProdList).
|
|
% TROP LENT
|
|
enlever_non_valide([],[]).
|
|
enlever_non_valide([S|SList],ResultList) :-
|
|
(\+ valide_somme(S,ProdList)),
|
|
enlever_non_valide(SList,ResultList),!.
|
|
enlever_non_valide([S|SList],[R|ResultList]) :-
|
|
valide_somme(S,ProdList),
|
|
R is S,
|
|
enlever_non_valide(SList,ResultList),!.
|
|
|
|
%******************************************************************%
|
|
% VERIFICATION QU'UN PRODUIT NE CORRESPOND QU'A 1 SEULE
|
|
% DECOMPOSITION (EN SOMME) EXISTANTE (car dans ce cas P
|
|
% connait ces 2 nombres)
|
|
%*******************************************************************%
|
|
|
|
% TROP LENT
|
|
somme_unique_for_prod(P) :- prod_liste(P,P1,P2),
|
|
gen_somme_liste(P1,P2,SommeList),
|
|
enlever_non_valide(SommeList,FiltreeSommes),
|
|
length(FiltreeSommes,Longueur),
|
|
Longueur<2.
|
|
|
|
somme_unique_for_prod_liste([],[]).
|
|
somme_unique_for_prod_liste([P|ProdList], ResultList) :-
|
|
(\+ somme_unique_for_prod(P)),
|
|
somme_unique_for_prod_liste(ProdList,ResultList).
|
|
somme_unique_for_prod_liste([P|ProdList],[R|ResultList]) :-
|
|
somme_unique_for_prod(P),
|
|
R is P,
|
|
somme_unique_for_prod_liste(ProdList,ResultList).
|
|
|
|
somme_produit(S,R) :- valide_somme(S,ProdList),
|
|
somme_unique_for_prod_liste(ProdList,[R|RList]),
|
|
length(RList,L),
|
|
L = 0.
|
|
|
|
|
|
/************************************************************
|
|
enumeration
|
|
***********************************************************/
|
|
|
|
% fonction qui énumere les solutions (X,Y) telles que X+Y < S
|
|
% enumere(S ...)
|