PROIECT DIDACTIC

Proiect didactic Clasa a XI-a

PROIECT DIDACTIC

Lecie pentru dobndire de noi cunotine

Data: 27 aprilieUnitatea de nvmnt: Colegiul Naional Gheorghe incai Baia MareDisciplina: InformaticClasa: a XI-a B (matematic-informatic, intensiv informatic)Profesor: prof. Carmen ANTONUnitatea de nvare: Structuri dinamice de dateTema: Liste circulareDurata: 1 or Locul de desfurare: sala de clas Nivelul iniial al clasei:

elevii i-au nsuit toate noiunile legate de utilizarea tipului pointer i diferenelor la nivel teoretic dintre structuri statice de date i structuri dinamice de date;

elevii cunosc operaiile elementare de lucru cu liste liniare simplu nlnuite;

elevii utilizeaz corect operaiile specifice acestora;

Obiectiv cadru:

Realizarea de aplicaii specifice alocrii dinamice i structurilor de date i anume listele circulare.

Obiectiv de referin:

a) S-i formeze deprinderi de lucru specifice temei de studiu;

b) S elaboreze algoritmi pentru problemele propuse utiliznd noua structur de dat;

c) S aplice algoritmi utiliznd limbajul de programare Borland Pascal;

d) S prelucreze date utiliznd listele circulare, folosind algoritmii nvai.

e) S asimileze operaiile specifice acestora; n lecia de fa reprezentarea, crearea i tiprirea unei liste;

f) S depaneze programele n cazul unor eventuale erori.

Obiective educaionale:

s defineasc corect subprogramele specifice listelor;

s recunoasc aplicaiile care necesit lucrul cu aceste structuri;

s tie s analizeze problemele din punctul de vedere al alocrii memoriei i reprezentrii datelor;

s argumenteze corect alegerea acestora;

s se autoevalueze n raport cu obiectivele i cu clasa;

s deosebeasc o structur static de una dinamic;

s implementeze algoritmii ntr-un limbaj de programare (Pascal);

Obiective operaionale:

O1:s declare corect o structur de tip list;

O2:s-i nsueasc modul de reprezentare i funcionare a listelor circulare;O3:s tie s declare i s defineasc subprogramele de creare i parcurgere a unei liste circulare;

O4:s analizeze corect o problem i s defineasc i s scrie corect un program care s utilizeze o list circular.STRATEGII DIDACTICE:

Principii didactice:

Principiul participrii i nvrii active;

Principiul asigurrii progresului gradat al performanei;

Principiul conexiunii inverse;

Metode de nvmnt:

Explicaia, conversaia, exerciiul, problematizarea, algoritmizarea;

Exerciiul, nvarea prin descoperire, modelarea.

Procedee de instruire:

Explicaia n etapa de comunicare;

Problematizarea prin crearea situaiilor problem;

nvarea prin descoperire;

Forme de organizare: frontal i individual;

Forme de dirijare a nvrii: dirijat de profesor i independent;

Resurse materiale:

tabla, fie de lucru individuale.

Material bibliografic:

Tudor Sorin, Manual de Informatic-varianta Pascal, Editura L&S Infomat, Bucureti, 2002;

Carmen Popescu, Culegere de probleme de Informatic, Editura Donaris, Sibiu, 2002;

Mihaela Veronica Stan .a., Algoritmi - Culegere de probleme clasa a XI-a, Editura L&S Soft, Bucureti, 2004

Metode de evaluare:

ntrebri orale; R.A.I. modificat; Test gril;

List de probleme;

Desfurarea activitii:

Moment organizatoric

Din aceast categorie fac parte urmtoarele activiti: pregtirea leciei (a proiectului didactic, a setului de ntrebri i aplicaii), organizarea i pregtirea clasei (frecvena la ore), captarea ateniei (anunarea temei i modului de desfurare a orei).

Reactualizarea cunotinelor

Verificarea cunotinelor anterioare se va realiza cu ajutorul unui test gril care conine 4 ntrebri legate de listele liniare simplu nlnuite (fia numrul 1). mprirea cerinelor i a ntrebrilor se va face ca ntr-o list circular, unor elevi din clas li se va da cte un bileel cu enunul ntrebrii, variantele de rspuns i numele urmtorului elev care va rspunde la ntrebare. Fia numrul 1

CerineRspunsuri corecte

1. Se consider c variabila cap memoreaz adresa de nceput a unei liste liniare simplu nlnuite L. Orice element al listei memoreaz ntr-un cmp numit adr adresa elementului urmtor. Care dintre urmtoarele expresii reprezint adresa celui de-al treilea element al listei.

a. cap^.adr^.adr

b. cap^.adr^.adr^

c. cap^.adr

d. cap.adr^.adr^

2. La adresele p i u sunt memorate primul, respectiv ultimul element al unei liste liniare simplu nlnuite L. Orice element al listei memoreaz n cmpul adr adresa elementului urmtor. Care dintre urmtoarele atribuiri interschimb informaiile dintre cele dou elemente ale listei? (aux este o variabil de acelai tip cu p i u)a. aux:=p; p:=u; u:=p;b. aux^.inf:=p^.inf; p^.inf:=u^.inf; u^.inf:=p^.inf;

c. aux^.inf:=p^.inf; p^.inf:=u^.inf; u^.inf:=aux^.inf;

d. p:=u; u:=p;3. O list liniar simplu nlnuit format din cel puin 10 elemente are adresa de nceput memorat iniial n variabila p. n cmpul ref al fiecrui nod al listei se memoreaz adresa elementului urmtor. Pentru a reine n p adresa penultimului element al listei se execut secvena:

a. while pnil do p:=p^.ref

b. while p^.refnil do p:=p^.ref

c. while p^.ref^.refnil do p:=p^.ref

d. while p^.ref^nil do p:=p^.ref

4. O list liniar simplu nlnuit, cu adresa de nceput memorat n variabila p este vid dac:

a. p^=nil

b. p=nil

c. p=0

d. p^=01. a

2. c

3. c

4. b

Comunicarea noilor cunotine

Se precizeaz titlul leciei i se trece la explicarea noiunii, declararea unui astfel de tip structurat de dat i operaiile posibile cu aceasta precum i necesitatea utilizrii ei n aplicaiile de programare. n cadrul explicaiilor se vor utiliza i modele grafice ale noiunii prezentate.

Listele circulare (figura 1) sunt liste liniare simplu nlnuite la care la cmpul de adres al ultimului nod al listei se memoreaz adresa primului nod din list.

prim

inf urm inf urm inf urm

inf 1 adr2

inf2 adr3

infn adr1 adr1 adr2

. adrn

Figura 1. Lista circular simplu nlnuit

n figura 1:

inf1, inf2, , infn reprezint informaia din noduri;

adr1, adr2, , adrn reprezint adresele elementelor listei;

fiecare nod conine adresa nodului urmtor.

Declaraia listei circulare cu elemente ce conin informaie de tip ntreg n limbajul Pascal este:

Type

adresa=^nod;

nod=record

inf:integer;

urm:adresa;

end;

Var

prim,p:adresa;

Variabila prim memoreaz adresa primului element al listei circularea, iar p este o variabil reper care memoreaz adresa unor variabile de tipul nod declarat. Referirea la un cmp din cadrul unui nod oarecare de la dresa p se face astfel:

p^.inf refer cmpul care conine informaia pentru care se definete lista;

p^.urm conine adresa urmtorului nod din list (pentru ultimul nod, acest cmp conine adresa primului nod).

Operaiile care se efectueaz cu listele circulare sunt: crearea listei, parcurgerea listei, inserarea unui element n list i tergerea unui element din list.

n plus fa de listele liniare simplu nlnuite, crearea listelor circulare presupune legarea ultimului element al listei de primul creat, operaie ce se efectueaz dup ce lista a fost creat.

Parcurgerea listei presupune vizitarea fiecrui nod din list. Diferena fa de listele simplu nlnuite const n condiia instruciunii repetitive folosite, care nu mai poate depinde de o valoare nil (care, n acel caz, semnifica sfritul listei); la lista circular, condiia de terminare va testa c ultimul element memoreaz adresa primului element creat. Parcurgerea poate fi fcut n dou moduri: (1) se tiprete informaia din primul nod i se trece la parcurgerea listei de la al doilea pn cnd se ajunge din nou la primul nod sau (2) se parcurge lista ncepnd cu primul nod pn cnd n cmpul urm al nodului curent se ntlnete adresa primului nod; n acest caz, informaia din nodul curent se va tipri ulterior.

La lista circular nu exist attea variante de inserare ca la lista simplu nlnuit, deoarece parcurgerea listei circulare pentru a ajunge la elementul dorit este mai facil dect a listelor simplu nlnuite. Inserarea naintea unui element dat se reduce astfel la o inserare dup un element cu modificarea adresei de inserare. Prin urmare, este suficient descrierea i implementarea unui algoritm de inserare a unui nod dup unul existent n list.tergerea unui nod dintr-o list circular impune tratarea urmtoarelor cazuri de excepie: nodul care trebuie ters nu exist n list i lista este vid. n plus, dac se dorete tergerea primului nod, atunci trebuie modificat adresa memorat n ultimul nod al listei, pentru a reflecta eliminarea primului nod din list.

Dirijarea nvrii pentru obinerea performanei

Se va pune n discuie aplicarea acestei structuri n probleme cum ar fi urmtoarea:

Enun: Joc numrtoare: Un grup de copii este aezat n cerc i particip la urmtorul joc: iniial, se stabilete un numr N i se alege (aleator) un copil de la care se ncepe numrtoarea. Apoi, tot al N - lea participant este eliminat din cerc, jocul continu pn cnd rmne un singur participant. S se scrie un program care citete numele participanilor la joc, numrul N i copilul de la care ncepe numrtoarea, i afieaz numele persoanelor n ordinea eliminrii lor (ultimul rmas, va fi afiat cu titlul de ctigtor). Se va folosi o lista circular simplu nlnuit pentru memorarea cercului copiilor (se memoreaz numele lor). Realizarea conexiunii inverse (feedback)

Pentru un studiu mai aprofundat al temei li se va da elevilor urmtoarea list de probleme pentru studiu individual (fia numrul 2).

Fia numrul 21. Scriei un algoritm de concatenare a dou liste circulare simplu nlnuite.

2. Elaborai un algoritm care s considere o list circular simplu nlnuit i s inverseze direciile tuturor sgeilor.

3. Scriei un algoritm de mprire a unei liste circulare simplu nlnuit n dou liste circulare avnd un numr ct mai apropiat de elemente (dac e posibil egal).

4. S se implementeze operaiile specifice unei liste liniare dublu nlnuite circular.

5. Scriei un program care s simuleze jocul Nu te supra frate! care are urmtoarele reguli:

Se joac pe o tabl cu 50 de csue numerotate cu valori de la 1 la 50. Fiecare juctor are o pies cu care mut i cu care ncepe de pe csua numrul 1. Scopul jocului este s ajungi primul cu propria piesa la final, pe csua cu numrul 50. Fiecare juctor arunc cu zarul i mut piesa lui attea csue cte i indic valoarea zarului. Desigur, dac n drum "pici" peste piesa altui juctor, l-ai scos din joc! Respectivul trebuie s atepte un zar cu valoarea 6 pentru a re-introduce piesa n joc. Pe parcursul jocului pot fi stabilite csue cu semnificaii speciale (csue bonus sau capcan) cum ar fi:

csua 4 - avansezi 2 csue;csua 13 - mai ai dreptul la o aruncare cu zarul;

csua 26 - avansezi nc odat valoarea zarului;csua 10 - te ntorci la csua 1;

csua 30 - stai o tur;csua 49 - te ntorci dublul zarului; .a.m.d.

PAGE 6