Referat Alimanescu
Mai jos puteti citi fragmente din
Referat Alimanescu si de asemenea puteti face
Download Referat AlimanescuCiteste fragmente din Referat Alimanescu
ACEST PROIECT LA INFORMATICA CONSTA IN
PREZENTAREA IN LIMBAJUL DE PROGRAMARE TURBO PASCAL A UNEI PROBLEME CE
ISI PROPUNE SA EXPUNA CAT MAI MULTE DINTRE CUNOSTINTELE ACUMULATE DEA
LUNGUL CELOR 4 ANI DE LICEU.
PE LANGA NOTIUNILE DE TEORIE CE VOR FACE OBIECTUL
ACESTUIA(BACKTRACKING,RECURSIVITATE, ALOCARE DINAMICA),EXPLICAREA
APROFUNDATA A TUTUROR PASILOR ALGORITMULUI ,ATASAREA FISIERULUI CE
DEMONSTREAZA CORECTITUDINEA PROBLEMEI, VOR INCERCA SA DOVEDEASCA
PREGATIREA CAT MAI TEMEINICA A AUTOAREI.
CUPRINS
Prezentarea tehnicii Backtracking………………………..4
Notiuni despre recurisivitate………………………………7
Backtracking recursiv……………………………………...9
Alocarea dinamica…………………………………………11
4.1 Notiuni generale…………………………………….11
4.2 Lista liniara dublu
inlantuita……………………....12
4.2.1
Creare................................................................13
4.2.2 Adaugare la
dreapta.........................................13
4.2.3 Adaugare in interiorul
listei.............................14
4.2.4 Stergere in ineteriorul
listei..............................14
4.2.5 Listare de la stanga la
dreapta.........................15
5)Enuntul problemeiâ€â€Problema mixta……………..............16
6)Explicarea
problemei…………….........................................17
7)Rezolvarea problemei………………………………………19
8)Biografie…………………………………………………….
.23
Capitolul 1
PREZENTAREA TEHNICII BACKTRAKING
Aceasta tehnica se foloseste in rezolvarea problemelor care indeplinesc
simultan urmatoarele conditii:
solutia lor poate fi pusa sub forma unui vector S=x1,x2,x3…xn cu
x1(A1,x2(A2,.....,xn(An;
multimile A1,A2,A3…An sunt multimi finite ,iar elementele lor se
considera ca se afla intr-o relatie de ordine bine stabilita
nu se dispune de o alta metoda de rezolvare ,mai rapida.
Observatii:
nu pentru toate problemele n este cunoscut de la inceput;
x1,x2,x3…xn pot fi la randul lor vectori;
in multe probleme multimile A1,A2,A3…An coincid;
La intalnirea unei astfel de probleme, daca nu cunoastem aceasta
tehnica,suntem tentati sa generam toate elementele produsului cartezian
A1(A2(A3…(An si fiecare element sa fie testat daca este
solutie.Rezolvand problema in acest mod,timpul de executie este atat de
mare ,incat poate fi considerat infinit,neavand nici o valoare
practica.
De exemplu,daca dorim sa generam toate permutarile unei multimi finite
A,nu are rost sa generam produsul cartezian A1A2A3…An pentru ca
apoi,sa testam,pentru fiecare element al acestuia,daca este sau nu
permutare .
Tehnica Backtracking are la baza un principiu extrem de simplu:
se construieste solutia pas cu pas:x1x2x3…xn;
daca se constata ca,pentru o valoare aleasa,nu avem cum sa ajungem la
solutie ,se renunta la acea valoare si se reia cautarea din punctul in
care am ramas
Concret:
se alege primul element x1 ce apartine lui A1
presupunand generate elementele x1,x2,x3…xk apartinand multimilor A1 A
2A3…Ak+1 se alege(daca exista) x,primul element disponibil din
multimea Ak+1,apar astfel 2 posibilitati:
nu s-a gasit un astfel de element,caz in care se reia cautarea
considerand generate elementele x1,x2,x3…xk+1 iar aceasta se reia de
la urmatorul element al multimii Ak ramas netestat
a fost gasit,caz in care se testeaza daca acesta indeplineste anumite
coditii de continuare ,aparand astfel alte doua posibilitati:
2.1) le indeplineste,caz in care se testeaza daca s-a ajuns la solutie
si apar din nou doua posibilitati
2.1.1) s-a ajuns la solutie ,se tipareste solutia si se reia algoritmul
considerand generate elementele x1,x2,…xk(se cauta in continuare un
alt element al multimii Ak+1 ramas netestat)
2.1.2) nu s-a ajuns la solutie ,caz in care se reia algoritmul
considerand generate elementele x1,x2,x3…xk+1 si se cauta un prim
element xk+2 ( Ak+2
2.2) nu le indeplineste caz in care se reia algoritmul considerand
generate elementele x1x2 x3…xk iar elementul xk+1 se cauta intre
elementele multimii Ak+1 ramase netestate.
Algoritmul se termina atunci cand nu mai exista nici un element
x1(A1 netestat.
Observatie: tehnica Backtracking are ca rezultat obtinerea tuturor
solutiilor problemei.In cazul in care se cere o singura solutie se poate
forta oprirea atunci cand a fost gasita.
Pentru usurarea intelegerii metodei,vom prezenta o rutina unica
aplicabila oricarei probleme,rutina care utilizeaza notiunea de
stiva.Rutina va apela proceduri si functii care au totdeauna acelasi
nume si parametri si care din punct de vedere al metodei realizeaza
acelasi lucru.Sarcina rezolvitorului este de a scrie explicit pentru
fiecare problema in parte procedurile si functiile apelate de
Backtraking.Evident,o astfel de abordare conduce la programe
lungi.Nimeni nu ne opreste,ca dupa intelegerea metodei sa scriem
programe scurte specifice fiecarei probleme in parte(de exemplu scurtam
substantial textul doar daca renuntam la utilizarea procedurilor si
functiilor)
Prezentam in continuare rutina Backtracking:
k:=1;init(1,st);
while k>0 do
begin
repeat
succesor(as,st,k);
if as then valid(ev,st,k);
until (not as) or (as and ev );
if as then
if solutie(k) then
tipar
else
begin
k:=k+1;
init(k,st);
end
else
k:=k-1;
end;
Observatie:
Problemele rezolvate prin aceasta metoda necesita un timp indelungat.Din
acest motiv,este bine sa utilizam metoda numai atunci cand nu avem la
dispozitie un alt algoritm mai eficient.Cu toate ca exista probleme
pentru care nu se pot elabora alti algoritmi mai eficienti,tehnica
Backtracking trebuie aplicata numai in ultima instanta.
CAPITOLUL 2
NOTIUNI DESPRE RECURSIVITATE
Recursivitatea este una din notiunile fundamentale ale
informaticii.Utilizarea frecventa a recursivitatii s-a facut dupa anii
80.Multe din limbajele de programare evoluate si mult utilizate(Fortran
,Cobol) nu permiteau scrierea programelor recursive.
In linii mari,recursivitatea este un mecanism general de elaborare a
programelor .Ea a aparut din necesitati practice (transcrierea directa a
formulelor matematice recursive) si reprezinta acel mecanism prin care
un subprogram(procedura,functie) se autoapeleaza.
Daca lucrurile par usor de inteles in cazul functiilor,nu tot atat de
simplu este sa aplicam recursivitatea utilizand proceduri.Astfel vom
vedea ca putem genera recursiv probleme de genul permutarilor.
Un algoritm recursiv are la baza un mecanism de gandire diferit de cel
cu care ne-am obisnuit deja.Atunci cand scriem un algoritm recursiv este
suficient sa gandim ce se intampla la un anumit nivel pentru ca la
orice nivel se intampla exact acelasi lucru.
Un algoritm recursiv corect trebuie sa se termine ,contrar programul se
va termina cu eroare si nu vom primi rezultatul asteptat.Conditia de
terminare va fi pusa de programator.
Un rezultat matematic de exceptie afirma ca pentru orice algoritm
iterativ exista si unul recursiv echivalent(rezolva aceeasi problema) si
invers,pentru orice algoritm recursiv exista si unul iterativ
echivalent.
In continuare, raspundem la intrebarea:care este mecanismul intern al
limbajului care permite ca un algoritm recursiv sa poata fi
implementat?
Pentru a putea implementa recursivitatea ,se foloseste structura de date
numita stiva.
Mecanismul unui astfel de program poate fi generalizat cu usurinta
pentru obtinerea recursivitatii.Atunci cand o procedura sau o functie se
autoapeleaza se depun in stiva:
valorile parametrilor transmisi prin valoare
adresele parametrilor transmisi prin referinta
valorile tuturor variabilelor locale(declarate la nivelul procedurii sau
functiei)
Din punct de vedere al modului in care se realizeaza autoapelul ,exista
doua tipuri de recursivitate:direct si indirecta.
Recursivitatea directa a fost deja prezentata.Recursivitatea indirecta
are loc atunci cand o procedura (functie) apeleaza o alta
procedura(functie),care la randul ei o apeleaza pe ea.
Un astfel de exemplu ar fi urmatorul:
Se considera doua valori reale,pozitive a0,b0 si n un numar natural.
Definim sirul:
an=(an-1+bn-1)/2 bn=an-1bn-1
Vom folosi doua functii a(n) si b(n).Fiecare dintre ele se autoapeleaza
dar o apeleaza si pe cealalalta.
CAPITOLUL 3
Backtracking recursiv
In capitolul 1 am prezentat rutina de backtracking
clasica,nerecursiva.In acest capitol prezentam rutina de backtracking
recursiva.Procedurile si functiile folosite sunt in general aceleasi,cu
doua mici exceptii:
SUCCESOR nu mai este procedura ci functie booleana ;
rutina backtracking se transforma in procedura,care se apeleaza prin
BACK(1)
Principiul de functionare al procedurii BACK,corespunzator unui nivel k
este urmatorul:
in situatia in care avem o solutie,o tiparim si revenim pe nivelul
anterior
in caz contrar se initializeaza nivelul si se cauta un succesor
cand am gasit unul verificam daca este valid;procedura se autoapeleaza
pentru (k+1) , in caz contrar urmand a se continua cautarea
succesorului;
daca nu avem succesor,se trece pe nivel inferior (k-1) prin iesirea din
procedura BACK
Vom explica in continuare utilizarea backtrackingului recursiv prin
generarea permutarilor:
program permutari;
type stiva=array[1..9] of integer;
var st:stiva;
ev:boolean;n,k:integer;
procedure init(k:integer;var st:stiva);
begin
st[k]:=0;
end;
function succesor(var st:stiva;k:integer):boolean;
begin
if st[k]
m do d:=d^.ad;
write( n= );readln(n);
new(e);
e^.nr:=n;
e^.as:=d;
d^.ad^.as:=e;
e^.ad:=d^.ad;
d^.ad:=e;
end;
Procedura se va apela includ(m,b)
4.2.4) Stergerea in interiorul listei
Aceasta operatie este realizata de procedura sterg.Operatiile efectuate
de aceasta procedura sunt urmatoarele:
se parcurge lista de la stanga la dreapta pentru a ne pozitiona pe
inregistrarea care urmeaza a fi stearsa;
campul de adresa dreapta al inregistrarii care o precede pe aceasta va
lua valoarea campului de adresa dreapta al inregistrarii care va fi
stearsa
campul de adresa stanga al inregistrarii care urmeaza inregistrarii care
va fi stearsa va lua valoarea campului de adresa stanga al inregistrarii
pe care o stergem;
se elibereaza spatiul de memorie rezervat inregistrarii care se sterge;
procedure sterg(m:integer;b:ref);
var d:ref;
begin
d:=b;
while d^.nr<>m do d:=d^.ad;
d^.as^.ad:=d^.ad;
d^.ad^.as:=d^.as;
disose(d);
end;
Procedura se va apela sterg(m,b)
4.2.5) Listare de la stanga la dreapta
Aceasta operatie este realizata de procedura listare,procedura care
realizeaza urmatoarele operatii:
porneste din stanga listei
atat timp cat nu s-a ajuns la capatul din dreapta al listei,se tipareste
informatia utila si se trece la inregistrarea urmatoare;
procedure listare(b:ref);
var d:ref;
begin
d:=b;
while d<>nil do
begin
writeln(d^.nr);
d:=d^.ad;
end;
end;
Procedura se apeleaza listare(b);
CAPITOLUL 5
Enuntul problemei
Fie o permutare a primelor m numere naturale (0b[j] then
begin
aux:=b[i];
b[i]:=b[j];
b[j]:=aux;
end;
Odata gasite elementele cerute de problema ,vom incerca sa rezolvam
punctul a) al acesteia prin introducerea numerelor din vectorul b ,deja
ordonate,intr-o lista dublu inlantuita.Despre crearea unei astfel de
liste am vorbit insa mai pe larg intr-un capitol anterior(vezi capitolul
4).
Dupa ce am creat aceasta lista ,vom deschide pentru scriere fisierul
"out.txt" in care vom lista elementele listei anterior create.Despre
pasii realizarii acestei operatii s-a vorbit deasemenea la capitolul 4.
Astfel a fost indeplinita prima cerinta a problemei.
Pentru punctul b) o sa avem nevoie de un alt vector ,cifre,care sa
indice numarul de cifre pe care il are fiecare element al vectorului
b.Totodata o sa stabilim si numarul de grupe existente,fiecare grupa k
continand numerele cu indicii de la li[k] si ls[k].
Urmatorul pas va fi de a construi vectorul apart in care elementele au
urmatoarea semnificatie:apart[i] indica numarul grupei careia ii
apartine numarul de pe pozitia i din vectorul b.Dupa indeplinirea
acestei instructiuni nu ne ramane decat sa dam curs apelarii procedurii
recursive rec(0)(observam aici utilizarea unui algoritm backtracking
nestandardizat).
Pentru a intelege mai bine programul,vom descrie si subprogramele
folosite in acest program.Acestea sunt numai proceduri.
Proceura recurs obtine permutarile elementelor din vectorul b in
vectorul yy,verifica daca elementul nu se afla deja pus.Daca da,si grupa
careia ii apartine elementul i,apart[i] este aceeasi cu grupa valida la
nivelul lng+1 conform permutarii curente a grupelor,scrisa in xx,adica
corect[lng+1],se reapeleaza pentru noul nivel.
Procedura bkt construieste vectorul corect cu semnificatia
corect[i]--grupa din care trebuie sa faca parte elementul aflat pe
pozitia i in permutarea numerelor construita in yy
Procedura rec construieste permutarile numerelor de la 1 la gr in
vectorul xx,adica obtine permutarile grupelor.
CAPITOLUL 7
Rezolvarea problemei
program prb_mixta;
type lista=^camp;
camp=record
inf:longint;
ls,ld:lista;
end;
var cifre,a,b,li,ls,apart,corect,xx,yy:array [1..9] of longint;
k,kk,aux,grupa,dist,s,m,i,cifra,gr,j:longint;
prim,ant,x:lista;
dis:boolean;
f:text;
procedure scrie;
begin
for i:=1 to m do
write(f,b[yy[i]], );
writeln(f);
end;
procedure recurs(lng:integer);
{obtine permutarile elementelor din vectorul b in vectorul yy}
var i:integer;
begin
if lng=m then scrie
else
for i:=1 to m do
begin
dis :=true;
for j:=1 to lng do
{verifica daca elementul nu se afla deja pus}
if yy[j]=i then dis:=false;
{daca dis=true si grupa careia ii apartine elementul
i,apart[i]}
{este aceeasi cu grupa valida la nivelul lng+1 conform}
{permutarii curente a grupelor scrisa in xx,adica corect[lng+1]}
{se reapeleaza pentru noul nivel}
if dis and (apart[i]=corect[lng+1]) then
begin
yy[lng+1]:=i;
recurs(lng+1);
end;
end;
end;
procedure bkt {construieste vectorul corect cu semnificatia:};
begin {corect[i] - grupa din care trebuie sa faca}
s:=0; {parte elementul aflat pe poz i in}
for i:=1 to gr do {permutarea numerelor construita in yy}
begin
grupa:=xx[i];
dist:=ls[grupa]-li[grupa];
for j:=(s+1) to (s+dist) do
corect[j]:=grupa;
s:=s+dist;
end;
recurs(0);
end;
procedure rec(l:integer); {construieste permutarile}
var i:integer {numerelor 1..gr in vectorul xx,adica
obtine};
begin {permutarile grupelor}
if l=gr then bkt
else
for i:=1 to gr do begin
dis:=true;
for j:=1 to l do
if xx[j]=i then dis:=false;
if dis then
begin
xx[l+1]:=i;
rec(l+1);
end;
end;
end;
begin
write( M= );readln(m);
for i:=1 to m do
begin
write( a[ ,i, ]= );readln(a[i]);
end;
for i:=1 to m do {generez ficare numar in vectorul b}
begin
b[i]:=a[i];
cifra:=a[i];
while (b[i] mod 10) <>i do
begin
b[i]:=b[i]*10+a[cifra];
cifra:=a[cifra];
end;
end;
for i:=1 to m-1 do {ordonam crescator elementele
vectorului b}
for j:=i+1 to m do
if b[i]>b[j] then
begin
aux:=b[i];
b[i]:=b[j];
b[j]:=aux;
end;
new(prim); {se creeaza lista dublu inlantuita}
prim^.inf:=b[1];
prim^.ls:=nil;
prim^.ld:=nil;
ant:=prim;
for i:=2 to m do
begin
new(x);
x^.inf:=b[i];
x^.ls:=ant;
x^.ld:=nil;
ant^.ld:=x;
ant:=x;
end;
assign(f, out.txt );rewrite(f); {se tiparesc elementele listei}
{in fisierul de iesire}
x:=prim;
while x<>nil do
begin
write(f,x^.inf, );
x:=x^.ld;
end;
writeln(f);
for i:=1 to m do
begin
j:=b[i];
cifre[i]:=0;
while j>0 do
begin
cifre[i]:=cifre[i]+1;
j:=j div 10 ;
end;
end;
{am construit vectorul cifre in care elementul cifre[i] indica}
{numarul de cifre al lui b[i]}
gr:=0;
k:=1;
repeat
kk:=k;
while (cifre[kk]=cifre[k]) and (kk<=m) do kk:=kk+1;
gr:=gr+1;
li[gr]:=k;
ls[gr]:=kk;
k:=kk;
until k>m;
{am calculat numarul gr de grupe}
{fiecare grupa contine numerele cu indicii de la li[k] la ls[k]}
for i:=1 to gr do
for j:=li[i] to ls[i] do
apart[j]:=i;
{am construit vectorul apart in care elementele au urmatoarea}
{semnificatie:}
{apart[i] indica numarul grupei careia ii apartine numarul de pe }
{pozitia i din vectorul b}
rec(0);
close(f);
end.
PAGE
PAGE 2
nil in1 adr2 aaaaaar2 adr2
adr1 in2 adr3
adrn-1 inn nil
ì¥Â@