Clasa VII/VIII lecția 8 - 26 nov 2013

From Algopedia
Jump to navigationJump to search

Anunț

  • Referitor la elevii ce vor continua la cercul de informatică începînd cu marți 26 nov: anunț calificare

Tema - rezolvări

Rezolvări aici [1]

Lecție

Discuții despre problemele de la barajele de calificare Șumen secția juniori.

Problema pom

Problema pom este dintr-o categorie numită parsing sau analiză sintactică din domeniul mai larg al compilatoarelor. Teoria din spatele analizei sintactice se studiază în facultate, dar bazele ei pot fi ințelese odată ce stăpîniți recursivitatea.

Pentru a implementa orice problemă de parsing avem nevoie să știm două lucruri: gramatici și implementarea analizorului recursiv cu proceduri pe baza acestor gramatici. Să le luăm pe rînd.

Gramatica expresiilor

Fără a intra în detalii deoarece depășește nivelul acestui cerc, putem descrie o expresie astfel:

Expr -> Litera [(Lista)]
Lista -> Expr [,Expr]*
Litera -> a|b|c|...|y|z

Unde parantezele pătrate semnifică o bucată opțională, steluța semnifică repetiție de oricîte ori, inclusiv zero, iar bara verticală reprezintă operatorul sau (opțiune între mai multe opțiuni).

Ce semnifică această gramatică? Ea descrie toate expresiile corecte, fără a ține cont de arități. Cum? Ea arată o succesiune de înlocuiri posibile. Astfel Expr se poate înlocui cu Litera care la rîndul ei se poate înlocui cu c. Astfel știm că c este o expresie corectă. Să luăm un caz mai complicat, să generăm de exemplu expresia f(a, g(x)):

Expr -> Litera(Lista) -> f(Lista) -> f(Expr, Expr) -> f(Litera, Expr) -> f(a, Expr) -> f(a, Litera(Lista)) -> f(a, g(Lista)) -> f(a, g(Expr)) -> f(a, g(Litera)) -> f(a, g(x))

Analizorul recursiv cu proceduri

Bazat pe gramatica precedentă putem implementa un analizor recursiv. Fiecare simbol neterminal (care se mai poate expanda, cele care încep cu litere mari) se înlocuiește cu o funcție C care "înghite" de la intrare o expresie. Ea verifică în același timp corectitudinea și se oprește la caracterul incorect, dacă găsește o greșeală. Să luăm un exemplu: funcția expr().

Această funcție va chema mai întîi funcția litera() care va înghiți la intrare o literă. Apoi va testa primul caracter la intrare. Dacă este paranteză înseamnă ca avem de "înghițit" în continuare o paranteză deschisă, apoi chemăm lista() și apoi înghițim o paranteză închisă. Pe tot parcursul, dacă găsim o nepotrivire (nu e literă, nu găsim paranteza închisă, sau funcția lista() returnează eroare) ne oprim returnînd eroare.

Ar mai fi de menționat că, deoarece vom avea mereu de luat decizii ce "înghițim" mai departe bazat pe primul carcater de la intrare, îl vom ține separat într-o variabilă numită first. Astfel, șirul de la intrare este reprezentat de primul caracter ținut în first și de fișierul de la intrare, ce urmează logic în secvență. De fiecare dată cînd citim un caracter din fișier îl trecem mai întîi în variabila first. Astfel putem "trage cu ochiul" la primul caracter din fișier fără a avea probleme cu faptul că l-am citit deja și că o altă funcție vrea să îl recitească. Toate funcțiile știu că primul caracter este în first.

Problema decodare

Problema decodare este o variantă a unei probleme clasice: se dă numărul unei combinări, să se afișeze combinarea. Ea este o problema subit mai grea dacă nu cunoaștem problema de bază :-) Aviz amatorilor (cei care nu vor să învețe nimic nou ci doar să ia cît mai multe puncte la concursuri).

Care este numărul de șiruri care începe cu cel mai mic număr posibil? Cel mai mic număr posibil este evident

MIN = 1 + D·(K-1)

deoarece punem ultima cifră din șir ca fiind unu și apoi ne deplasăm către prima cifră adunînd D. Vom face acest lucru de (K-1) ori.

Numărul de șiruri care începe cu MIN este evident 1. Cîte șiruri încep cu MIN-1? Să-l calculăm. Avem acum o unitate în plus pe care o putem adăuga fie între primul și al doilea număr, fie între al doilea și al treilea, ș.a.m.d., pîna după ultimul număr. Avem deci K poziții posibile, rezultînd K șiruri care încep cu MIN-1. Cîte șiruri încep cu MIN-2? Avem acum două unități ce pot fi inserate în aceleași locuri. Ceea ce înseamnă că avem posibilități de inserare, unde sînt combinări cu repetiție:

Observăm acum regula. Putem determina numărul de șiruri care încep cu un număr. Drept pentru care putem determina primul număr: începem cu MIN ca primul număr, apoi îl incrementăm pe măsură ce calculăm numărul de șiruri care încep cu respectivele numere. Ne oprim cînd suma numerelor de șiruri depășește numărul șirului ce trebuie afișat.

Odată aflat primul număr reducem problema la o problemă mai mică: avem MIN-D numere ce vor forma șiruri de cîte K-1. Ne interesează acum șirul cu numărul inițial din care scădem numărul de șiruri calculate pînă acum.

Temă

Rezolvați următoarele probleme de la Șumen:

Rezolvări aici [2]