UNIVERSITATEA BABEŞ-BOLYAIFACULTATEA DE MATEMATICĂ ŞI INFORMATICĂ

MODELProbă scrisă la INFORMATICĂ

Toate subiectele sunt obligatorii. Se acordă 10 puncte din oficiu. Timpul efectiv de lucru este de 3 ore.

Subiectul I (30 puncte)

a) Definiţi noţiunea de variabilă. Ce înţelegeţi prin variabilă statică şi variabilă dinamică? Daţi exemple sugestive.

b) Descrieţi tipul tablou într-un limbaj de programare.c) Ce înţelegeţi prin sortarea unui şir de date? Daţi exemplu de un algoritm care realizează

sortarea unui şir de date şi discutaţi complexitatea lui.

Subiectul II (30 puncte)

Se dă următorul algoritm:Se cere:a) Ce se va afişa dacă se citesc valorile:

5, 222, 2043, 29, 2, 20035?b) Determinaţi un set de date de intrare care să

nceapă cu valoarea ȋ 3 astfel încât valoarea afişată să fie 222.

c) Scrieţi o secvenţă de instrucţiuni echivalentă care să utilizeze structura repetitivă Repeta în locul structurii Câttimp.

Subiectul III (30 puncte)

Se citeşte un şir X de numere naturale pozitive, citirea şirului terminându-se la introducerea valorii 0 (Exemplu: dacă valorile introduse sunt 1, 2, 3, 0 atunci şirul citit va fi

)3,2,1( 321 ==== xxxX , iar lungimea şirului citit va fi 3=n ). Să se scrie un program care construieşte şi afişează şirul ),...,( 21 kyyyY = conţinând, în ordine descrescătoare, numerele palindroame distincte din şirul X. Un număr natural se numeşte palindrom dacă citit de la stânga la dreapta sau de la dreapta la stânga reprezintă acelaşi număr (Exemplu: 131 este palindrom, iar 12 nu este palindrom). Şirul Y se va construi direct ordonat, fără a se face ordonarea ulterioară construcţiei. Exemple:

− Pentru şirul )677,44,313,1,131,13,2,2442,2(=X se obţine )1,2,44,131,313,2442(=Y .− Pentru şirul )623,24,21(=X se va tipări mesajul 'Sirul Y e vid'.

Se vor folosi subprograme pentru: citirea unui şir, determinarea cifrelor unui număr, verificarea dacă un număr este palindrom, construirea şirului Y şi tipărirea unui şir.

Programul se poate scrie într-unul dintre limbajele studiate la liceu (Pascal, C++ etc). Folosiţi comentarii pentru a uşura înţelegerea soluţiei date (explicarea semnificaţiei identificatorilor folosiţi, descrierea detaliilor de implementare etc).

Citeste n;s 0;Pentru i1,n executa nr 1; Citeste x; Cattimp x>9 executa nr nr*10; x[x/10]; SfCattimp; s s+x*nr;SfPentru;Tipareste s;

BAREMCorectare probă scrisă INFORMATICĂ

SUBIECT I

a) 8pb) 8pc) 14p

SUBIECT II

a) Se afiseaza valoarea 22222. 8pb) 3 200 20 2 16pc) 6p

SUBIECT III

Subprograme din care: 23p− citirea unui şir 2p− determinarea cifrelor unui număr 2p− verificarea dacă un număr este palindrom 4p− inserarea unui număr într-un şir ordonat 6p− construirea şirului Y 3p− tipărirea unui şir. 2p− alte subprograme 4p

Program principal 2pStil 5p

− comentarii, structurare, indentare, corectitudineapelul corect al subprogramelor

SCHIŢĂ DE REZOLVARE PENTRU SUBIECTUL IIII

OBSERVAȚIE IMPORTANTĂ

Acest material nu vrea să sugereze candidaţilor că redactarea rezolvării problemei trebuie să respecte ad-litteram etapele și modul de lucru descrise mai jos. Textul de faţă descrie modalitatea de rezolvare a problemei de programare folosind metoda detalierii în paşi succesivi, având în primul rând un caracter didactic, explicativ. Prin citirea lui, candidaţii pot înţelege mai bine atât cerinţa din enunţ privind subprogramele folosite, cât şi modul în care este gândit baremul de rezolvare.Pentru o rezolvare bine apreciată sunt importante următoarele:

• folosirea subalgoritmilor/subprogramelor la soluţia unei probleme de programare

• explicarea semnificaţiei parametrilor subprogramelor şi a tipului lor (date: parametri de intrare, rezultate: parametri de ieşire)

• explicarea prin comentarii a deciziilor importante şi a semnificaţiei variabilelor locale

• respectarea cerinţelor problemei.Prin enumerarea subprogramelor cerute în enunţul problemei se doreşte uşurarea muncii candidaţilor. Dacă n soluţia realizată de un candidat sunt subprograme cu altăȋ implementare dec t cea sugerată (cum e cazul funcției ȃ palindrom n exemplul de maiȋ jos), însă modul de rezolvare este corect și bine explicat, ea va fi notată corespunzător. În programare sunt rare situaţiile în care o problemă are o singură soluţie.

În cele ce urmează vom descrie, folosind limbajul Pseudocod, o modalitate de proiectare a algoritmului de rezolvare a problemei propuse, care explică detaliat atât cerinţele problemei (folosirea de subalgoritmi), cât şi baremul de rezolvare.

Algoritmul de rezolvare va fi obţinut prin detalierea pas cu pas a enunţului problemei, proces denumit şi proiectare descendentă sau rafinare/detaliere în paşi succesivi. Primul algoritm de descris corespunde problemei de rezolvat. Pe parcursul proiectării sale se identifică alți subalgoritmi.

Pentru fiecare algoritm/subalgoritm identificat, vor exista cel puțin două versiuni: versiunea inițială (numită specificare), conținând propoziții Pseudocod nestandard (precedate prin caracterul ‘@’ și exprimate în limbaj natural), care precizează numele şi parametrii subalgoritmului și versiunea finală, conținând numai propoziții Pseudocod standard. De regulă, fiecare propoziție nestandard detaliată devine comentariu. Comentariile sunt puse în acolade.

Detalierea în paşi succesivi produce versiuni din ce în ce mai detaliate şi mai precise ale algoritmilor/subalgoritmilor. Proiectarea unui algoritm/subalgoritm este completă când descrierea sa conţine numai propoziţii Pseudocod standard. Soluția problemei este completă când toți algoritmii/subalgoritmii identificați sunt proiectați complet.

Algoritmul de rezolvare a problemei Versiunea 1:

Algoritmul SUBIECTIII este@ Citeşte şirul X@ Construieşte şirul Y@ Tipăreşte şirul Y

SfAlgoritm

Fiecare dintre cele trei propoziții nestandard de mai sus conduce natural câte un subalgoritm, cu numele sugestive: citire, construire şi tipărire.

Subalgoritmul citire (X, n) este{Rezultate: şirul nXXX ,....,, 21 şi numărul natural n (lungimea şirului X)}

{Descriere: Se citeşte un şir X de numere naturale pozitive, citirea terminându-se la introducerea valorii 0}

@ Se citesc repetat numere până la citirea valorii 0 şi se adaugă în şirul X SfSubalgoritm

Subalgoritmul construire (X, n, Y, k) este{Date: şirul nXXX ,....,, 21 şi numărul natural n (lungimea şirului X)}

{Rezultate: şirul kYYY ,....,, 21 conţinând în ordine descrescătoare numerele palindroame din X şi numărul natural k (lungimea şirului Y)}{Descriere: Se construieşte (direct în ordine descrescătoare) şirul kYYY ,....,, 21 }

@ Examinează elementele din şirul X şi pune în şirul Y cele care sunt palindroame, @ în aşa fel încât să se păstreze ordinea descrescătoare a elementelor din Y

SfSubalgoritm

Subalgoritmul tipărire (X, n) este{Date: şirul nXXX ,....,, 21 şi numărul natural n (lungimea şirului X)}

{Descriere: Se tipăresc elementele şirului X}@ Se parcurge şirul X şi se tip reşte fiecare elementǎ

SfSubalgoritm

În acest moment, fiecare dintre cei trei subalgoritmi este specificat complet, ceea ce permite obţinerea versiunii finale a algoritmului, prin rescrierea Versiunii 1 ( nlocuirea propozițiilorȋ nestandard cu apelurile corespunzătoare de subalgoritmi):

Algoritmul de rezolvare a problemei Versiunea 2

Algoritmul SUBIECTIII estecitire (X, n)construire (X, n, Y, k)tipărire (Y, k)

SfAlgoritm

Urmează ca în continuare să fie detaliaţi subalgoritmii citire, construire şi tipărire.

Subalgoritmii citire şi tip rireǎ sunt simpli:

Subalgoritmul citire (X, n) este:{Se citesc repetat numere până la citirea valorii 0 şi se adaugă în şirul X. Deoarece se citeşte cel puţin o valoare, se foloseşte structura repetitiv ǎ repetǎ}n←0 {Iniţial şirul X nu are nici un element.}repetǎ

n←n+1citeşte X[n]

pân când ǎ X[n]=0n←n-1 {Ultima valoare citit , num rul 0, nu este element al şirului, de aceea se ǎ ǎ

decrementeaz valoarea lui ǎ n}SfSubalgoritm

Subalgoritmul tip rireǎ (X, n) este:{Se verific dac şirul ǎ ǎ X are cel puţin un element. Dacă X are 0 elemente, se va afişa un mesaj corespunzător}daca n=0 atunci

tip reşteǎ ‘Sirul este vid’altfel

{Se parcurge şirul X şi se tip reşte fiecare element}ǎpentru i←1, n executa

tip reşteǎ X[i]sfpentru

sfdacaSfSubalgoritm

Subalgoritmul construire este unul mai complex, necesitând mai mulţi paşi de detaliere, descrişi în continuare. Primul pas de detaliere pleacă de la propoziția nestandard din specificarea subalgoritmului:

Subalgoritmul construire (X, n, Y, k) este{iniţial şirul Y nu are elemente}k←0{parcurge pe rând elementele din şirul X}pentru i←1,n execută

@ dacă elementul X[i] este palindrom, adaugă-l la Y astfel încât Y să rămână @ ordonat descrescător

sfpentruSfSubalgoritm

Această versiune conţine tot o singură propoziţie nestandard. Examinând-o cu atenţie, se identifică două subprobleme de rezolvat / doi subalgoritmi de descris:

• verificarea unui număr dacă este sau nu palindrom;

• inserarea unui număr într-un şir ordonat descrescător astfel încât să se păstreze ordonarea şirului.

Primul subalgoritm returnează un rezultat boolean, fiind exprimat natural printr-o funcție.

Specificările subalgoritmilor identificați sunt:

Funcţia palindrom (a) este{Date: numărul natural a}{Rezultat: adevărat dacă a este palindrom, fals în caz contrar}{Descriere: Se verifică dacă numărul a este sau un palindrom}

@ Verifică dacă şirul cifrelor numărului este palindrom (este acelaşi parcurs de la stânga la @ dreapta sau de la dreapta la stânga)

SfFuncţie

Subalgoritmul inserare (a, Y, k) este{Date: numărul natural a, şirul kYYY ,....,, 21 ordonat descrescător şi numărul natural k (lungimea şirului Y)}{Rezultate: şirul kYYY ,....,, 21 ordonat descrescător în care a fost inserat a şi numărul natural k

(noua lungime a şirului Y)}{Descriere: Se inserează valoarea a în şirul Y astfel încât să se păstreze ordonarea şirului}

@ Caută poziţia pe care ar trebui inserat a în Y şi apoi inserează-l în Y pe poziţia respectivă SfSubalgoritm

Cu specificările de mai sus, versiunea finală a subalgoritmului construire devine:

Subalgoritmul construire (X, n, Y, k) estek←0pentru i←1,n execută

{verifică dacă elementul X[i] este palindrom}dacă palindrom(X[i]) atunci

{inserează X[i] în şirul ordonat Y }inserare(X[i], Y, k)

sfdacă sfpentru

SfSubalgoritm

Rămân a fi detaliate funcţia palindrom şi subalgoritmul inserare.

Pentru a verifica dac un num r este ǎ ǎ palindrom, trebuie mai întâi s se determine şirul cifrelorǎ num rului, iar apoi s se testeze dacă elementele egal depărtate de capetele șirului sunt egale:ǎ ǎ

Funcţia palindrom (a) este@ Construieşte şirul cifrelor num rului ǎ a, numit cifre, având lungimea t @ Verifică dacă șirul cifre este sau nu palindrom, testând elementele egal depărtate de @ capetele şirului

SfFuncţie

Din prima propoziţie nestandard se identifică un nou subalgoritm, determin Cifre(a, cifre, t)ǎ pentru determinarea cifrelor unui număr. A doua propoziție nestandard se poate transpune direct în propoziții standard. Se obține astfel varianta finală a funcţiei palindrom:

Funcţia palindrom (a) este{Construieşte şirul cifrelor num rului ǎ a, numit cifre, având lungimea t} determinaCifre(a,cifre, t)estePalindrom ← adev ratǎ {Se presupune c num rul ǎ ǎ a este palindrom}i←1 { Se vor testa cifrele de pe pozitiile i şi t-i+1 }{ Deoarece se testează elemente egal depărtate de capete, şirul cifre se va parcurge numai pân la jumătate }ǎcâttimp (i≤ t div 2) şi (estePalindrom=adevărat) execută

dac ǎ cifre[i] ≠ cifre[t-i+1] atunci {există în șir dou elemente/cifre egal depărtateǎ de capete care sunt diferite }

estePalindrom←fals altfel

i← i+1sfdacǎ

sfpentrupalindrom←estePalindrom

SfFuncţie

Subalgoritmul pentru determinarea cifrelor unui număr este descris n continuare. ȋ

Subalgoritmul determinaCifre (a, cifre, t) este{Date: a, un num r natural nenul}ǎ{Rezultate: şirul tcifrecifrecifre ,....,, 21 şi numărul natural t (lungimea şirului cifre)}{Descriere: Determin cifrele num rului natural ǎ ǎ a şi le depune în şirul cifre}

t←0câttimp a>0 executǎ

t←t+1cifre[t]←a mod 10 {restul împ rţirii num rului ǎ ǎ a la 10}a←a div 10 {câtul împ rţirii num rului ǎ ǎ a la 10}

sfcâttimpSfSubalgoritm

A mai rămas de detaliat subalgoritmul inserare. Primul pas de detaliere pleacă de la propoziţia nestandard din specificarea acestuia. Este tratat separat cazul când a este mai mic sau egal decât orice element din Y (sau când Y nu conţine nici un element).

Subalgoritmul inserare (a, Y, k) este{verifică dacă a trebuie adăugat pe ultima poziţie în Y }dacă (k=0) sau (a≤ Y[k]) atunci

{se adaugă la sfârşit}1+← kkakY ←][

altfel{se caută poziţia unde ar trebui inserat a în Y astfel încât să se păstreze ordonarea}

1←i {se începe parcurgerea şirului Y}{se caută prima poziţie i astfel încât ][iYa ≥ }

câttimp ( ][iYa < ) execută1+← ii

sfcâttimp{ i este poziţia pe care ar trebui inserat a în şirul Y pentru a păstra ordinea descrescătoare a elementelor}@ deplasează elementele din Y de pe poziţiile i,i+1,...,k cu o poziţie spre dreapta şi

apoi adaugă pe a pe poziţia i sfdacă

SfSubalgoritm

Versiunea finală a subalgoritmului inserare se obține prin detalierea ultimei propoziții nestandard, folosind structura repetitiv ǎ pentru :

Subalgoritmul inserare (a, Y, k) este{verifică dacă a trebuie adăugat pe ultima poziţie în Y }dacă (k=0) sau (a≤ Y[k]) atunci

{se adaugă la sfârşit}1+← kkakY ←][

altfel{se caută poziţia unde ar trebui inserat a în Y astfel încât să se păstreze ordonarea}

1←i {se începe iterarea şirului Y}{se caută prima poziţie i astfel încât ][iYa ≥ }

Câttimp ( [ ]a Y i< ) execută1+← ii

Sfcâttimp{ i este poziţia pe care ar trebui inserat a în şirul Y pentru a păstra ordinea descrescătoare a elementelor}{deplasează elementele din Y de pe poziţiile i,i+1,...,k cu o poziţie spre dreapta }pentru j ←k, i, -1 executǎ

][]1[ jYjY ←+sfpentru

aiY ←][ {adaugă num rul ǎ a pe poziţia i în şirul Y}1+← kk {se incrementeaz num rul de elemente din şirului ǎ ǎ Y}

sfdacăSfSubalgoritm

Lăsăm în seama cititorului implementarea algoritmului si a subalgoritmilor într-un limbaj de programare.

Observație

Menționăm faptul că funcția palindrom admite o implementare alternativă față de cea descrisă anterior, n care nu este necesară memorarea cifrelor numărului.ȋ Funcţia palindrom (a) este

{Construieşte num rul ǎ invers format din cifrele numărului a luate n ordine inversăȋ și apoi verifică dacă acest număr este egal cu a } număr←a invers←0 {Ia cifrele numărului a ncep nd cu cifra unitățilorȋ ȃ și construiește numărul invers}câttimp (număr>0) execută

invers←invers*10 + număr mod 10 {se actualizează numărul invers }număr←număr div 10 {câtul împ rţirii num rului ǎ ǎ număr la 10}

sfc ttimpȃ {Dacă numărul este egal cu inversul său, atunci este palindrom}

dacă a=invers atuncipalindrom←adevărat

altfelpalindrom←fals

sfdacăSfFuncţie