�ݺ�ߣ

Backtracking Clasa X
Manualul profesorului

Software educaţional realizat de: Profesori coordonatori:
Adrian – Gabriel Diţă Corina Achinca
Şerban Nistor Cecilia Bălănescu
Rodica Cherciu

Cuprins

1. Terminologie – Prezentarea elementelor software
2. Informaţii generale despre tema prezentată
3. Obiective
4. Structura generală
4.1. Conţinut
4.2. Recomandări de structurare şi predare
5. Structura detaliată
5.1. Joc – Problema damelor
5.2. Exemplu practic: aranjarea mobilei într-o casă
5.3. Operaţii pe stivă
5.4. Exemplificarea lucrului pe stivă
5.5. Prezentarea şablonului de funcţii şi proceduri
5.6. Generarea permutărilor
5.7. Problema generării aranjamentelor
5.8. Problema damelor
5.9. Joc – Problema comis-voiajorului
5.10. Problema comis-voiajorului – rezolvare iterativă
5.11. Problema comis-voiajorului – rezolvare recursivă
5.12. Problema comis-voiajorului – implementare
5.13. Joc – Problema labirintului
5.14. Problema labirintului – rezolvare iterativă
5.15. Problema labirintului – implementare
6. Teste de evaluare
6.1. Testul 1
6.2. Testul 2
6.3. Testul 3
6.4. Testul 4
7. Teme pentru acasă
7.1. Tema 1
7.2. Tema 2
7.3. Tema 3
7.4. Tema 4
8. Bibliografie

1. Terminologie
Obiect de conţinut
Un fişier independent care prezintă informaţii grupate din punct de vedere
tematic, ce nu pot fi prezentate separat. Poate fi format din mai multe pagini de
conţinut. În cadrul acestui ghid vom folosi şi noţiunea de componentă atunci
când vom face referire la un obiect de conţinut.

Butoane start animaţie/trecere la pasul următor
Sunt amplasate în cadrul animaţiilor şi al aplicaţiilor care conţin mai mulţi
paşi. Prin apasarea acestui buton începe rularea animaţiei sau respectiv se trece
la pasul următor al animaţiei. După apăsare, acest buton se transformă în buton
de pauză, care, odată accesat întrerupe pentru moment animaţia la cadrul
curent.

Texte de reper – sunt link-uri prezente în text, evidenţiate printr-o culoare
specifică a cuvantului, care atunci când sunt accesate, oferă informaţii
suplimentare ce detaliază noţiunile respective.

Butoane teorie
Accesarea lor prezintă pas cu pas, într-o fereastră de detaliu, noţiunile
teoretice legate de lecţie, pe care cine doreşte le poate revedea pentru a
parcurge interactiv cerinţele următoare ale lecţiei.

Butoane de detaliere
Oferă informaţii suplimentare despre o anumită noţiune sau prezintă mai
în detaliu conţinutul unei părţi din lecţie, pentru cei care simt nevoia să aibă mai
multe explicaţii.

Butoane de revenire
Sunt amplasate în partea de jos a ecranului. Prin apăsarea acestui buton
se reia animaţia de la început, pentru a o studia mai bine.

Butoane de obiective
Sunt amplasate în partea de jos a ecranului şi oferă utilizatorului într-o
fereastră de detaliu, obiectivele parcurgerii materialului din modulul respectiv.

Butoane de defilare pe text
Prin apăsarea acestor butoane, textul se derulează în sensul săgeţii.

Butoane de start
Prin accesarea acestui buton se începe cronometrarea timpului în care
elevul rezolvă o anumită cerinţă.

Butoane de resetare
Se folosesc pentru reînceperea jocului în cazul în care elevul solicită acest
lucru.

Butoane de help
Oferă elevului detalii asupra modului în care trebuie să rezolve interactiv
anumite cerinţe.

Butoane de verificare
Sunt utilizate în cadrul unor probeleme care se rezolvă interactiv. În
această situaţie elevul solicită calculatorului să-i verifice corectitudinea soluţiei.

Butoane de viteză
Prin accesarea acestor butoane se stabileşte viteza de derulare a
animaţiilor in funcţie de capacitatea de înţelegere a elevului.

Ferestre de detaliu
Oferă informaţii suplimentare sau detalii despre un anumit element
(termen, concept, imagine, algoritm)
Se întâlnesc ferestre de tipul:
- urmărirea etapelor execuţiei unui algoritm elaborat în cadrul lecţiei
- indicaţii asupra modului în care trebuie rezolvate anumite cerinţe
- fereastra „Teorie” – care descrie amănunţit baza teoretică necesară
pentru rezolvarea problemelor supuse atenţiei elevului.

- fereastra „Enunţ” – redă enunţul problemei în timpul rezolvării
acesteia, dacă elevul solicită
- ferestre „Ajutor” – dau indicaţii suplimentare asupra modului interactiv
de completare a ferestrelor de dialog
- ferestre de dialog – apar în cazul în care se solicită elevului să
completeze interactiv procedurile şi funcţiile specifice metodei
backtracking pentru o problemă dată

- ferestre de stabilire a parametrilor pentru animaţie – se utilizează
pentru a „personaliza” simularea modului de execuţie a algoritmului în
funcţie de posibilităţile şi caracteristicile psiho-individuale ale elevului

2. Informaţii generale despre tema
prezentată
Produsul multimedia realizat oferă o perspectivă coerentă, unitară şi
constructivă asupra cunoaşterii, utilizării şi implementării tehnicii de programare
backtracking.
În cadrul acestei teme abordate – backtracking – au fost puse în evidenţă
următoarele aspecte:
- definirea tehnicii de programare backtracking, cu accent pe problemele care
pot fi rezolvate prin această metodă;
- prezentarea principalelor proceduri specifice metodei backtracking şi
aplicarea acestora în probleme concrete;
- formarea abilităţilor de construire a algoritmului backtracking utilizând
metode activ-participative de tip “joc”.

Cuvinte cheie la această temă sunt: funcţii, proceduri, stivă, listă,
algoritm, limbaj pseudocod/limbaj de programare, recursivitate, matrice de
adiacenţă.
Materialul are o structură modularizată care permite folosirea în mai multe
variante a intrumentelor puse la dispoziţie.
Sunt puse la dispoziţia elevului atât module de teorie referitoare la tehnica
de programare backtracking, cât şi momente de evaluare pentru realizarea unui
feedback permanent, colectiv şi care să pună în lumină progresul înregistrat de
elevi.
Fiecare lecţie conţine o temă pe care elevii trebuie să o elaboreze acasă
sau în timpul orelor de laborator.

3. Obiective
Obiectiv Detaliere
Obiective de referinţă
R1 Utilizarea corectă a noţiunilor informatice, a vocabularului informatic
aferent şi a elementelor specifice limbajului pseudocod.
R2 Prelucrarea datelor de tip calitativ şi cantitativ cuprinse în algoritmii
elaboraţi.
R3 Utilizarea corectă a algoritmilor şi a raţionamentelor în rezolvarea unor
probleme cu grade de dificultate diferite.
R4 Elaborarea etapelor de realizare a unei aplicaţii în urma analizei
acesteia.
R5 Exprimarea şi redactarea corectă a algoritmului în limbaj pseudocod sau
limbaj de programare Pascal/C++.
Obiective operaţionale
OP1 Să recunoască tipurile de probleme care se rezolvă prin tehnica
backtracking.
OP2 Să identifice principiul de funcţionare şi să recunoască părţile esenţiale
ale algoritmului: funcţii şi proceduri.
OP3 Să rearanjeze funcţiile şi procedurile pentru problema damelor.
OP4 Să interpreteze şi să stabilească valorile variabilelor utilizate în algoritm,
când se dau valorile datelor de intrare, pentru o problemă care se
rezolvă prin tehnica backtracking.
OP5 Să identifice şi să recunoască tehnica de programare backtracking
pentru o problemă dată (problema comis-voiajorului şi problema
labirintului).
OP6 Să-şi amintească procedurile de bază ale tehnicii backtracking – forma
standard (nerecursivă).
OP7 Să construiască funcţiile şi procedurile de bază ale tehnicii backtracking
şi să creeze programul principal corespunzător care le apelează.
OP8 Să modifice algoritmul creat utilizând backtracking recursiv şi să deducă
principalele schimbări care se impun prin îmbinarea celor două tehnici
de programare (backtracking – recursiv).
OP9 Fiind date valorile de intrare să inţeleagă modul de execuţie al
algoritmului construit prin backtracking recursiv.
OP10 Să compare cele două forme backtracking (recursiv – nerecursiv) din
punct de vedere al eficienţei.
OP11 Să aplice noţiunile învăţate la tehnica backtracking în plan, în problema
labirintului în care trebuie să distingă caracteristicile şi principalele
modificări din funcţiile şi procedurile standard.
OP12 Fiind date valorile de intrare în problema labirintului să înţeleagă modul
de execuţie al algoritmului construit.

OP13 Să interpreteze şi să stabilească valorile variabilelor utilizate în algoritm,
când se dau valorile datelor de intrare, pentru problema labirintului.

4. Structura generală
4.1. Conţinut
Se prezintă lista obiectelor de conţinut (notate cu M) şi caracteristicile lor
generale.

M1 – Joc – Problema damelor
Obiective didactice OP1, OP2
Timp 10 minute
Tip de interacţiune exerciţiu, problematizare, descoperire
cu elevul
Descriere - prin acest joc elevul este pus în faţa unei probleme cu date
concrete care-l determină să caute (să cerceteze) condiţiile
în care se pot aşeza patru dame pe tabla de sah.

M2 – Exeplul practic: aranjarea mobilei intr-o casa
Timp 5 minute
Tip de interacţiune expunerea, observarea, descrierea
cu elevul
Descriere - este prezentată într-o formă atractiv – captivantă
modalitatea de aşezare a mobilei într-o casă;
- animaţia realizată, observată cu atenţie, conduce la ideea
de metodă backtracking: aşezi mobila în casă în toate
modurile posibile şi o alegi pe cea care-ţi place mai mult.

M3 – Operaţii pe stivă
Obiective didactice OP2
Timp 5 minute
Tip de interacţiune expunerea, observarea, problematizarea, modelarea şi
cu elevul simularea
Descriere - se defineşte stiva şi principalele operatii care se fac pe
stivă;
- prin animaţia atractivă şi sugestivă (vraf de farfurii) elevul
înţelege mai bine mecanismul stivei (Last In – First Out):
pentru a extrage o farfurie trebuie să le scoatem pe cele
situate deasupra, iar pentru a pune o farfurie, trebuie să o
aşezăm totdeauna deasupra celorlalte.

M4 – Exemplificarea lucrului pe stivă
Timp 5 minute
Tip de interacţiune observarea, problematizarea, modelarea şi simularea
cu elevul
Descriere - apelând acest modul, elevul învaţă modul de gestionare a
unei stive. Printr-o animaţie tridimensională, elevul află:
- cum se elimină un element din stivă;
- cum se adaugă un element în stivă;
- cum se modifica un element în stivă.

M5 – Prezentarea şablonului de funcţii şi proceduri
Timp 10 minute
Tip de interacţiune explicaţia, modelarea, problematizarea
cu elevul
Descriere - în acest modul sunt prezentate funcţiile şi procedurile
standard ale tehnicii de programare backracking.

M6 – Generarea permutărilor
Obiective didactice OP2, OP2, OP3
Timp 25 minute
Tip de interacţiune observaţia, problematizarea, modelarea şi simularea
cu elevul
Descriere - modulul pune în evidenţă o succesiune de operaţii mintale
care conduc elevul spre înţelegerea clară a mecanismului
backtracking;
- permutările de trei elemente (fiind reprezentate aici de trei
melodii) sunt generate pas cu pas, în ritmul de înţelegere şi
cu respectarea stilului cognitiv, a particularitaţilor psiho-
individuale ale fiecărui elev.

M7 – Problema generării aranjamentelor de trei elemente luate câte două
Timp 10 minute
Tip de interacţiune explicaţia, exerciţiul, problematizarea, modelarea şi simularea
cu elevul
Descriere - modulul conţine un joc prin care elevul este invitat să
construiască aranjamentele de trei elemente luate câte
două.
- printr-o participare activă, elevul, aflat permanent în
interacţiune cu calculatorul, este condus spre construirea
aranjamentelor având la dispoziţie stiva şi cele patru cifre:
0 (iniţializare stivă), 1, 2 şi 3 pentru construirea
aranjamentelor corespunzătoare.

M8 – Problema damelor
Timp 15 minute
Tip de interacţiune problematizare, descoperire, exerciţiu, modelare şi simulare
cu elevul
Descriere - prezentarea problemei damelor;
- explicarea modalităţii de rezolvare a acestei probleme prin
tehnica backtracking;
- elevul are ca sarcină de lucru să aşeze în ordine secvenţele
de operaţii specifice fiecărei proceduri sau funcţii;
- după această interacţiune a elevului cu programul, urmează
o etapă de animaţie care are rolul de a exemplifica modul
de execuţie al algoritmului pentru cazul a patru dame.

M9 – Joc – Problema comis-voiajorului
Timp 10 minute
cu elevul
Descriere - este un joc atractiv care îl pune pe elev în situaţia de a
determina un ciclu hamiltonian într-un graf dat.

M10 – Problema comis-voiajorului – rezolvare iterativă
Timp 10 minute
Tip de interacţiune observare, problematizare, învăţare dirijată
cu elevul
Descriere - în acest modul se explică modalitatea de construire a
algoritmului backtracking iterativ pentru problema comis-
voiajorului;
- elevul este dirijat interactiv spre construirea funcţiilor si
procedurilor backtracking în cazul problemei comis-
voiajorului.

M11 – Problema comis-voiajorului – rezolvare recursivă
Timp 7 minute
cu elevul
Descriere - printr-o participare activă, elevul, aflat permanent în
interacţiune cu calculatorul, este condus spre înţelegerea
mecanismului de utilizare a metodei backtracking recursiv.

M12 – Problema comis-voiajorului – implementare
Timp 8 minute
Tip de interacţiune observare, problematizare, modelare şi simulare
cu elevul
Descriere - este un modul interactiv care conduce elevul spre
înţelegerea mecanismului de execuţie a algoritmului care
utilizează backtracking-ul recursiv;
- se prezintă, pas cu pas, in ritmul de înţelegere al elevului,
instrucţiunile ce se execută (modul de gestionare a stivei
soluţiilor şi stivei de recursivitate).

M13 – Joc – Problema labirintului
Timp 10 minute
cu elevul
Descriere - modulul conţine un joc – problema labirintului;
- printr-o participare activă, utilizând o animaţie captivantă,
elevul înţelege mecanismul de rezolvare a problemei
labirintului care utilizează metoda backtracking în plan.

M14 – Problema labirintului – rezolvare iterativă
Timp 10 minute
cu elevul
Descriere - în acest modul se dau detalii în legătură cu algoritmul
backtracking care trebuie construit pentru problema
labirintului;
- construirea funcţiilor şi procedurilor specifice acestei
probleme se face interactiv.

M15 – Problema labirintului – implementare
Timp 15 minute
Tip de interacţiune observare, problematizare, modelare şi simulare
cu elevul
Descriere - este un obiect de conţinut bogat în animaţii care descrie
modul de execuţie al algoritmului;
- urmărind cu atenţie acest modul interactiv, elevul îşi
clarifică şi fundamentează succesiunea de operaţii logice
prin care, implementând metoda backtracking în plan, se
poate rezolva problema labirintului.

4.2. Recomandări de structurare şi predare
Îmbinarea modulelor realizate pentru această lecţie este la latitudinea
fiecărui profesor, în funcţie de particularităţile psiho-individuale ale elevilor clasei.

1. Lecţia 1 (definirea şi înţelegerea tehnicii de programare backtracking)

Obiect de conţinut Timp (minute)
M2 5
M3 5
M4 5
M5 10
M6 10
Test 1 10
Tema 1 5

2. Lecţia 2 (implementarea tehnicii backtracking în problema damelor)

M1 10
M7 10
M8 15
Test 2 10
Tema 2 5

3. Lecţia 3 (backtracking recursiv)

M9 10
M10 10
M11 7
M12 8
Test 3 10
Tema 3 5

4. Lecţia 4 (backtracking în plan)

M13 10
M14 10
M15 15
Test 4 10
Tema 4 5

5. Structura detaliată a
conţinuturilor
5.1. Joc – Problema damelor
Acest obiect de conţinut are rolul de a familiariza elevul cu „problema
damelor”. Obiectul este interactiv şi se prezintă sub formă de joc. Elevul trebuie
să aşeze pe tabla de sah patru dame, astfel încât ele „să nu se atace”. El trebuie
să respecte regulile jocului: damele să nu fie aşezate pe aceeaşi linie, coloană
sau pe diagonală. Mutarea damelor este restricţionată de timp: elevul se va
încadra în 5 minute, perioada în care el va determina toate situaţiile posibile în
care se pot aşeza damele pe tabla de şah.

5.2. Exemplu practic: aranjarea mobilei într-o
casă
Acest modul prezintă problema aranjării mobilei într-o casă. Sunt date
obiectele care constituie mobila casei. Acestea se deplasează ocupând camerele
casei în toate modurile posibile. Animaţia atrage atenţia elevului şi-l conduce spre
aflarea unei noi metode de programare: tehnica backtracking. Prin utilizarea

butonului se începe animaţia. Aceasta se poate relua, ori de câte ori doreşte

elevul, apasând butonul .

5.3. Operaţii pe stivă
Acest obiect este interactiv şi are ca scop definirea noţiunii de stivă,
precum şi a operaţiilor ce se pot face cu elementele unei stive: adăugarea şi
scoaterea unui element din stivă. Elevul are la dispoziţie următoarele butoane:

– declanşează animaţia, care prezintă cât se poate de sugestiv ce este o
stivă

– reia animaţia pentru o înţelegere cât mai bună.
În timpul animaţiei, elevul participă activ la înţelegerea definiţiei, utilizând
aceleaşi butoane.

5.4. Exemplificarea lucrului pe stivă
Este un obiect de conţinut interactiv, care conduce elevul la fixarea
cunoştinţelor privind operaţiile efectuate pe stivă şi modul în care se realizează
ele pe un exemplu concret.

Interactivitatea se realizează prin intermediul unor butoane , ,

, care permit declanşarea animaţiei, oprirea acesteia şi reluarea la momentul
următor, în funcţie de posibilitatea de întelegere a elevului. Iniţial stiva conţine
un element A. La adăugarea unui nou element B, se observă că acesta este
aşezat primul. Dacă dorim să eliminăm din stivă elementul A, trebuie mai întâi să
fie scos elementul B şi apoi elementul A. Animaţia, grafica, culorile, sunt realizate
pentru a păstra echilibrul psihologic, atractiv – captivant şi astfel elevul să fie
condus către o percepere optimă a lucrului pe stivă.

5.5. Prezentarea şablonului de funcţii şi
proceduri
În acest obiect sunt prezentate procedurile şi funcţiile specifice metodei
backtracking: succesor, validare, init, soluţie şi tipar. Acestea sunt prezentate în
pseudocod şi vor fi completate în funcţie de problema pe care elevul o are de
rezolvat. Se recomandă înainte de studierea acestor proceduri, să se studieze cu
multă atenţie teoria legată de backtracking, care poate fi accesată prin utilizarea
butonului .

5.6. Generarea permutărilor
Acest obiect este interactiv. Rolul lui este de a exemplifica modul de
gestionare a stivei într-o problemă concretă de backtracking: construirea
permutărilor de trei elemente. Elevul urmăreşte modalitatea de umplere a stivei,
după tehnica backtracking. În paralel, se evidenţiază operaţiile care se execută în
algoritmul backtracking şi astfel elevul face corelaţia între gestionarea stivei şi
logica acestei tehnici de programare.

Respectând particularităţile psiho-individuale ale elevului, obiectul conţine
două butoane cu care animaţia se poate relua, opri sau continua. Prin
interacţiunea elevului cu programul este pusă în lumină succesiunea de operaţii
mintale care conduc la construirea celor şase permutări.

5.7. Problema generării aranjamentelor
Este un obiect interactiv sub forma unui joc. Elevul are la dispoziţie
elementul 0 (pentru iniţializarea stivei) şi 1, 2, 3 cu care să construiască
aranjamente de două elemente. Se evidenţiază astfel principiul backtracking şi se
realizează o auto-evaluare a elevului în ceea ce priveşte corectitudinea înţelegerii
acestei tehnici de programare.

În momentul în care elevul a încărcat greşit stiva, este atenţionat şi i se
precizează precedura din schema backtacking care nu a fost apelată.

5.8. Problema damelor
Acest moment al lecţiei este un moment interactiv şi are ca scop
rezolvarea problemei damelor prin tehnica backtacking. Elevului i se prezintă
operaţiile ce se execută în cadrul algoritmului backtracking pentru această
problemă. El trebuie să identifice operaţiile pentru fiecare procedură. Dacă
alegerea nu este bine făcută, primeşte indicaţii şi este condus spre rezolvarea
corectă a problemei. După stabilirea procedurilor, începe implementarea
algoritmului pentru cele patru dame. La fiecare pas se explică elevului operaţiile
care se efectuează în algoritm, până la găsirea completă a tuturor soluţiilor.

5.9. Joc – Problema comis-voiajorului
Este un obiect de conţinut interactiv, de tip joc.
Există o interacţiune permanentă a elevului cu calculatorul pentru găsirea
drumului pe care trebuie să-l parcurgă comis-voiajorul; el trebuie să respecte
următoarele reguli:
- să viziteze toate casele
- să treacă o singură data pe la fiecare casă
Jocul începe în momentul în care elevul accesează butonul . În
acest moment se declanşează cronometrul şi rezolvarea problemei trebuie să se
facă în 7 minute. Dacă elevul a greşit traseul, există butonul care îi
permite să reia totul de la început. În momentul găsirii soluţiei, elevului i se
comunică timpul în care a găsit drumul căutat. Utilizând butonul se
reamintesc o serie de noţiuni necesare elaborării algoritmului problemei. Butonul
comunică elevului ce competenţe dobândeşte în urma parcurgerii
acestui set de module.

5.10. Problema comis-voiajorului – rezolvare
iterativă
Acest obiect de conţinut are rolul de a elabora algoritmul rezolvării
problemei comis-voiajorului prin metoda iterativă. Elevul este solicitat să rezolve
interactiv problema. Din ferestrele procedure şi respectiv function îşi alege pe
rând fiecare din acestea, pe care le completează cu instrucţiunile pseudocod
specifice problemei comis-voiajorului.

Butonul trebuie accesat înaintea construirii procedurilor. În acest
moment se deschide fereastra „Ajutor” care oferă indicaţii cu privire la modul în
care se completează procedurile şi funcţiile pentru implementarea iterativă a
metodei backtracking.

5.11. Problema comis-voiajorului – rezovare
recursivă
Prin parcurgerea acestui modul, elevul îşi formează deprinderea de a
utiliza metoda backtracking în forma recursivă. Este un obiect de conţinut
interactiv.
Se deschid două ferestre de dialog: function succesor si procedure
bkt(k). Cele două proceduri se completează de către elev, care urmăreşte în
continuare noţiunile teoretice prin folosirea butonului .

În cadrul ferestrelor există butonul . Prin accesarea lui, elevul
primeşte răspuns dacă a rezolvat corect sau nu cerinţa. În cazul în care
rezolvarea este incorectă, are dreptul la un numar maxim de 6 încercări. În final,
dacă nu găseşte rezolvarea corectă i se oferă soluţia şi este atenţionat că nu a
reuşit să descopere singur varianta corectă.

5.12. Problema comis-voiajorului –
implementare
Prin acest obiect de conţinut se pune în evidenţă succesiunea de
operaţii/instrucţiuni care se execută în cadrul algoritmului backtracking recursiv
pentru problema comis-voiajorului.
Este un obiect de conţinut interactiv. Elevul urmăreşte pas cu pas modul
de construire a soluţiilor pe „stiva soluţiilor” şi în acelaşi timp poate vizualiza
modul de gestionare a segmentului de stivă ataşat recursivităţii.
Animaţia se desfăşoară automat sau poate fi condusă de elev, în ritmul pe
care îl doreşte, stabilind prin intermediul ferestrei de dialog „viteza de rulare”.

5.13. Joc – Problema labirintului
Este un moment interactiv de tip joc. Acesta captează atenţia elevului care
trebuie să se deplaseze printr-un anumit labirint. Animaţia atractivă şi captivantă
conduce la înţelegrea problemei şi a mecanismului backtracking în plan.

Explicaţia jocului se obţine prin accesarea butonului , iar butonul
foloseşte pentru fixarea vitezei de deplasare a cavalerului în funcţie de ritmul de
înţelegere al elevului.

5.14. Problema labirintului – rezolvare iterativă
Se explică elevului modul în care sunt memorate datele de intrare în
problema labirintului. Acest lucru se obţine dacă facem click pe grupul de cuvinte
„Matricea de adiacenţă”. În acest caz sunt prezentate datele de intrare şi
codificarea acestora.
În secvenţa principală, făcând click pe procedurile init, succesor şi tipar,
se deschid ferestre de dialog care solicită atenţia elevului şi îl antrenează în
completarea acestora.

5.15. Problema labirintului – implementare
În acest moment al lecţiei, elevul este dirijat spre înţelegerea logică a
modului de execuţie a algoritmului elaborat la pasul anterior.
Aşezând mouse-ul pe suprafeţele matricei situată în partea dreaptă sus,
sunt explicate elevului codificările pentru sensul de deplasare.

Există de asemenea butonul care fixează viteza de derulare a
animaţiei.
Declanşarea animaţiei, în cazul în care ea nu este automată, este condusă
de elev prin mouse. Este simulat modul de gestionare a valorilor ce indică poziţia
cavalerului în ficare moment: linia, coloana şi direcţia.
Aceste valori sunt trecute în trei stive, reprezentate tridimensional, iar la
găsirea unei soluţii, acestea sunt exemplificate pe matricea de adiacenţă.
Simularea etapelor de găsire a soluţiilor, exemplifică elevului succesiunea de
operaţii mintale care conduc la descoperirea rezultatului.

6. Teste de evaluare
6.1. Testul 1
Problema 1
Punctaj: 1 Timp: 1 minut Obiectiv: OP2
Enunţul problemei:
Dacă pentru nivelul k oarecare al vectorului soluţie am verificat toate valorile
posibile:
a) algoritmul se încheie
b) se revine pe nivelul anterior
c) se trece pe nivelul următor

Problema 2
Enunţul problemei:
După ce s-a găsit o valoare convenabilă pentru componenta k, următorul pas
este:
a) se trece la componenta următoare (k+1), dacă nu s-a ajuns la o soluţie
b) se rămâne la componenta k, căutând în continuare o altă valoare convenabilă
c) se revine la componenta k-1

Problema 3
Enunţul problemei:
În ce condiţii se revine la componenta anterioară?
a) după ce am găsit o valoare convenabilă pentru componenta k
b) dacă valoarea testată pentru componenta k nu convine
c) dacă am testat toate valorile posibile pentru componenta k

Problema 4
Enunţul problemei:
În ce condiţii se trece de la componenta k la componenta k+1?
a) după ce am găsit o valoare convenabilă pentru componenta k
b) după ce am testat toate valorile posibile pentru componenta k
c) dacă nu am găsit nici o valoare convenabilă pentru componenta k

Problema 5
Enunţul problemei:
Iniţializarea componentei st[k] se realizează:
a) când se trece de pe nivelul k-1 pe nivelul k
b) când se revine de pe nivelul k+1 pe nivelul k
c) când pe nivelul k+1 au fost testate toate valorile posibile

Problema 6
Enunţul problemei:
Algoritmul se încheie dacă:
a) s-au testat toate valorile posibile pentru primul nivel
b) s-au testat toate valorile posibile pentru ultimul nivel
c) pe un nivel oarecare, k, nu am găsit nici o valoare care să verifice condiţiile de
continuare

Problema 7
Enunţul problemei:
După găsirea unei soluţii, pasul următor este:
a) se revine pe nivelul anterior
b) se rămâne pe acelaşi nivel, testându-se următoarea valoare disponibilă
c) se încheie algoritmul

Problema 8
Enunţul problemei:
În cazul stivei, întotdeauna se permite accesul direct la:
a) prima componentă introdusă
b) ultima componentă introdusă
c) toate componentele sale

Problema 9
Enunţul problemei:
Se dă o stivă implementată cu ajutorul unui vector S. În stivă s-au introdus, în
această ordine, numerele 1 si 2; S=(1,2). Dacă se noteaza cu PUSH(n) operaţia
prin care se adaugă informaţia x în stivă şi cu POP operaţia prin care se scoate
un element din stivă, care este rezultatul operaţiilor:
POP, PUSH(3), PUSH(6), POP, PUSH(5)
a) S=(3,6,5)
b) S=(3,6,5)
c) S=(1,3,5)

6.2. Testul 2
Problema 1
Punctaj: 1 Timp: 1 minut Obiectiv: OP1, OP2, OP4
Enunţul problemei:
Se citesc n şi p numere naturale, n>=p. Să se genereze toate submulţimile cu p
elemente ale mulţimii {1,2,......n}.
Care este numărul maxim de elemente din stivă?
a) n
b) p
c) n+p

Problema 2
Punctaj: 1 Timp: 1 minut Obiectiv: OP1, OP2, OP4
Enunţul problemei:
Care este condiţia de validare?
a) elementele puse în stivă să fie consecutive
b) elementele puse în stivă să fie nenule
c) elementele puse în stivă să fie distincte

Problema 3
Enunţul problemei:
Pentru a evita repetiţia, elementele se aşează în stivă în ordine crescătoare: pe
nivelul k se va afla o valoare mai mare decât pe nivelul k-1 şi mai mică decât n-
p+k.
Folosind cunoştiinţele acumulate, alege secvenţa de cod pentru următorul
subprogram:
procedure init(k,st)
if k>1 then ...
a) st[k]<-1
b) st[k]<-st[k+1]
c) st[k]<-st[k-1]
d) st[k]<-0

Problema 4
Punctaj: 1 Timp: 1 minut Obiectiv: OP2, OP4
Enunţul problemei:
p+k.
subprogram:
procedure init(k,st)
if k>1 then st[k]<-st[k-1]
else if k=1 then ...
endif
a) st[k]<-1
b) st[k]<-st[k+1]
c) st[k]<-st[k-1]
d) st[k]<-0

Problema 5
Enunţul problemei:
p+k.
subprogram:
procedure succesor(k,st,as)
if ... then
st[k] <- st[k]+1
as <- true
else as <- false
endif
a) st[k]<n-p+k
b) st[k]<n+p-k
c) st[k]<n
d) st[k]<=n-p+k

Problema 6
Enunţul problemei:
p+k.
subprogram:
procedure validare(k,st,ev)
...
a) ev<-true
for i<-1,k-1 do
if st[k]=st[i] then ev<-false
endif
b) ev<-true
c) ev<-true
if st[k]=st[n] then ev<-false
endif
d) ev<-true
if st[k]=st[k-1] then ev<-false
endif

Problema 7
Enunţul problemei:
În cazul problemei damelor pe tabla de şah:
a) mulţimile S1, S2,..., Sn coincid
b) elementele s1, s2,..., sn coincid
c) mulţimile S1, S2,..., Sn sunt distincte

Problema 8
Enunţul problemei:
Tabloul în care se reţine soluţia pentru problema aranjamentor este de fapt:
a) un tablou bidimensional
b) o coadă
c) nici una din variantele de mai sus

Problema 9
Enunţul problemei:
Costel a implementat metoda backtracking pentru a tipări toate cuvintele formate
cu cele cinci litere ale cuvântului ASTRU. Programul tipăreşte un şir de cuvinte
separate prin spaţiu în ordinea alfabetică. Care este cuvântul tipărit chiar în faţa
cuvântului RASTU?
a) SUART
b) RASUT
c) SUTRA
d) RAUTS

6.3. Testul 3
Problema 1
Punctaj: 1 Timp: 1 minut
Enunţul problemei:
Fie un program care implementează metoda backracking pentru determinarea
numerelor naturale cu ajutorul cifrelor 1,2,3,4,5. Numerele vor conţine toate cele
5 cifre distincte şi vor fi construite în ordine crescătoare. Ce număr va fi tipărit
după 31245?
a) 25413
b) 31254
c) 25431
d) 21345

Problema 2
Enunţul problemei:
Fie un program care implementează metoda backtracking pentru determinarea
5 cifre distincte şi vor fi construite în ordine crescătoare. Câte numere tipăreşte
programul?
a) mai puţin de 100
b) 100
c) 120
d) mai mult de 120

Problema 3
Enunţul problemei:
5 cifre distincte şi vor fi construite în ordine crescătoare. Numărul 21453 va fi
tipărit:
a) al 20-lea
b) al 28-lea
c) al 31-lea
d) nu se poate preciza

Problema 4
Enunţul problemei:
5 cifre distincte şi vor fi construite în ordine crescătoare. Înaintea numărului
31245 va fi tipărit numărul:
a) 25413
b) 31254
c) 25431
d) 21345

Problema 5
Enunţul problemei:
În utilizarea tehnicii backtracking, varianta recursivă:
a) revenirea din autoapel este echivalentă cu trecerea la nivelul urmator din
varianta nerecursivă
b) revenirea din autoapel este echivalentă cu trecerea la nivelul anterior din
varianta recursivă
c) nu se revine niciodată la nivelul anterior
d) se revine la nivelul anterior la încheierea algoritmului

Problema 6
Enunţul problemei:
În probleme care utilizează backtracking recursiv, care din următoarele afirmaţii
este adevărată?
a) funcţia back se autoapelează pentru valoarea următoare a aceluiaşi nivel din
stivă
b) funcţia back se autoapelează pentru următorul nivel din stivă
c) funcţia back se autoapelează pentru nivelul următor din stivă fără a mai găsi
succesorul elementului
d) funcţia back se autoapelează fără a se ţine seama de nivelul din stivă

Problema 7
Enunţul problemei:
În problema damelor, se implementează metoda backtracking recursiv.
Procedura bkt afişează toate modalităţile posibile de aşezare a 4 dame pe tabla
de şah.
Funcţia validare testează dacă valoarea pusă pe nivelul k a generat o soluţie
validă, returnând true sau false.
Puneţi în locul punctelor de suspensie variante potrivite (scrierea este în
pseudocod).
function validare(k)
posibil<-true
for i=1,k-1 do
if ... then posibil<-false
endif
endfor
validare<-posibil
return
a) (st[k]=st[i]) and (abs(st[k]-st[i])=abs(k-i))
b) (st[k]=st[i]) or (abs(st[k]-st[i])=abs(k-i))
c) (st[k]<>st[i]) and (abs(st[k]-st[i])=abs(k-i))
d) (st[k]<>st[i]) or (abs(st[k]-st[i])=abs(k-i))

Problema 8
Enunţul problemei:
În problema damelor, se implementează metoda backtracking recursiv.
Procedura bkt afişează toate modalităţile posibile de aşezare a 4 dame pe tabla
de şah.
Puneţi în locul punctelor de suspensie varianta potrivită:
procedure bkt(k)
for i=1,4 do
....
endfor
return
a) if k=1 then tipar
else for i=1,4 do
st[k]<-i
bkt(k+1)
endfor
endif

b) st[k]<-i
if valid(k) then
if k=5 then tipar
else bkt(k+1)
endif
endif
c) if k<4 then
for i=1,4 do
st[k]<-i
bkt(k+1)
endfor
else tipar
endif

Problema 9
Enunţul problemei:
În procedura BKT se afişează toate elementele produsului cartezian MxMxMxM
unde M={1,2,...n}; st este un vector de numere întregi, iar procedura tipar
afişează elementele st[1],st[2],...st[4].
procedure bkt(k)
...
return
Alegeţi din variantele de mai jos secvenţa care trebuie aşezată în locul punctelor
de suspensie pentru a obţine un rezultat eronat la apelul bkt(1).
a) for i=1,4 do
st[k]<-i
if k=n then tipar
else bkt(k+1)
endif
endfor
b) if k=4 then tipar
else for i=1,4 do
st[k]<-i
bkt(k+1)
endfor
endif
c) if k<5 then for i=1,n do
st[k]<-i
bkt(k+1)
endfor
else tipar
endif

6.4. Testul 4
Problema 1
Enunţul problemei:
Pe o tablă de şah de dimensiune mxn se găseşte un cal în poziţia (l0, c0). Se
încearcă determinarea tuturor modalităţilor prin care acesta poate să treacă de 2
ori prin acelaşi loc ştiind că un cal situat într-un punct dat poate sări în 8 direcţii
afişate în figura alăturată.

8 1

7 2

*

6 3

5 4
Care dintre următoarele afirmaţii este adevărată:
a) vectorul soluţie are n componente
b) vectorul soluţie are m componente
c) vectorul soluţie are mxn componente

Problema 2
Enunţul problemei:
Din punctul k, caracterizat de coordonatele (st[k].l, st[k].c) se poate ajunge într--
unul din punctele:
a) (st[k].l-1, st[k].c+1)
b) (st[k].l-2, st[k].c+1)
c) (st[k].l-1, st[k].c+2)
d) (st[k].l+1, st[k].c+1)
e) (st[k].l+1, st[k].c+2)
f) (st[k].l-2, st[k].c+2)

Problema 3
Enunţul problemei:
Alegeţi varianta corectă de scriere pentru procedura init, unde (l1, c1) reprezintă
poziţia căsuţei de pe tablă unde calul se poate deplasa în mod valid din poziţia k-
1.
a) procedure init(k)
st[k].l<-l0
st[k].c<-c0
return
b) procedure init(k)
st[k].d<-0
return
c) procedure (k)
st[k].d<-1
if k=1 then st[k].l<-l0
st[k].c<-c0
else st[k].l<-l1
st[k].c<-c1
return
d) procedure (k)
st[k].d<-0
if k=1 then st[k].l<-l0
st[k].c<-c0
else st[k].l<-l1
st[k].c<-c1
return

Problema 4
Enunţul problemei:
Dacă (l, c) reprezintă o poziţie validă a calului atunci alegeţi condiţia corectă:
a) (l>1) or (c>1) or (l>m) or (c>n)
b) (l>1) and (c>1) and(l>m) and (c>n)
c) (l>1) and (c>1) and (l<m) and (c<n)
d) (l>=1) and (c>=1) and (l<=m) and (c<=n)

Problema 5
Enunţul problemei:
Determinaţi condiţiile corecte de continuare ce trebuiesc îndeplinite de procedura
valid:
a) poziţia aleasă nu trebuie să fie în afara tablei de şah
b) calul nu trebuie să se întoarcă la punctul de unde tocmai a venit dar poate
reveni mai târziu în acest punct
c) calul nu poate trece de mai multe ori prin acelaşi loc

Problema 6
Punctaj: 2 Timp: 2 minute
Enunţul problemei:
Alegeţi varianta corectă de scriere a funcţiei solutie:
a) function solutie(k)
if k=m*n then solutie<-true
else solutie<-false
endif
return
b) function solutie(k)
if k=m then solutie<-true
else solutie<-false
endif
return
c) function solutie(k)
if k=m then solutie<-true
else solutie<-false
endif
return

Problema 7
Punctaj: 2 Timp: 2 minute
Enunţul problemei:
Alegeţi varianta corectă de scriere a procedurii tipar:
a) procedure tipar(k)
write(st[k].l, st[k].c)
return
b) procedure tipar(k)
for i=1, n do write(st[i],l, st[k].c) endfor
return
c) procedure tipar(k)
for i=1, k do write(st[i].l) write(st[i].c) endfor
return

7. Teme pentru acasă
7.1. Tema 1

Problema 1

Fie n cuburi, etichetate de la 1 la n (n ≤ 200) de laturi Li, şi culori Ci, i=1...n. Să
se aranjeze cele n cuburi în turnuri de k cuburi, astfel încât să fie stabile ( nu se
va aranja un cub mai mare peste un cub mai mic), iar culorile cuburilor alăturate
trebuie să fie diferite.
Să se descrie algoritmul de rezolvare a problemei date folosind tehnica
backtracking.
Indicaţie: - pentru introducerea datelor se foloseşte o matrice a cuburilor cu n
linii şi două coloane ) pe prima coloană latura cubului, iar pe coloana
a doua culoarea).

Problema 2

Să se determine toate modurile în care se poate perfora un bilet de autobuz. Un
bilet are 9 puncte de perforare posibile:
* * *
* * *
* * *
Un bilet poate fi introdus în aparat pe o singură faţă.

7.2. Tema 2

Problema 1

Determinaţi toate modurile de scriere a unui număr natural ca sumă de numere
prime distincte.
Indicaţie: - Se generează într-un tablou unidimensional toate numerele prime
mai mici decât numărul dat.

Problema 2

Se consideră o mulţime cu n elemente şi un număr natural k nenul.
Să se calculeze câte submulţimi cu k elemente satisfac pe rând condiţiile de mai
jos şi să se afişeze aceste submulţimi.
a) conţin p obiecte date;
b) nu conţin nici unul din q obiecte date;
c) conţin exact un obiect din p obiecte date;
d) conţin r obiecte din p obiecte date dar nu conţin alte q obiecte.

7.3. Tema 3
Problema 1

Câştigătorul unui premiu în valoare de v lei poate să aleagă din n tipuri de
obiecte în valoare de v1, v2,...,vn, astfel încât obiectele alese să aibă valoarea
totală v. Ştiind că există m1 obiecte de tipul 1, m2 obiecte de tipul 2,..., mn
obiecte de tipul n, determinaţi toate alegerile posibile ce îndeplinesc condiţia
cerută.

Problema 2

O caravană formată din n cămile călătoreşte prin deşert în şir indian. Beduinul se
hotărăşte să schimbe aşezarea cămilelor astfel încât fiecare cămilă să nu mai
vadă în faţa ei aceeaşi cămilă de pâna atunci. Care sunt posibilităţile de a aşeza
cămilele?

7.4. Tema 4
Problema 1

Un cal şi un rege se află pe o tablă de şah. Unele câmpuri ale tablei sunt "arse",
poziţiile lor fiind cunoscute. Calul nu poate călca pe câmpuri "arse", iar orice
mişcare a calului face ca respectivul câmp să devină "ars". Să se afle dacă există
o succesiune de mutări permise (cu restricţiile de mai sus), prin care calul să
poată ajunge la rege şi să revină la poziţia iniţială. Poziţia iniţială a calului,
precum şi poziţia regelui sunt considerate "nearse".

Problema 2

Se dă un caroiaj dreptunghiular de n linii şi n coloane. În fiecare celulă se află un
număr întreg din intervalul [0, 15] a cărui reprezentare binară pe 4 poziţii indică
ieşirile posibile spre celulele alăturate în ordinea N, E, S, V. Ieşirea intr-o anumită
direcţie este posibilă dacă şi numai dacă bitul corespunzător acelei direcţii este 1.
Să se elaboreze un program recursiv care să determine dacă dintr-o celulă
oarecare a caroiajului, ale cărui coordonate sunt cunoscute, se poate ieşi în afara
lui. În caz afirmativ se vor afişa toate drumurile posibile numerotând solutţiile.
Indicaţie: Dacă numărul dintr-o celulă este 11 atunci reprezentarea binară va fi
1011 şi deci direcţiile posibile sunt N, S şi V.

8. Bibliografie:
Informatică: - clasa a x-a – Tudor Sorin – Editura L&S
Informatică: - clasa a x-a – George Daniel Mateescu – Editura Petrion
Pavel Florin Moraru
Otilia Sofran
Informatică: - Probleme propuse şi rezolvate – Rodica Cherciu - Editura Niculescu
Dan Grigoriu
Irina Iosupescu
Cecilia Bălănescu
Simona Petrescu
Marcel Homorodean

�ݺ�ߣ

Manualul profesorului

More Related Content

Manualul profesorului