% % 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 ...)