SUMA A 15.000 NUMERE
<![CDATA[
/************************************
Problema:
Sa se insumeze toate numerele date ca fapte intr-o baza interna, de forma:
nr(real).
Problema este interesanta pentru valori mari, de exemplu 15.000 de fapte in
baza, caz in care o solutie de tip findall esueaza.
Dificultatea consta in transmiterea unei sume partiale odata cu parcurgerea
solutiilor alternative nr(X), dat fiind ca atingerea unei solutii ulterioare
presupune backtracking, iar in acel moment orice informatie calculata
prin unificarea unor variabile se pierde prin insasi natura mecanismului
de backtracking.
Solutie:
- Se salveaza baza continand faptele
- Se verifica daca exista un fapt nr(X), se insumeaza intr-o variabila intermediara,
faptul se sterge din baza, apoi se apeleaza recursiv; astfel, reusim sa parcurgem
toate faptele din baza fara sa apelam la backtracking.
- La sfarsit, se consulta baza salvata la primul fapt, pentru a restaura faptele.
Pentru valori mici, putem testa corectitudinea solutiei suma2 comparativ cu
solutia suma1, printr-un goal de genul:
genereaza(1000), suma1(S1), suma2(S2)
Dat fiind ca numerele sunt parcurse in aceeasi ordine in ambele solutii,
se poate adauga si S1 = S2, altfel ar putea exista erori:
genereaza(1000), suma1(S1), suma2(S2), S1 = S2
Paul Mateescu, grupa 309-Informatica, an III-ZI, 2009.
Facultatea de Matematica si Informatica, Universitatea Spiru Haret Bucuresti.
*************************************/
domains
rl = real*
predicates
genereaza(real) % genereaza faptele nr(real) in baza
suma1(real) %prin findall
suma1(rl, real, real)
suma2(real) % prin retract de nr(real) pe masura ce este insumat
suma2(real, real)
database - numere
nr(real)
clauses
% Genereaza N fapte de forma nr(real) in baza de date "numere"
genereaza(N) :-
N > 0,
random(R),
R1 = 1000* R,
assertz(nr(R1)),
N1 = N - 1,
!,
genereaza(N1).
genereaza(_).
% Insumeaza toti X-ii pentru care nr(X). Esueaza pentru valori mari,
% de exemplu 15000!
suma1(S) :-
findall(X, nr(X), L),
suma1(L, 0, S).
suma1([], S, S) :- !.
suma1([H|T], SI, S) :-
SIA = SI + H,
!,
suma1(T, SIA, S).
% Insumeaza toti X-ii pentru care nr(X), evitand backtracking-ul:
suma2(S) :-
save("DBNUMERE.TXT", numere),
suma2(0, S),
consult("DBNUMERE.TXT", numere).
suma2(SI, S) :-
nr(X),
SIA = SI + X,
retract(nr(X)),
!,
suma2(SIA, S).
suma2(S, S).
]]>