backtracking clasa x manualul...

Backtracking Clasa X Manualul profesorului

Software educaţional realizat de: Adrian – Gabriel Diţă Şerban Nistor

Profesori coordonatori: Corina Achinca

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

cu elevul exerciţiu, problematizare, descoperire

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 Obiective didactice OP1, OP2


cu elevul expunerea, observarea, descrierea

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


cu elevul expunerea, observarea, problematizarea, modelarea şi 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ă Obiective didactice OP2, OP4


cu elevul observarea, problematizarea, modelarea şi simularea

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 Obiective didactice OP1, OP2


cu elevul explicaţia, modelarea, problematizarea

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


cu elevul observaţia, problematizarea, modelarea şi simularea

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ă Obiective didactice OP2, OP3, OP4


cu elevul explicaţia, exerciţiul, problematizarea, modelarea şi simularea

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 Obiective didactice OP2, OP3, OP4


cu elevul problematizare, descoperire, exerciţiu, modelare şi simulare

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 Obiective didactice OP5, OP6



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ă Obiective didactice OP5, OP6, OP7


cu elevul observare, problematizare, învăţare dirijată

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ă Obiective didactice OP7, OP8, OP9



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 Obiective didactice OP8, OP9, OP10


cu elevul observare, problematizare, modelare şi simulare

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 Obiective didactice OP1, OP5



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ă Obiective didactice OP6, OP11, OP12



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 Obiective didactice OP11, OP12, OP13


cu elevul observare, problematizare, modelare şi simulare

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)

Obiect de conţinut Timp (minute)

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


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


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


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


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


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


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


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


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: 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 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


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}. 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: Se citesc n şi p numere naturale, n>=p. Să se genereze toate submulţimile cu p elemente ale mulţimii {1,2,......n}. 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 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


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}. 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 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


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}. 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 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


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


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


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 Punctaj: 1 Timp: 1 minut Enunţul problemei: Fie un program care implementează metoda backtracking 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. Câte numere tipăreşte programul? a) mai puţin de 100 b) 100 c) 120 d) mai mult de 120

Problema 3 Punctaj: 1 Timp: 1 minut Enunţul problemei: Fie un program care implementează metoda backtracking 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. 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 Punctaj: 1 Timp: 1 minut Enunţul problemei: Fie un program care implementează metoda backtracking 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. Înaintea numărului 31245 va fi tipărit numărul: a) 25413 b) 31254 c) 25431 d) 21345

Problema 5 Punctaj: 1 Timp: 1 minut 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 Punctaj: 1 Timp: 1 minut 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 Punctaj: 1 Timp: 1 minut 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 Punctaj: 1 Timp: 1 minut 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 Punctaj: 1 Timp: 1 minut 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 Punctaj: 1 Timp: 1 minut 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 Punctaj: 1 Timp: 1 minut 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 Punctaj: 1 Timp: 1 minut 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 Punctaj: 1 Timp: 1 minut 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 Punctaj: 1 Timp: 1 minut 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

backtracking clasa x manualul...

Documents