Problema Labirintului Informatica [PDF]

Zitiervorschau

Problema labirintului

Să presupunem că labirintul are forma unei grădini englezeşti de formă rectangulară, împrejmuită de gard viu.De-a lungul perimetrului acesteia, gardul viu este întrerupt de una sau mai multe ieşiri.În interior, grădina este alcătuită din coridoare împrejmuite, la rândul lor, de garduri vii.Problema care se pune este aceea că, pornind dintr-un punct interior grădinii, dintr-o poziţie iniţială aflată pe un coridor, să se găsească calea ce conduce, parcurgând numai coridoare (făra a avea posibilitatea de a trece prin gard viu!), la ieşirea din labirint. Exemplu de labirint:

H H H H H H H H

H . H . H . . H

H . . . H . H H

H H . H . . . H

H H . . . H . H

H H H H . H . H

H . . . . H . H

H . H H H . . H

H . H . H . H H

H . H . H . H H

H H . . H . . .

H H H H H H H H

Am figurat cu ajutorul caracterului ‘H’ gardul viu, iar cu ajutorul caracterului ‘.’ spaţiul asociat coridoarelor.Se observă că, pentru reprezentarea acestei grădini-labirint, se foloseşte un tablou bidimensional(ale cărui elemente sunt caracterele ‘H’ şi ‘.’).Suplimentar, o să folosesc denumirea de parcelă asociată unei arii elementare de pe suprafaţa grădinii.În reprezentarea iniţială a labirintului, unei parcele libere îi corespunde caracterul ‘.’, iar o parcelă ocupată este marcată prin ‘H’.Ulterior, pe măsură ce se efectuează deplasări pe coridoarele labirintului, parcelele prin care am trecut deja, se vor nota cu ‘o’, ele pierzând atributele de “libere”.

1

În rezolvarea problemei o să folosesc pentru orientare, mijloacele clasice:punctele cardinale.O primă schiţă a soluţiei problemei labirintului este următoarea (notez P poziţia curentă pe coridoare, prin această poziţie încercând să ne continuăm drumul spre ieşire, prin avansarea la o parcelă liberă din imediata vecinătate): if parcela P se află pe conturul grădinii then am găsit ieşirea din labirint else begin încearcă să te îndrepţi spre Est; if nu am găsit încă ieşirea then încearcă să te îndrepţi spre Sud; if nu am găsit încă ieşirea then încearcă să te îndrepţi spre Vest; if nu am găsit încă ieşirea then încearcă să te îndrepţi spre Nord; end; Soluţia trebuie explicitată!Voi detalia înţelesul “încearcă să te îndrepţi spre Est”, pentru celălalte trei puncte cardinale analogia fiind imediată: {încearcă să te îndrepţi spre Est} if poziţia vecină la Est lui P este o parcelă liberă(coridor) then găseşte o cale de la parcela vecină la Est lui P până la ieşire; Evident, problema pusă: “găseşte o cale de la parcela vecină la Est lui P până la ieşire” este echivalentă problemei originale: “găseşte o cale de la P la ieşire”!Trebuie specificat că ordinea de investigare propusă (Est,Sud,Vest,Nord) a fost aleasă arbitrar, problema rezolvându-se similar pentru orice altă combinaţie a celor patru puncte cardinale. Pentru rezolvare, voi folosi o procedură, ”găsit” , având drept parametrii coordonatele unei parcele şi sarcina de a determina calea de ieşire din labirint, pornind din această parcelă.Procedura este de tip recursiv.

2

Programul (algoritmul propriu-zis): Program Labirintul; uses fdelay,crt; const limnord=1; limsudmax=20; limvest=1; limestmax=20; coridor='.'; gard='H'; pas='o'; marcat='^'; type latitudine=limnord..limsudmax; longitudine=limvest..limestmax; parcele=string[20]; var labirint:array[1..20] of parcele; startlat:latitudine; startlong:longitudine; limsud,i:1..limsudmax; limest,j:1..limestmax; gasit:boolean; f:text; Procedure gasesc(lat:latitudine; long:longitudine); Begin if (lat=limnord) or (lat=limsud) or (long=limvest) or (long=limest) then gasit:=true else begin labirint[lat,long]:=pas; if labirint[lat,long+1]=coridor then gasesc(lat,long+1); if not gasit then if labirint[lat+1,long]=coridor then gasesc(lat+1,long); if not gasit then if labirint[lat,long-1]=coridor then gasesc(lat,long-1); if not gasit then if labirint[lat-1,long]=coridor then gasesc(lat-1,long); end; if gasit then labirint[lat,long]:=marcat; End; Begin{PP} {Secventa de citire a labirintului: a)citirea de la tastatura; b)citirea dintr-un fisier} {a)} {write('dimensiune sud(maxim20)= '); readln(limsud);

3

write('dimensiune est(maxim20)= '); readln(limest); writeln; writeln('introduceti pe linii structura labirintului'); writeln('folositi caracterele:'); writeln(' H-gard'); writeln(' .-coridor'); writeln; for i:=1 to limsud do for j:=1 to limest do begin write('pozitia',i:2, ',' ,j:2, ':'); readln(labirint[i,j]) end; writeln; writeln('labirintul propus arata astfel:'); writeln; for i:=1 to limsud do begin for j:=1 to limest do write(labirint[i,j]); writeln; end; writeln; writeln('precizati pozitia initiala'); Repeat writeln('linia (1..',limsud:2,')='); readln(startlat); write('coloana (1..',limest:2,')='); readln(startlong); writeln; Until labirint[startlat,startlong]='.';} {b)} Assign(f,'lab.in');Reset(f); readln(f,limsud,limest); for i:=1 to limsud do readln(f,labirint[i]); writeln; writeln('labirintul propus arata astfel:'); writeln; for i:=1 to limsud do writeln(labirint[i]); writeln; writeln('precizati pozitia initiala'); Repeat write('linia (1..',limsud:2,')='); readln(startlat); write('coloana (1..',limest:2,')='); readln(startlong); writeln; Until labirint[startlat,startlong]='.'; {Analiza caii de iesire} gasit:=false;

4

gasesc(startlat,startlong); {Secventa de afisare a labirintului} writeln; writeln('Labirintul rezolvat arata astfel:'); writeln; for i:=1 to limsud do begin for j:=1 to limest do begin if labirint[i,j]='H' then textcolor(green) else if labirint[i,j]='o' then textcolor(red) else if labirint[i,j]='^' then textcolor(9) else textcolor(white); write(labirint[i,j]); end; writeln; end; if not gasit then writeln('nu exista cale de iesire din labirint'); readln; End.

Prin instrucţiunea “labirint[lat,long]:=pas” mă asigur că parcelele prin care am trecut sunt marcate, evitând posibila învârtire în cerc, iar prin “labirint[lat,long]:=marcat” se evidenţiază fiecare pas parcurs pe calea spre ieşire.În acest fel în desenul final al labirintului apar trasate atât calea spre ieşire din labirint (marcată prin ‘^’) cât şi coridoarele parcurse inutil (marcate prin ‘o’) în timpul căutării.

Pentru exemplul pe care l-am arătat la labirintul iniţial voi prezenta forma finală după ce l-am parcurs pentru a găsi o ieşire: coordonate(2,2)

5

H H H H H H H H

H ^ H . H . . H

H ^ ^ . H . H H

H H ^ H ^ ^ ^ H

H H ^ ^ ^ H ^ H

H H H H o H ^ H

H o o o o H ^ H

H o H H H ^ ^ H

H o H . H ^ H H

H o H . H ^ H H

H H . . H ^ ^ ^

H H H H H H H H

Observaţii: -citirea labirintului se poate face atât din fişier cât şi de la tastatură; -am preferat citirea din fişier deoarece timpul de construcţie a labirintului este mai scurt, iar o eventuală citire de la tastatură a labirinturilor care au coordonate (sud,est) mai mari decat 12 este foarte dificilă, iar şansa de a introduce greşit caracterele este foarte mare; -am specificat in program că algoritmul funcţionează pentru coordonate (sud,est) până la 20, dar nu este nici o problemă dacă se doreşte introducerea unor coordonate mai mari, chiar mult mai mari ; -citirea de la tastatură apare şi ea în algoritm dar este ‘pusă’ între apostrofuri;

Note Realizarea acestui proiect a fost întocmită de elevul Neghină Bogdan Nicolae, elev în clasa a XII-a C,al Colegiului Naţional Vasile Lucaciu, din Baia-Mare, Maramureş.

6

Surse de inspiraţie/documentaţia: -Manualul pentru clasa a XI-XII-a Informatică- ‘Programarea calculatoarelor’. -Internet Explorer. Acest proiect a fost realizat în programul Microsoft Office Word 2003. Algoritmul ‘Labirintul’ a fost realizat cu ajutorul programului: Borland Pascal 7.0.

Sfârşit

7