Metoda Reluarii
-
Upload
marina-cretu -
Category
Documents
-
view
94 -
download
1
description
Transcript of Metoda Reluarii
1
Metoda reluării
2Datele iniţiale în metoda reluării
Mulţimile:
};,,{11,12111 maaaA
};,,{22,22212 maaaA
...
}.,,{ ,21 nnmnnn aaaA
3Soluţia în metoda reluării
Spaţiul soluţiilor:
nAAAS 21
Soluţia: ),,,,( 21 nxxxX
unde ;11 Ax ;22 Ax ..., .nn Ax
4Ideia 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ţiileproblemei, trecem la pasul k+2.
În caz contrar revenim la pasul k şi alegem alt xk.
5Că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 ,1 a 3 ,2 a 3 ,30
k k:= + 1 k k-:= 1k k:= + 1
1
A 1
A 2
A 3
0 0
6Schema 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}
7 Operații
Procedura Reluare comunică cu programul apelant și subprogrameleapelante prin variabilile globale ce reprezină vectorul X și mulțimile A1, A2, ..., An.Subprogramele apelante execută următoarele operații:PrimulElement (k)- returnează primul element din mulțimile Ak ;Continuare (k)- returnează valoarea true dacă elementele înscrise în primele k componente ale vectorului X satisfac condițiile de continuare și false în caz contrar;ExistaSuccesor (k)- returnează valoarea true dacă elementul memorat în componența xk
are un succesor în mulțimea Ak și false în caz contrar. Succesor (k)- returnează succesorul elementului memorat în componența xk ;PrelucrareaSolutiei- de obicei, în această procedură soluția reținută în vectorul X este afișată la ecran.
8Clasificarea 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.
9Exemplul 1. Problema din manual
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.
10Exemplul 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;
11Function PrimulElement
function PrimulElement(k : integer) : Natural;begin PrimulElement:=1;end; {PrimulElement }
12
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
13
function ExistaSuccesor(k : integer) : boolean;begin ExistaSuccesor:=(X[k]<M[k]);end; { ExistaSuccesor }
Function ExistaSuccesor
function function Succesor (k:integer) : integer;Succesor (k:integer) : integer;beginbegin Succesor :=X[k]+1;Succesor :=X[k]+1;endend;{Succesor};{Succesor}procedureprocedure PrelucrareaSolutiei; PrelucrareaSolutiei;varvar k: integer; k: integer;beginbegin write (’Solutia:’);write (’Solutia:’);forfor k:=1 k:=1 toto n n dodo write (A[k, X[k]],’’); write (A[k, X[k]],’’); writeln;writeln; Indicator:=true;Indicator:=true;endend; {PrelucrareaSolutiei}; {PrelucrareaSolutiei}
14
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
15
123
j
iC
12
..... .
3B
n
1 2 31 2 ... m...
Exemplul 2. Labirintul
16Labirintul. Formularea matematică
Mulţimile:},,,{1 StîngaJosDreaptaSusA },,,{2 StîngaJosDreaptaSusA
...Soluţia:
},,,,,,,,,,{
JosJosJosJosDreaptaDreaptaDreaptaJosDreaptaDreaptaDreaptaX
},,,{3 StîngaJosDreaptaSusA