презентация microsoft office power point
TRANSCRIPT
![Page 1: презентация Microsoft office power point](https://reader036.vdocumente.com/reader036/viewer/2022082810/55888c98d8b42a91298b4730/html5/thumbnails/1.jpg)
Metoda reluării
Efectuat de: Bejan Mihai
![Page 2: презентация Microsoft office power point](https://reader036.vdocumente.com/reader036/viewer/2022082810/55888c98d8b42a91298b4730/html5/thumbnails/2.jpg)
Datele iniţiale în metoda reluării
Mulţimile:
};,,{11,12111 maaaA
};,,{22,22212 maaaA
...
}.,,{ ,21 nnmnnn aaaA
![Page 3: презентация Microsoft office power point](https://reader036.vdocumente.com/reader036/viewer/2022082810/55888c98d8b42a91298b4730/html5/thumbnails/3.jpg)
Soluţia în metoda reluării
Spaţiul soluţiilor:
nAAAS 21
Soluţia: ),,,,( 21 nxxxX
unde ;11 Ax ;22 Ax ..., .nn Ax
![Page 4: презентация Microsoft office power point](https://reader036.vdocumente.com/reader036/viewer/2022082810/55888c98d8b42a91298b4730/html5/thumbnails/4.jpg)
Ideea metodei reluării
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ţiile
problemei, trecem la pasul k+2.
În caz contrar revenim la pasul k şi alegem alt xk.
![Page 5: презентация Microsoft office power point](https://reader036.vdocumente.com/reader036/viewer/2022082810/55888c98d8b42a91298b4730/html5/thumbnails/5.jpg)
Căutarea soluţiei prin metoda reluării
01
1
10
k := 1
k k:= + 1
a 1 ,1
a 2 ,1
a 1 2,
a 2 ,2
a 3 ,1a 3 ,2 a 3 ,30
k k:= + 1 k k-:= 1k k:= + 1
1
A 1
A 2
A 3
0 0
![Page 6: презентация Microsoft office power point](https://reader036.vdocumente.com/reader036/viewer/2022082810/55888c98d8b42a91298b4730/html5/thumbnails/6.jpg)
Schema generală a algoritmului recursiv bazat pe metoda reluării
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}
![Page 7: презентация Microsoft office power point](https://reader036.vdocumente.com/reader036/viewer/2022082810/55888c98d8b42a91298b4730/html5/thumbnails/7.jpg)
Clasificarea problemelor
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.
![Page 8: презентация Microsoft office power point](https://reader036.vdocumente.com/reader036/viewer/2022082810/55888c98d8b42a91298b4730/html5/thumbnails/8.jpg)
Exemplu
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.
![Page 9: презентация Microsoft office power point](https://reader036.vdocumente.com/reader036/viewer/2022082810/55888c98d8b42a91298b4730/html5/thumbnails/9.jpg)
Exemplul 1. Reprezentarea datelor
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;
![Page 10: презентация Microsoft office power point](https://reader036.vdocumente.com/reader036/viewer/2022082810/55888c98d8b42a91298b4730/html5/thumbnails/10.jpg)
Function PrimulElement
function PrimulElement(k : integer) : Natural;begin PrimulElement:=1;end; {PrimulElement }
![Page 11: презентация Microsoft office power point](https://reader036.vdocumente.com/reader036/viewer/2022082810/55888c98d8b42a91298b4730/html5/thumbnails/11.jpg)
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 }
Function Continuare
![Page 12: презентация Microsoft office power point](https://reader036.vdocumente.com/reader036/viewer/2022082810/55888c98d8b42a91298b4730/html5/thumbnails/12.jpg)
function ExistaSuccesor(k : integer) : boolean;begin ExistaSuccesor:=(X[k]<M[k]);end; { ExistaSuccesor }
Function ExistaSuccesor
![Page 13: презентация Microsoft office power point](https://reader036.vdocumente.com/reader036/viewer/2022082810/55888c98d8b42a91298b4730/html5/thumbnails/13.jpg)
Anatol Gremalschi, 2004
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 }
Procedure Reluare
![Page 14: презентация Microsoft office power point](https://reader036.vdocumente.com/reader036/viewer/2022082810/55888c98d8b42a91298b4730/html5/thumbnails/14.jpg)
Anatol Gremalschi, 2004 14
Vă mulţumesc pentru atenţie !