Atesttat informatica

8/6/2019 Atesttat informatica

1/17

3

Introducere 2I. Metoda de programare Backtracking .... 3

II. Metoda Backtracking generalizat ..... 5III. Problema Labirintului 7IV. Problema sariturii calului 11V. Problema Bilei . 13

VI. Backtracking generalizat recursiv ....... 15VII. Problema labirintului (recursiv) ..... 16Bibliografie 17


2/17

4

Pentru prelucrarea informaiei omul a inventat calculatorul, dar datorit dezvoltriivertiginoase a prelucrrilor de date cu calculatorul, s -au putut aborda i rezolva problemedin ce n ce mai complexe.

Definit n anul 1971 de ctre Niklaus Wirth, limbajul Pascal (numit astfel n cinsteamatematicianului francez Blaise Pascal), este un limbaj de interes general, coceput iniialn scop didactic, ca instrument de nvare a programrii n mod sistematic. Datoritcalitilor sale (folosete un mod bine structurat de reprezentare a programelor, asigurclaritate, sugestivitate i simplitate), acest limbaj a fost adoptat rapid ca limbaj de iniieren programare i a fost apoi axtins cu faciliti care s-i asigure utilizarea performant calimbaj nalt ce poate fi folosit n rezolvarea unei mari diversiti de probleme, cu gradsporit de complexitate.

Limbajul de programare PASCAL este un limbaj agreat de programatori,permindu-le acestora s alctuiasc cu uurin n mod sistematic programe complexe.

Lucrarea urmrete prezentarea i explicarea detaliat a metodei BACKTRACKING punnd accent pe forma generalizat a metodei. Aceasta cuprinde, pe lng toate toate

aspectele usual abordate n cadrul metodei, i unele chestiuni de dificultate sporit, oferindastfel puncte de pornire n aprofundarea metodei.

n capitolele I i II, pentru fixarea cunotinelor de baz i pentru crearea unordeprinderi de organizare riguroas n cadrul metodei Backtracking simple i generalizate.

S-au inclus n capitolele III, IV i V probleme ce se rezolv cu ajutorul metodei,toate fiind nsoite de explicarea i rezolvarea complet, dnd i indicaii despre particulariti ale metodei. Problemele nu sunt de acelai nivel, dificultatea acestoracrescnd pe parcursul celor 3 capitole.

Facem referire c problemele rezolvate sub form de program n limbaj de programare Borland Pascal au fost mai nti testate i verificate pentru evitarea

erorilor.Capitolul VI exemplific utilizarea metodei Backtracking generalizat recursive, d

detalii n legtur cu modul acesta de rezolvare a problemelor, n capitolul VII fiindreluat problema din capitolul III dar implementat acum recursiv.


3/17

5

De multe ori, n aplicaii apar probleme n care se cere gsirea unor soluii de formax=x1x2...xn unde xi A, i = 1,,n n carex1xn trebuie s ndeplineasc anumite condiii.

Am putea s generm toate combinaiile posibile de valori i apoi s le alegem doar pecele convenabile. Considernd mulimile A = {ai,1,ai,2,,ai,n(i)}, aceste combinaii s-ar puteaconstrui astfel: pentru fiecare valoare posibil fixat pentru componenta xi, vom alege toatevalorile posibile pentru componenta xi+1 i pentru fiecare astfel de valoare fixat pentruxi+1 vomalege toate valorile posibile pentru componentaxi+2, etc.

Rezolvnd problema n acest mod, deci genernd tote elementele produsului cartezian

nAAA vvv ...21 i verificnd abia apoi dac fiecare combinaie este o soluie, eficient estesczut.

Astfel, dac de exemplu ne propunem s generm toate cuvintele formate cu litere a,b,c,aa nct fiecare liter s apar o singur dat, combinaiile posibile sunt n numr de 27, dintrecare convin doar 6.

Tehnica Backtracking propune generarea soluiei prin completarea vectorului x n ordinex1x2...xn i are la baz un principiu de bun sim: dac se constat c avnd o combinaie parialde form v1v2...v k-1 (unde vi,,vk-1sunt valori deja fixate), dac alegem pentru xk o valoare vk icombinaia rezultat nu ne permite s ajungem la o soluie, se renun la aceast valoare i sencearc o alta (dintre cele netestate n aceast etap). ntr-adevr, oricum am alega celelaltevalori, dac una nu corespunde nu putem avea o soluie.

Pentru exemplu ales anterior se observ c dac notm cuvntul cux1x2x3, combinaia aax3nu ne poate conduce la o soluie (literele trebuie s fie distincte) i deci nu are sens s maincercm s stabilim valori pentrux3.

Altgoritmul general al metodei BacktrackingPentru evitarea generrii combinaiilor neconvenabile se procedeaz astfel:Presupunem c s-au gsit valorile v1v2vk-1 pentru componentele x1x2...xk-1(au rmas de

determinat valorile pentruxkxn). ne ocupm n continuare de componentaxk. Paii urmai sunt:1. Pentru nceput, pentruxknu s-a testat nc nici o valoare.2. Se verific dac exist valori netestate pentruxk.

a) n caz afirmativ, se trece la pasul 3.b) Altfel, se revine la componenta anterioar,xk-1; se reia pasul 2 pentru k=k-1.

3.Se alege prima valoare v dintre cele netestate nc pentruxk.4. Se verific dac acest combinaie parial v1v2vk-1v ne poate conduce la un rezultat(dac sunt ndeplinite anumite condiii de continuare).

a) Dac valoarea aleas este bun se trece la pasul 5.b) Altfel, se rmne pe aceeai poziie ki se reia cazul 2.

5. Se verific dac s-a obinut o soluie .a) n caz afirmativ, se tiprete aceast soluie i se rmne la aceeai component

xk, relundu-se pasul 2.b) Altfel se reia altgoritmul pentru urmtoarea component (se trece la pasul 1

pentru k=k+1).


4/17

6

Altgoritmul ncepe prin stabilirea unei valori pentru componenta x1(k=1) i se ncheie cnd pentru aceasta am testat toate valorile posibile i conform pasului 2b) ar trebui s revenim lcomponenta anterioar, care n aceast caz nu exist.

Rezumnd, metoda Backtracking se folosete n rezolvarea problemelor care ndeplinesccondiiile:

- soluia poate fi pus sub forma unui vector S=x1x2xn, undexi ;,...,1, niAi ! - mulimileAi sunt finite i ordonate (pentru a lua n considerare toate valorile posibile).

nainte de a scrie programul care ne va obine soluiile, trebuie s stabilim unele detalii cuprivire la:

- vectorul soluiecte componente are, ce menine fiecare component.- mulimea de valori posibile pentru fiecare component (sunt foarte importante

limitele acestei mulimi).- condiiile decontinuare(condiiile ca o valoare x[k]s fie acceptat).- condiiacaansamblul devalori generat s fie soluie. Pe baza acestor date vom scrie apoi procedurile i funciile pe care le vom apela n

altgoritmul general al metodei, dat mai jos, care se poate aplica tuturor problemelor ce respectcondiiile menionate anterior. Aceste proceduri i funcii au o semnificaie comun, prezentndns particulariti n funcie de fiecare problem n parte.

Astfel, se va nota cu x vectorul care conine soluia; x[k] = v va avea ca semnificaiefaptul c elementul al-v-lea din mulimea de valori ppsibile Ak a fost selectat pentru componenta

xk. dac mulimea Ak are m elemente, a1a2am,pentru uurin ne vom referii la indicii lor

1,2,,m. Deci valorile posibile pentru o component vor fi 1,2,,m n aceast ordine.Iniial, cnd pentru o component nu am testat nc nimic, aceasta va avea valoarea 0 (unindice care nu exist). Aceast operaie se va realiza n procedura INIT care va avea ce

parametru poziia k.

Funcia EXISTA(k) verific dac ultima valoare aleas pentru componentaxk nu a atinslimita maxim admis (indicele de valoare maxim). ntruct elementele sunt testate n ordine,acest lucru este echivalent cu a verifica dac mai avem valori netestate nc pentru aceastcomponent.

Funcia CONT(k) verific dac valoarea aleas pentru x[k] ndeplinete condiiile decontinuare, deci dac aceast combinaie parial v1v2vk

poate s conduc la o soluie.

Observaii: - n unele probleme n variaz de la o soluie la alta;- mulimile Ai pot coincide;- metoda Backtracking ofer toate soluiile.

Observaie: De obicei valorile posibile sunt chiar successive i n acest caz se poateconsidera c x[k] = v are semnificaia c pentru componentaxk s-a ales chiar valoarea v.n acest caz iniializarea trebuie fcut cu o valoare imediat naintea primei valoriposibile. De exemplu dac valorile posibile ar fi 5,6,7, atunci iniializarea se va face cuvaloarea x[k] = 4

Observaie: La implementarea acestei funcii, de obicei se pornete de la premisa c sepoate obine o soluie i se identific acele cazuri n care acest lucru este posibil.


5/17

7

Funcia SOLUTIE(k) verific dac s-a ajuns la o soluie final.ProceduraTIPAR(k) tiprete o soluie.

Altgoritmul propus este:

procedure BKT;

var k:integer;

begin

k:=1;INIT(k);

while k>0 do

if EXISTA(k) then

begin

x[k]:=x[k]+1;

VALPOS(k);

if CONT(k) then

if SOLUTIE(k) then

TIPAR(k)

else

begin

k:=k+1;

INIT(k);end;

end

else

k:=k-1;

end;

De asemenea, trebuie s avem n vedere c altgoritmul general se poate modifica i adaptan funcie de problema rezolvat.

Metoda Backtracking generalizat are urmtoarea deosebire fa de metoda obinuit deBacktracking: n metoda obinuit vectorul soluie este un tablou unidimensional, x 1,x2xn,fiecare component avnd o anumit valoare la un moment dat, dar dac componenta xk are maimulte caracteristici atunci este nevoie folosirea metodei generalizate.

n acest caz vectorul x trebuie s descrie aceste caracteristici. Valorile posibile ale uneicomponente trebuie generate n ordine, dar pentru c o valoare are mai multe caracteristici vomutiliza o variabil auxiliar cu ajutorul creia vom nota (i vom obine) n ordine toate acestevalori posibile.

Observaii: n situaiile n care operaiile relizate n procedurile enunate suntsimple, se poate renuna la implementarea lor n aceast form, iar altgoritmulgeneral va conine direct aceste operaii.


6/17

8

Astfel, pentru a genera toate valorile posibile pentru o component k este suficient sgenerm toate valorile posibile pentru aceast variabil auxiliar i pe baza lor s aflm valorilelui x[k].

De exemplu dac x este vectorul soluie, iar d vectorul auxiliar, putem descrie un tip debaz pentru o component astfel:

const nmax=20 ;type component=record

caract1: tip1;

caract2: tip2;

end;

var x:array[1..nmax] of component;

d:array[1..nmax] of integer;

Un altgoritm general ar putea fi:

procedure BKTG;

var k:integer;begin

k:=1;

INIT(k);

while k>0 do

if EXISTA(k) then

begin

d[k]:=d[k]+1;

VALPOS(k);

if CONT(k) then

if SOLUTIE(k) then

TIPAR(k)

else

begink:=k+1;

INIT(k);

end;

end

else

k:=k-1;

end;

Procedura INIT va iniializa datele referitoare la componenta k-practic va iniializacomponenta corespunztoare din vectorul auxiliar, d[k].

Funcia EXISTA verific dac mai exist valori netestate nc pentru componenta k

(practic dac mai exist valori posibile pentru componenta corespunzatoare din vectorul auxiliar).Procedura VALPOS va completa pentru componenta k n vectorul soluie valoareacaracteristicilor sale, n funcie de valoarea lui d[k].

CONT, SOLUTIE, TIPAR au aceeai semnificaie ca i n cazul metodei simple.

Observaie:Uneori este posibil ca prima componenet (sau primele) s aib valori dejafixate i n acest caz generarea se realizeaz pentru componentele 2,3,


7/17

9

Se d un labirint sub form de matricecu m linii si n coloane. Fiecare element al

matricei se codific cu: 0 dac este zid icu 1 dac este culoar.

ntr-un punct al labirintului, de coordonate(l0,c0) se gsete o persoan. Se cere s se

gseasc toate ieirile din labirint.De exemplu, pentru un labirint cu configuraia

0 0 1 0 00 0 1 0 01 1 1 1 10 0 0 1 10 0 0 0 0

unde l0=3, c0=3,am putea avea posibilitile:

0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0

0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 01 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Pentru a scrie programul stabilim urmtoarele:- vom folosi matricea tab pentru a memora configuraia labirintului.- vectorul soluie are un numr variabil de componente i conine o succesiune de

elemente ale tabloului care ar reprezenta un drum n labirint. Un element al vectorului,x[k], conine coordonatele unui punct n care ne aflm la pasul respective: linia sicoloana (l,c).

- pentru a determina mulimea de valori posibile pentru o component, inem cont deurmtoarele:

Aflndu-se ntr-un punct dat, persoana poate s mearga n 4 direcii pe care le codificm cu1,2,3,4Fiecare direcie de deplasare induce un anumit deplasament liniei, respectiv coloanei.Astfel:

j - pe direcia 1: linia scade cu o unitate, deci deplasamentul ei este1coloana rmne aceei, deci deplasamentul ei este 0

1 - pe direcia 2: linia rmne aceeai, deci deplasamentul ei este 0i 3 * 2 coloana crete cu o unitate, deci deplasamentul ei este 1


8/17

10

4 - pe direcia 3: linia crete cu o unitate, deci deplasamentul ei este 1coloana rmne aceei, deci deplasamentul ei este 0

- pe direcia 4: linia rmne aceeai, deci deplasamentul ei este 0coloana scade cu o unitate, deci deplasamentul ei este -1

Din punctul k-1 caracterizat de coordonatele (x[k-1].1,x[k-1].c) ca punct urmtorn traseul urmat ar putea fi unul din punctele vecine date de direcia de deplasare aleas. Deci

vom alege ca vector auxiliar un vector d care ne memoreaz direcia aleas pentru a ajunge npunctul curent.Astel, coordonatele punctului curent se deduc n funcie de punctul din care se pleac,

x[k-1], direcia de deplasare aleas, d[k], respectiv deplasamentul indus de aceast direcieliniei si coloanei:

X[k].l = x[k-1].l + depl[d[k]].l

X[k].c = x[k-1].c + depl[d[k]].c

Deplasamentele fiind nite mrimi constante, pot fi initializate de la declarare.Procedura VALPOS calculeaz coordonatele punctului corespunztor componentei k n

funcie de punctul din care se pornete i de direcia aleas.- condiii de continuare pentru ca o valoare x[k] s fie acceptat:

- persoana nu trebuie s treac de 2 ori prin acelai loc;- valoarea x[k] trebuie s corespund unui culoar.

- am gsit o soluie final dac am ajuns pe una din laturile labirintului, deci linia saucoloana s se afle pe una din margini.

Pentru exemplu considerat, vectorul soluie se va completa astfel:

d1d2d3 x1 x2 x3 0 (3,3) Stabilim valoarea primei componente, care este corespunztoare

punctului din care se pleac(l0,c0). Direcia din care s-a ajuns aicinu intereseaz.

0 1 (3,3)(2,3) Prima direcie posibil este 1. Din (3,3) pe directia 1 ajungem in punctul (2,3) -convine este pe culoar. Trecem la urmtoareacomponent, k=3.

0 1 1 (3,3)(2,3)(1,3) ncepem cu prima direcie posibil pentru acest component,d[3]=1; coordonatele punctului corespunztor lui k=3 n careajungem din x[2]pe direcia 1 sunt (1,3) -convine. Se observ cam ajuns la marginea labirintului, deci am obinut o soluie ,pe careo tiprim. Rmnem la k=3.

0 1 2 (3,3)(2,3)(2,4) Urmtoarea valoare posibil pentru d[3] este 2; punctul n care

ajungem este (2,4) care nu convine, fiind n zid. Rmnem la k=3.0 1 3 (3,3)(2,3)(3,3) Pornind din (2,3) pe direcia 3 ajungem n (3,3)- nu convine, ammai trecut pe aici. Deci in continuare k=3.

0 1 4 (3,3)(2,3)(2,2) Pentru urmtoarea direcie, 4, punctul n care se ajunge din (2,3)este (2,2) nu convine este zid. Am epuizat toate direciile posibile

pentru k=3, deci revenim la k=2.0 2 (3,3)(3,4) Urmtoarea direcie posibil pentru k=2 este 2; punctul n care se

ajunge este (3,4), care convine. Trecem la k=3;0 2 1 (3,3)(3,4)(2,4) Prima direcie aleasa este 1; pornind din x[k-1] punctul (3,4),

ajungem n (2,4) nu convine, fiind zid, rmnem la k=3;


9/17

11

0 2 2 (3,3)(3,4)(3,5) Pe direcia d[3]=2, punctul n care se ajunge este (3,5) este pemargine, deci am obinut o nou soluie. Rmnem la k=3, pentru onou direcie.

0 2 3 (3,3)(3,4)(4,4) Urmtoarea valoare pentru d[3]este 3, iarx[3]-punctul (4,4) convine; trecem la k=4.

0 2 3 1 (3,3)(3,4)(3,4) Prima direcie posibil este d[4]=1, iarx[4]este punctul (3,4) nu convine; rmnem la k=4.

Procedeul continu pn cnd am epuizat toate valorile posibilepentru componenta d[2](de la ea ncepe generarea).Procedura BKTG este modificat n ceea ce priveste faptul c generarea se face pentru

componentele 2,3, deoarece prima poziie este fixat.Programul corespunztor este:

program labirint1;

uses crt;

type component=record

l,c:integer;

end;

vectsol=array[1..100]of component;

auxiliar=array[1..100]of 0..4; labirint=array[1..25,1..25]of char;

const depl:array[1..4]of component=((l: -1;c:0),(l:0;c:1),

(l:1;c:0),(l:0;c:-1));

var x:vectsol;

d:auxiliar;

tab:labirint;

n,m:integer;

l0,c0:integer;

procedure citire;

var i,j:integer;

beginclrscr;

writeln('configuratia labirintului: ');

write('m=');readln(m);

write('n=');readln(n);

writeln('Se codifica astfel: 1-culoar; 0-zid');

for i:=1 to m do

for j:=1 to n do

begin

write('tab[',i,',',j,']=');

readln(tab[i,j]);

end;

writeln('Pozitia initiala: ');

write('l0=');readln(l0);write('c0=');readln(c0);

x[1].l:=l0;

x[1].c:=c0;

end;

procedure INIT(k:integer);

begin

d[k]:=0;

end;

function EXISTA(k:integer):bool ean;


10/17

12

begin

EXISTA:=d[k]1 do

if EXISTA(k)then

begin

d[k]:=d[k]+1;

VALPOS(k);

if CONT(k)then

if SOLUTIE(k)then

TIPAR(k)else

begin

k:=k+1;

INIT(k);

end;

end

else

k:=k-1;

end;

begin


11/17

13

CITIRE;

BKTG;

end.

Se d o tabl de ah de dimensiune mxn. Un cal se afln poziia (l0,c0). S se gseasc toate modalitile prin careacesta poate s parcurg ntreaga tabl far s treac dedou ori prin acelai loc.

De exemplu, pentru n = m = 5, i poziia iniial (1,1) o soluie este:

1 20 17 12 316 11 2 7 1821 24 19 4 13

10 15 6 23 825 22 9 14 5

Problema trateaz aceeai situaie ca i n cazul labirintului, avnd specific alegereavalorilor posibile pentru o component.

Pentru a scrie programul, vom stabili urmtoarele repere:- vectorul solutie are nxm componente, fiind nxm elemente pe tabla de

ah (iar calul trebuie s treac prin toate). Fiecare component caracterizeazun element al tablei prin coordonatele sale l,c;

- determinarea valorilor posibile pentru componenta k se face astfel:aflndu-se ntr-un punct dat, calul poate sri n 8 direcii pe care le codificm1,2, , 8, ca n figura alturat.

- pe direcia 1: calul se mut cu 2 linii mai sus, deci deplasamentul liniei este 2coloana se mut la dreapta cu 1, deci deplasamentul ei este 1

- pe direcia 2: linia scade cu 1, deci deplasamentul ei este -1coloana crete cu 2 unitai, deci deplasamentul ei este 2

- pe direcia 3: linia coboar cu o unitate, deci deplasamentul ei este -1coloana se mut la dreapta cu 2, deci deplasamentul ei este 2

(analog se completeaz deplasamentele pentru toate cele 8 cazuri).

Din punctual k-1,caracterizat de coordonatele (x[k-1].l,x[k-1].c), ca puncturmtor n traseul urmat ar putea fi unul din punctele date de direcia de deplasare aleas. Decivom alege ca vector auxiliar un vectord care ne memoreaz direcia aleas pentru a ajunge n

punctul current.Astfel, coordonatele punctului curent se deduc n funcie de punctul din care se pleac,

x[k-1], direcia de deplasare aleas, d[k],respective deplasamentul Indus de aceast direcieliniei i coloanei:

X[k].l = x[k-1].l + depl[d[k]].l

X[k].c = x[k-1].c + depl[d[k]].cDeplasamentele fiind nite mrimi constante, pot fi iniializate de la declarare.

8 17 2

*

6 35 4


12/17

14

- condiii de continuare:- poziia aleas nu trebuie s fie n afara tablei de ah;- calul nu trebuie s trec de mai multe ori prin acelai loc, deci x[k]x[i]

pentru oricei=1, ,k-1;- am am gsit o soluie final dac am completat toate componentele vectorului (deci

k=nxm ).Pentru exemplul considerat se va stabili prima component cu coordonatele punctului n

care se afl persoana iniial: k =1, x[k].l = l0 =1, x[k].c = c0 = 1.Se ncepe de la k = 2. Vectorul soluie se va completa astfel:

d1d2d3 x1 x2x3 0 (1,1) Stabilim valoarea primei componente, care este

corespunztoare punctului de plecare (l0,c0).Direcia din care a ajuns aici nu ne intereseaz.

0 1 (1,1)(-1,2) Prima direcie posibil este 1. din (1,1) pe direcia 1ieim de pe tabla de ah, deci nu convine; rmnemla k=2.

0 2 (1.1)(0,3) Pe aceast direcie de asemenea prsim tabla, deci

rmnem la k=2.0 3 (1,1)(2,3) Pentru aceast direcie ajungem n (2,3) -

convine,deci trecem la k=3.0 3 1 (1,1)(2,3)(0,4) Testm prima direcie posibil: pornind din (2,3) pe

direcia 1 ajungem n (0,4) nu convine, am ieitde pe tabl. Deci n continuare k=3.

0 3 2 (1,1)(2,3)(1,5) Pentru urmtoarea direcie, 2, punctual n care seajunge din (2,3)este (1,5) convine, deci trecem lak=4.

Procedeul continu pn cnd am epuizat toatevalorile pentru componenta d[2] (de la ea ncepe

generarea).Datele folosite n program sunt:


l,c:integer;

end;


auxiliar=array[1..100] of 0..4;

tabla=array[1..25,1..25]of integer;

const depl:array[1..8]of component=((l: -2;c:1),(l:-1;c:2),(l:1;c:2),

(l:2;c:1),(l:2;c:-1),(l:1;c:-2),(l:-1;c:-2),(l:-2;c:-1));

var x:vectsol;

d:auxiliar;n,m:integer;

l0,c0:integer;

Procedurile i funciile care prezint particulariti sunt:

procedure citire;

var i,j:integer;

begin




13/17

15


write('l0=');readln(l0);

write('c0=');readln(c0);

x[1].l:=l0;

x[1].c:=c0;

end;

function EXISTA(k:integer):boolean;

begin

EXISTA:=d[k]


14/17

16

- pe direcia 3: bila rmne peaceeai linie ,

deci deplasamentul liniei este 0 coloana se mut la dreapta cu 1, decideplasamentul ei este 1(analog se completeaz deplasamentele pentru toate cele 8 cazuri).

Din punctual k-1, caracterizat de coordonatele (x[k-1].l,x[k-1].c), ca puncturmtor n traseu ar putea fi unul din punctele vecine date de direcia de deplasare aleas. Decivom alege ca vector auxiliar un vector d care ne memorez direcia aleas pentru a ajunge n

punctual current.- condiii de continuare pentru ca o valoare x[k]s fie acceptat: bila nu poate trece dectpe o pozitie vecin cu nlimea mai mica;

- am gsit o soluie final dac am ajuns la marginea terenului.Declaraiile folosite n program sunt:type component=record

l,c:integer;

end;


auxiliar=array[1..100]of 0..4;

teren=array[1..25,1..25]of integer;

const depl:array[1..8]of component=((l:1;c: -1),(l:-1;c:1),(l:0;c:1),

(l:1;c:1),(l:1;c:0),(l:1;c:-1),(l:0;c:-1),(l:-1;c:-1));

var x:vectsol;

d:auxiliar;

n,m:integer;

l0,c0:integer;

cote:teren;

Procedurile i funciile care prezint particulariti sunt:procedure citire;

var i,j:integer;

begin

writeln('configuratia terenului:');


write('n=');

readln(n);

for i:=1 to m do

for j:=1 to n do

begin

write('cote[',i,',',j,']=');

readln(cote[i,j]);

end;


write('l0=');readln(l0);


x[1].l:=l0;

x[1].c:=c0;

end;


begin

EXISTA:=d[k]cote[l,c];

end;


15/17

17

function SOLUTIE(k:integer):boolean;

begin

with x[k] do SOLUTIE:=(l=1)or(c=1)or(l=m)or(c=n);

end;

Dac am scrie un altgoritm care operaiile efectuate asupra unei componente (fie ea k) avectorului soluie generat prin metoda Backtracking generalizat, atunci am putea apela acestaltgoritm i pentru componenta urmatoare, k+1 (pentru c aciunile realizate asupra acesteicomponente sunt similare, ns aplicate altor valori). Dar cum trecerea de la componenta k laurmtoarea face parte din aciunea descris de acest altgoritm, nseamn c apelul este recursiv.

Vom demonstra c altgoritmul recursiv urmeaz corect paii metodei Backtrackinggeneralizat.

Presupunem ca altgoritmul descries pentru o component k se ncheie la epuizareavalorilor posibile pentru aceasta. n aceast situaie se revenea la componenta anterioar, relundtestrile pentru aceast component. ntr-un apel recursiv, la ncheierea execuiei acestuie serevine la programul apelant n cazul nostru am fcut apel din altgoritmul corespunztor lui k-1,deci aceast ntoarcere nu trebuie fcut explicit.

Altgoritmul general n varianta recursiv ar putea avea forma:

procedure BKTGR(k:integer);

begin

INIT(k);

while EXISTA(k) do

begind[k]:=d[k]+1;

VALPOS(k,d);

if CONT(k) then

if SOLUTIE(k) then

TIPAR(k)

else

BKTGR(k+1)

end;

end;

Celelalte funcii care apar au aceeai semnificaie i implementare ca i n variantanerecursiv.

n programul principal procedura se va apela avnd ca parametru prima component

pentru c aceasta se va completa prima. Se observ c altgoritmul se va ncheia atunci cnd vor fitestate toate valorile posibile pentru aceast component i deci seria de apeluri este ncheiat.


16/17

18

program labirintul;

uses crt;


l,c:integer;

end;

vectsol=array[1..100]of component; auxiliar=array[1..100]of 0..4;

labirint=array[1..25,1..25]of 0..2;

const depl:array[1..4]of component=

((l:-1;c:0),(l:0;c:1),

(l:1;c:0),(l:0;c:-1));

var x:vectsol;

d:auxiliar;

tab:labirint;

n,m:integer;

l0,c0:integer;

procedure citire;

var i,j:integer;

beginclrscr;

writeln('configuratia labirintul:');



writeln('Se codifica astfel:

1-culoar; 0-zid');

for i:=1 to m do

for j:=1 to n do

begin

write('tab[',i,',',j,']=');

readln(tab[i,j]);

end;

writeln('Pozitia initiala: '); write('l0=');readln(l0);


x[1].l:=l0;

x[1].c:=c0;

end;

procedure INIT(k:integer);

begin

d[k]:=0;

end;


begin

EXISTA:=d[k]


17/17

19

TIPAR(k)

else

BKTGR(k+1);

end

end;

begin

CITIRE;

BKTGR(2);

end.

BIBLIOGRAFIE:

1. L. oca, A. R. Demco, C. Opincaru, A. SindileInformaticManual pentru clasa a X-aEditura Niculescu - Bucureti, 2000

2. Fl. Munteanu, T. Ionescu, Gh. Musc, D. Saru, S. M. DascluProgramarea calculatoarelorManual pentru liceele de informatic,

clasele X-XIIEditura Didactic i Pedagogic Bucureti, 1995

3. S. Niculescu i colaboratoriBacalaureat i atestatEditura L&S, 1998

Atesttat informatica

Documents

Transcript of Atesttat informatica