1

2

3

Această metodă generală de programare se aplică problemelor în care soluţia se poate reprezenta sub forma unui vector X = (x1, ..., xn)ÎS unde S = S1 x ... x Sn , unde mulţimile S1, ...,Sn

sunt mulţimi finite având |Si| = si elemente. Pentru fiecare problemă concretă sunt date anumite relaţii între componentele x1 , ... xn ale vectorului X, numite condiţii interne.

4

};,,{11,12111 maaaA

};,,{22,22212 maaaA

...

}.,,{ ,21 nnmnnn aaaA

5

nAAAS 21

),,,,( 21 nxxxX

unde ;11 Ax ;22 Ax ..., .nn Ax

6

1. Presupunem că la pasul k am calculat deja valorile:),,,( 21 kxxx

2. Selectăm din mulţimea Ak+1 valoarea xk+1:),,,,( 121 kk xxxx

3. Dacă ),,,,( 121 kk xxxx satisface condiţiileproblemei, trecem la pasul k+2.

În caz contrar revenim la pasul k şi alegem alt xk.

7

01

1

10

k := 1

k k:= + 1

a 1 ,1

a 2 ,1

a 1 2,

a 2 ,2

a 3 ,1 a 3 ,2 a 3 ,30

k k:= + 1 k k-:= 1k k:= + 1

1

A 1

A 2

A 3

0 0

8

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; { while } end { then } else PrelucrareaSolutiei;end; {Reluare}

9

1. Mulţimile A1, A2, ..., An sînt cunoscute.

3. Elementele din care sînt formate mulţimile A1, A2, ..., An şi numărul n sînt necunoscute.

2. Sînt cunoscute elementele din care sînt formate mulţimile A1, A2, ..., An, numărul n fiind necunoscut.

10

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.

11

const mmax=50; { numărul maximal de mulţimi } nmax=50; { numărul maximal de elemente }

type Natural = 0..MaxInt; Multime = array[1..nmax] of Natural;

var A : array[1..nmax] of Multime; n : 1..nmax; { numărul de mulţimi } M : array[1..nmax] of 1..mmax; { cardinalul mulţimii S[k] } X : array[1..nmax] of 1..mmax; { indicii elementelor selectate } q : Natural; k, j : integer; Indicator : boolean;

12

function PrimulElement(k : integer) : Natural;begin PrimulElement:=1;end; {PrimulElement }

13

function Continuare(k : integer) : boolean;var j : integer; suma : Natural;begin suma:=0; for j:=1 to k do suma:=suma+A[j, X[j]]; if ((k<n) and (suma<q)) or ((k=n) and (suma=q)) then Continuare:=true else Continuare:=false;end; { Continuare }

14

function ExistaSuccesor(k : integer) : boolean;begin ExistaSuccesor:=(X[k]<M[k]);end; { ExistaSuccesor }

15

procedure Reluare(k : integer); { Metoda reluarii - varianta recursiva }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 { while } end { then } else PrelucrareaSolutiei;end; { Reluare }

16

123

j

iC

12

......

3B

n

1 2 31 2 ... m...

17

},,,{1 StîngaJosDreaptaSusA },,,{2 StîngaJosDreaptaSusA

...

},,,,,,,,,,{

JosJosJosJosDreaptaDreaptaDreaptaJosDreaptaDreaptaDreaptaX

},,,{3 StîngaJosDreaptaSusA

18

Piesele iniţiale “Tren” format din 3 piese

)}6,6(),0,3(),5,3(),6,3{(1 A

19

)}6,6(),0,3(),5,3{(2 A

)}0,3(),5,3{(3 A

20