TORODII DARIA, CLASA XI B

Metoda Reluării

METODA RELUĂRII – PRESUPUNE CĂ SOLUŢIA PROBLEMEI PE CARE TREBUIE SĂ O

REZOLVĂM POATE FI REPREZENTATĂ PRINTR-UN VECTOR:

X=(X1, X2, …, X K , …, XN) .FIECARE COMPONEN TĂ A VECTORULUI X

POATE LUA VALORI DINTR-O ANUMITĂ MULŢIME A K . SE CONSIDERĂ CĂ ELEMENTELE

MULŢIMII A K SUNT ORDONATE CONFORM UNUI CRITERIU BINE STABILIT.

Ce reprezintă metoda reluării ?

Căutarea soluţiei prin metoda reluării

G

E

N

E

R

A

L

I

T

Ă

Ţ

I

Schema generală

Procedure Reluare (k:integer);Begin if k<=n then begin X[k]:=PrimulElement(k); if Continuare(k) then Reluare(k+1); while ExistaSuccesor(k) do Begin X[k]:=Succesor(k); if Continuare(k) then Reluare(k+1) end; end else PrelucrareaSolutiei;End;

Metoda Trierii Metoda Reluării

Complexitatea algoritmului: O( )

Timpul cerut de algoritmul respectiv este foarte mare;

Soluţionează aceleaşi probleme

Complexitatea algoritmului: O( )

Timpul cerut de algoritmul respectiv este mai mic;

Soluţionează aceleaşi probleme

Diferenţa dintre metodele trierii şi reluării

Exemple de probleme

Se consideră mulţimile A1, A2, …, An fiecare mulţime fiind formată din mk numere naturale. Selectaţi din fiecare mulţime cîte un număr în aşa mod încît suma lor să fie egală cu q.

Se consideră mulţimea B={b1, b2, …, bn} formată în primele n litere ale alfabetului latin. Elaboraţi un program care generează toate submulţimile Bi formate exact din q litere.

Elaboraţi un program care afişează la ecran toate modurile de a descompune un număr natural în sumă de k numere naturale distincte.

HTTP: / / INFO.MCIP.RO/?T=BACKHTTP: / /SOFTWARE.UCV.RO/~CSTOICA/TP/

BACKTRACKING.PDF

Link-uri utile