Cum iei cat mai multe puncte la Bacalaureatul de Informatica

Salutare prieteni si bine v-am regasit. Am promis in urma cu un an (un an jumate) ca voi prezenta o strategie prin care puteti obtine cat mai multe puncte in proba de Informatica a Bacalaureatului. Din pacate, atunci s-a schimbat structura si nu am mai revenit cu acest tutorial.

Pentru a prezenta aceasta strategie, vom rezolva sesiunea speciala de anul trecut (2018).

Subiectul I

Grila cu instructiunea if (Problema 1)

1. Variabila x este de tip întreg. Indicați o expresie care are valoarea 1 dacă și numai dacă expresia C/C++ alăturată x<=3 || x>10 are valoarea 1.

Pentru a rezolva aceasta problema, trebuie luata fiecare varianta la rand si transformat raspunsul. Se vor aplica urmatoarele reguli atunci cand efectuezi transformarea:

1. ! (x < 10) se transforma in x >= 10. Deoarece negarea lui “<” este “>=”.
2. ! (x <= 10) se transforma in x > 10. Deoarece negarea lui “<=” este “>”.
3. ! (x < 10 || y > 5) se transforma in x >= 10 && y <= 5. Deoarece trebuie negat fiecare operator pe rand. Transformam mai intai x < 10 in x >= 10, mai apoi transformam || in && si in cele din urma y > 5 devine y <= 5.

Acum trecem la variantele de raspuns date in problema si transformam toate variantele de raspuns:

a. !( x < 3 && x < 10 ) devine x >= 3 || x >= 10
b. x >= 3 && ! ( x >= 10 ) devine x >= 3 && x < 10 – deoarece transformam doar a doua parte
c. ! ( x < 3 || x <= 10 ) devine x >= 3 && x > 10
d. ! ( x > 3 ) || ! ( x <= 10 ) devine x <= 3 || x > 10 – transformam doar conditiile lui x si lasam || neschimbat (deoarece “!” nu se aplica asupra interogarii, se aplica separat)

Problema pseudocod (Problema 2)

2. S-a notat cu a%b restul împărţirii numărului natural a la numărul natural nenul b şi cu [a] partea întreagă a numărului real a.

citeşte n, a (numere naturale nenule)
nr <- 0
i <- 1
cât timp i <= n execută
--- citeşte b (număr natural nenul)
--- c <- 0
--- cât timp b % 2 = 0 execută
------ b <- [b/2]
------ c <- c + 1
--- dacă c = a atunci
------ nr <- nr + 1
--- i <- i + 1
scrie nr

a) Scrieţi valoarea afişată dacă se citesc, în această ordine, numerele 5, 3, 9, 206, 200, 80, 24.

Indiferent de pseudocodul ce se va da, aceasta problema se va aborda tot timpul la fel. Trebuie creeat un tabel de valori ce va fi actualizat tot timpul cand o valoare se va schimba. Pentru a face tabelul de valori, coloanele vor reprezenta fiecare variabila in parte ce apare in problema (chiar daca unele variabile nu vor fi schimbate niciodata). Drept urmare, vom face tabelul pentru urmatoarea problema si avem urmatoarele coloane: n, a, nr, i, b, c. (ordinea in care le scrii nu este foarte importanta)

De fiecare data cand se modifica o valoare, copiem linia precedenta si inlocuim valoarea care se modifica. La finalul executarii tabelului, ar trebuii sa obtinem valoarea care ni se cere in enunt. In cazul acesta, valoarea este 2.

b. Dacă pentru variabila n se citeşte numărul 4, iar pentru variabila a se citeşte numărul 2, scrieţi un set de numere distincte din intervalul [10,99] care pot fi citite în continuare astfel încât, în urma executării algoritmului, să se afișeze valoarea 4.

In acest subpunct de obicei ni se cere sa oferim valori care sa produca un rezultat final. De obicei dupa ce ati facut tabelul, ar trebuii sa va prindeti despre ce este vorba in pseudocod si cum acesta functioneaza. Trebuie sa il analizati si sa il descrieti in cuvinte cat mai naturale.

In subpunctul anterior, numarul nostru curent se impartea la 2 in randuri repetate. Iar la final se verifica daca numarul se imparte la 2 de exact 3 ori. Cu alte cuvinte, daca numarul nostru este multiplu de 8 (2³). De data aceasta “a”-ul nostru este 2, drept urmare, trebuie sa urmarim multiplii de a lui 4. Trebuie sa avem grija, deoarece numarul trebuie sa se imparta exact la 4, dar nu la 8, 16, s.a.m.d.

Luam pe rand multiplii de a lui 4 si avem: 12 (4 * 3), 20 (4 * 5), 28 (4 * 7) si 36 (4 * 9).

c. Scrieţi în pseudocod un algoritm echivalent cu cel dat, înlocuind adecvat prima structură cât
timp…execută cu o pentru…execută.

Va las mai jos cateva secvente de cod care va pot indruma cum se inlocuiesc aceste structuri in pseudocod.

Daca urmarim schema de mai sus si inlocuim, vom obtine:

citeşte n, a (numere naturale nenule)
nr <- 0
pentru i <- 1, n executa
--- citeşte b (număr natural nenul)
--- c <- 0
--- cât timp b % 2 = 0 execută
------ b <- [b/2]
------ c <- c + 1
--- dacă c = a atunci
------ nr <- nr + 1
scrie nr

d. Scrieţi programul C/C++ corespunzător algoritmului dat.

La fel ca la subpunctul c, va atasez o schema care va arata cum se inlocuieste adecvat pseudocodul.

Urmarim tabelul de mai sus si transformam pseudocodul

#include    <iostream>

using namespace std;

int main()
{
    unsigned int n, a, b, nr, i, c;
    cin >> n >> a;
    nr = 0;
    for(i = 1; i <= n; i++)
    {
        cin >> b;
        c = 0;
        while(b % 2 == 0)
        {
            b = b / 2;
            c = c + 1;
        }
        if(c == a)
        {
            nr = nr + 1;
        }
    }
    cout << nr;
    return 0;
}

Subiectul II

Problema 1 si 2 (grilele pentru grafuri)

1. Un arbore cu 9 noduri, numerotate de la 1 la 9, este reprezentat prin vectorul de „taţi” (3,3,0,5,2,5,2,5,8). Descendenții direcți(“fii”) ai nodului cu eticheta 5 sunt:

Pentru a rezolva aceasta parte este necesar sa stiti toate definitiile ce tin de Teoria Grafurilor. Va las mai jos principalele definitii ce trebuie stiute pentru Bacalaureat:

Graf neorientat

Definiție: Se numește graf neorientat o pereche ordonată de mulțimi G=(X,U), unde:

X este o mulțime finită și nevidă de elemente numite vârfuri sau noduri
U este o mulțime finită de submulțimi cu două elemente din X, numite muchii.

Graf orientat

Definiție: Se numeşte graf orientat o pereche ordonată de mulțimi notată G=(V, U), unde:

V este o mulțime finită şi nevidă ale cărei elemente se numesc noduri sau vârfuri;
U este o mulțime de perechi ordonate de elemente distincte din V ale cărei elemente se numesc arce.

Componente conexe

Definitie: O componenta conexa e un subgraf conex maximal. Care are un drum intre oricare doua noduri nu s-ar mai putea adauga alte noduri pastrand-o conexa. In exemplul de mai jos avem 3 componente conexe: componenta portocalie (3 – 1 – 2), componenta rosie (4 – 5) si componenta albastra (6)

Graf partial

Definitie: Fie graful G = (X, U). Un graf partial al lui G, este un graf G1 = (X, V) cu V ⊆ U. Altfel spus, un graf partial G1 al lui G, este chiar G, sau se obtine din G pastrand toate varfurile si eliminand niste muchii.

Subgraf

Definitie: Fie graful G = (X, U). Un subgraf al lui G, este un graf G1 = (Y, V) unde Y ⊂ X, iar V va contine toate muchiile din U care au ambele extremitati in Y. Altfel spus, un subgraf al unui graf se obtine eliminand niste noduri si toate muchiile incidente acestor noduri.

Lant elementar

Definitie: Se numeste lant in graful G, o succesiune de varfuri L = {z₁,z₂,…,z_k} unde z₁,z₂,…,z_k ∈ X, cu proprietatea ca oricare doua varfuri consecutive sunt adiacente, adica muchiile [z₁, z₂], [z₂, z₃], …,[z_k-1, z_k] ∈ U

Pentru un lant L = {z₁,z₂,…,z_k}, daca varfurile sunt distincte doua cate doua, atunci lantul se numeste elementar. In caz contrar, lantul este neelementar.

L₁ = {1, 2, 3, 7, 4} este elementar, simplu, de lungime 4.
L₂ = {8, 7, 3, 5, 6} este elementar, simplu, de lungime 4.

Lant neelementar

L₁ = {6, 5, 3, 5} este neelementar si de lungime 3.
L₂ = {3, 4, 7, 3, 2} este neelementar, simplu si de lungime 4.

Ciclu

Definitie: Se numeste ciclu intr-un graf, un lant L = {z₁,z₂,…,z_k} cu proprietatea ca z₁ = z₂ si muchiile [z₁, z₂], [z₂, z₃], …,[z_k-1, z_k] sunt distincte doua cate doua.

Daca intr-un ciclu, toate varfurile cu exceptia primului si a ultimului sunt distincte doua cate doua, atunci ciclul se numeste elementar. In caz contrar, el este nelementar.

Analizam 3 cicluri:

C₁ = {1, 2, 3, 5, 6, 1} este un ciclu elementar.
C₂ = {3, 4, 7, 8, 5, 3, 2, 1, 6, 5, 3} este un ciclu neelementar.
C₃ = {3, 4, 7, 8, 5, 3} este un ciclu elementar.

Ciclu Hamiltonian

Definitie:

O cale hamiltoniana P a unui graf simplu G este o cale simpla care contine toate nodurile lui G.
Un ciclu hamiltonian al unui graf este un ciclu care contine toate nodurile grafului.

Ciclu Eulerian

Definitie:

Un drum Eulerian intr-un graf simplu G = (V, E) este un drum ce contine toate muchiile lui G.
Un circuit Eulerian intr-un graf simplu G = (V, E) este un circuit ce contine toate muchiile lui G.
Un graf Eulerian este un graf simplu ce contine un circuit Eulerian.

Arbore

Definitie: Un graf conex si fara cicluri se numeste arbore.

Fie un graf G = (X, U). Urmatoarele afirmatii sunt echivalente:

G este arbore
G este un graf conex, minimal in raport cu aceasta proprietate (eliminand o muchie oarecare, se obtine un graf ne-conex)
G este un graf fara cicluri, maximal in raport cu aceasta proprietate (adaugand o muchie oarecare, se obtine un graf care are cel putin un ciclu)

Un arbore cu n varfuri are n-1 muchii.

Revenim la enuntul problemei de mai sus. Pentru a rezolva aceasta problema ne uitam cine este nodul al carui tata este 0 si construim arborele, urmarind pe rand fiecare fiu. Arborele din enunt este urmatorul:

Urmarim fii nodului 5, iar raspunsul nostru este d. 4, 6, 8

2. Numărul de noduri ale unui graf neorientat fără cicluri, cu 26 de muchii și 12 componente conexe este:

Ideea in aceasta problema este folosim mai intai toate muchiile. Pentru a folosii toate muchiile putem construii un graf ca cel din figura, insiruind noduri unul dupa altul. Astfel formam prima componenta conexa. Acum ca am utilizat toate cele 26 de muchii, folosind 27 de noduri, pentru a forma restul de 11 componente conexe doar construim noduri izolate. Folosim astfel in total c. 38 de noduri

Problema 3 (struct)

3. Variabila d, declarată alăturat, memorează în câmpul mic cel mai mic divizor, strict mai mare decât 1, al numărului natural din intervalul [2,10²], memorat în câmpul nr.
Scrieţi o secvență de instrucțiuni în urma executării căreia, pentru numărul memorat în câmpul nr al variabilei d, se afișează pe ecran mesajul prim, dacă numărul este prim, mesajul patrat dacă numărul este pătratul unui număr prim, sau două numere naturale, separate printr-un spațiu, reprezentând cel mai mic și cel mai mare dintre divizorii proprii pozitivi ai săi. Divizorii proprii pozitivi ai unui număr sunt divizori pozitivi diferiţi de 1 şi de el însuşi.
Exemplu: dacă în câmpul nr se memorează numărul 12, iar în câmpul mic se memorează numărul 2, se afișează pe ecran
2 6
iar dacă în câmpul nr se memorează numărul 9, iar în câmpul mic se memorează numărul 3, se afișează pe ecran mesajul
patrat

struct divizor {
    int nr, mic;
} d;

Pentru a rezolva aceasta problema cu struct, puteti urmarii tutorialul special dedicat acestei structuri de date – Tipul struct in C++ | Teorie si probleme rezolvate .

Pentru a rezolva aceasta problema trebuie sa analizam cele trei cazuri ce apar in enunt:

cazul in care afisam doua numere: cel mai mic divizor (nr mic – oferit in enunt) si cel mai mare divizor (adica nr / mic)
cazul in care avem un patrat: adica nr = mic * mic
cazul in care avem un numar prim: adica mic = 1 (deoarece un numar prim se imparte doar la 1 si el insusi)

if(d.mic != 1)
{
    if(d.mic * d.mic == d.nr)
    {
        cout << "patrat";
    }
    else
    {
        cout << d.mic << " " << d.nr / d.mic;
    }
}
else if(d.mic == 1)
{
    cout << "prim";
}

Problema 4 (matricea)

4. Variabilele i şi j sunt de tip întreg, iar variabila a memorează un tablou bidimensional cu 9 linii şi 9 coloane, numerotate de la 1 la 9, având iniţial toate elementele nule.
Fără a utiliza alte variabile, scrieţi secvenţa de instrucţiuni de mai jos, înlocuind punctele de suspensie astfel încât, în urma executării secvenţei obţinute, variabila a să memoreze tabloul
alăturat.

Inainte de a rezolva orice problema ce implica matrici, trebuie sa urmariti cu atentie:

De unde incepe parcurgerea unei matrici, deoarece uneori se incepe de la 0, alteori se incepe de la 1
Cum se foloseste algoritmul de indicii matricei (i si j) pentru a compune elementele.

Va las mai jos 5 exemple clasice ce le puteti intalnii atunci cand dati de astfel de probleme:

Exemplul 1 (diagonala principala)

Acesta exemplu face parte din exemplele clasice atunci cand vine vorba despre prelucrarea unei matrici. Este vorba despre diagonala principala. Toate elementele ce fac parte din (sau sunt peste) diagonala principala sunt numerotate cu “1”, in timp ce elementele ce se afla sub diagonala principala sunt numerotate cu “0”.

for(int i = 1; i <= 6; i++)
{
    for(int j = 1; j <= 6; j++)
        if(i <= j)
            cout << "1";
        else
            cout << "0";
    cout << "\n";
}

Daca am fi avut conditia if(i == j) atunci doar diagonala principala ar fi devenit “1”. De asemenea, daca aveam if(i >= j) triunghiul de sub diagonala principala ar fi completat cu “1”.

Exemplul 2 (diagonala secundara)

Acest exemplu este cel de-al doilea caz “clasic”. Este vorba despre diagonala secundara. Toate elementele ce fac parte din (sau sunt peste) diagonala principala sunt numerotate cu “1”, in timp ce elementele ce se afla sub diagonala principala sunt numerotate cu “0”.

for(int i = 1; i <= 6; i++)
{
    for(int j = 1; j <= 6; j++)
        if(i+j <= 7)
            cout << "1";
        else
            cout << "0";
    cout << "\n";
}

Daca am fi avut conditia (i + j == 6 + 1) atunci doar diagonala secundara ar fi devenit”1″. De asemenea, daca aveam (i + j >= 6 + 1) triunghiul de sub diagonala secundara ar fi fost completat cu “1”.

Exemplul 3 (diagonala secundara – triplata)

In acest exemplu trebuie sa analizam pe baza carei reguli este construita figura formata din elementele cu “6”. Analizam indicii matricei si ajungem la concluzia ca toate elementele cu 6 au urmatoarea regula: (i + j == N || i + j == N + 1 || i + j == N + 2) – deoarece avem conditia (i + j == N + 1) – din exemplul de mai sus .

for(int i = 1; i <= 7; i++)
{
    for(int j = 1; j <= 7; j++)
        if(i+j == 7 || i + j == 7 + 1 || i + j == 7 + 2)
            cout << "1";
        else
            cout << "0";
    cout << "\n";
}

Noua ne trebuie un elemente in fata si in spatele acestei diagonale, asa ca mai adaugam un (i + j == N) pentru a obtine diagonala de deasupra diagonalei secundare si (i + j == N + 2) pentru a obtine diagonala de dedesuptul diagonalei secundare.

Exemplul 4 (diagonala principala si cea secundara + o observatie)

In acest exemplu analizam pe baza carei reguli este construita partea din matrice care contine “0”. Observam faptul ca aceasta este formata din combinarea diagonalei principale cu cea secundare – si vom avea conditia if(i == j || i + j == N + 1) .

for(int i = 1; i <= 7; i++)
{
    for(int j = 1; j <= 7; j++)
        if(i == j || i + j == 8)
            cout << 0;
        else
            cout << ((i + j) - 2) % 6;
    cout << "\n";
}

Mai trebuie doar sa vedem ce se intampla cu restul elementelor. Observam ca acestea fac parte din multimea {1, 2, 3, 4, 5} – asadar niciodata nu vor depasii 5 – o operatie ce ne ajuta cu acest lucru este restul impartirii (sau MOD %). Daca scriem x % MOD – toate numerele vor fi de la [0, MOD -1], adica putem sa ne folosim de x % 6 – pentru a folosii doar numere de la [1, 5].

Urmatoarea observatie care duce la obtinerea solutii este faptul ca insumand indicii, iar mai apoi scazand 2 obtinem matricea finala.

Observatie: daca incepeam matricea de la 0, nu mai era nevoie sa scadem 2 si totul ar fi fost mai dragut.

for(int i = 0; i < 7; i++)
{
    for(int j = 0; j < 7; j++)
        if(i == j || i + j == 6)
            cout << 0;
        else
            cout << (i + j) % 6;
    cout << "\n";
}

Exemplul 5 (numararea pana la n²)

Pentru a rezolva aceasta problema, observam faptul ca figura noastra nu este impartita pe diferite “zone”. Avem o generare consecutiva de numere, iar acestea se plaseaza in ordinea in care este parcursa matricea. Intrebarea ce ramane este “cum obtinem noi numerele?”.

Ca si pana acum, analizam indicii, si observam ca pe fiecare linie, termenii sunt obtinuti adunand +1 termenului anterior. In momentul cand se trece la urmatoarea linie, elementul urmator incepe deja cu 6 unitati in plus fata de elementul de deasupra lui.

for(int i = 1; i <= 6; i++)
{
    for(int j = 1; j <= 6; j++)
            cout << (i - 1) * 6 + j << " ";
    cout << "\n";
}

Exemplul 6 (cel din problema)

Am facut exemplul cu 7 pentru ca nu am gasit mai multe culori. Exemplul din problema are 9 linii si coloane.

Analizam putin poza si ajungem la urmatoarea concluzie: de fiecare data cand parcurgem a[i][j] si ii setam o valoare, ar trebuii sa facem acelasi lucru si pentru a[j][i].

Singura problema care ar intervenii ar fi suprascrierea unei valori. Ne folosim de mentiunea „avand initial toate elementele nule” si rezolvam aceasta problema.

// TREBUIE CA MATRICEA a[N + 1][N + 1] SA FIE DECLARATA GLOBALA!
for (int i = 1; i <= N; i++)
{
    for (int j = 1; j <= N; j++)
    {
        if (a[i][j] == 0)
        {
            a[i][j] = i;
            a[j][i] = i;
        }
        cout << a[i][j] << " ";
    }
    cout << "\n";
}

Problema 5 (siruri de caractere)

5. Un text are cel mult 100 de caractere și este format din cuvinte, numere naturale şi spaţii. Cuvintele sunt formate numai din litere mici ale alfabetului englez. Cuvintele şi numerele sunt separate prin câte un spaţiu, ca în exemplu.
Scrieţi un program C/C++ care citeşte de la tastatură un text de tipul menţionat mai sus şi afişează pe ecran numărul din text care începe cu cea mai mare cifră, ca în exemplu. Dacă există mai multe astfel de numere, se afișează doar unul dintre acestea, iar dacă textul nu conține niciun număr, se afișează pe ecran mesajul nu exista.
Exemplu: pentru textul
am 190 de nuci si 70 de castane
se afişează
70

In acest tip de problema se folosesc cativa algoritmi elementari atunci cand vorbim despre lucrul cu sirurile de caractere:

Parcurgerea sirului, caracter cu caracter

In momentul cand declaram un sir de caractere, declaram practic un vector ce stocheaza caractere – deoarece avem nevoie de cate un “element” pentru fiecare litera (si spatiu) ce se regaseste in propozitie.

Un lucru foarte important este caracterul \0 de la finalul sirului. Orice sir de caractere va fi insotit de acest simbol, iar el indica sfarsitul unui sir. Atunci cand vom declara un sir de caractere vom avea in vedere sa includem loc si pentru acest simbol.

Pentru a parcurge sirul caracter cu caracter, vom trata sirul ca un vector de caractere:

char text[101];
cin.getline(text, 101);

int lungimeText = strlen(text); // Folosim functia pentru determinarea lungimii unui sir
for(int i = 0; i < lungimeText; i++)
    cout << "Caracterul " << i << " => " << text[i] << "\n";

Despartirea sirului in cuvinte

Pentru a rezolva acest tip de problema trebuie sa stim cum functioneaza functia strtok. Documentarea functiei o puteti gasii aici: strtok – C++ Reference.

Pe scurt:

Aceasta functie primeste ca si parametrii:
- Sirul de caractere sau NULL*
- O lista de delimitatoare (dupa ce caractere sa “sparga” sirul – in cazul nostru, il sparge dupa spatiu)
Ce returneaza aceasta functie?
- Aceasta functie returneaza un pointer – “o sagetica” – catre prima grupa de caractere gasita inainte de delimitator. In cazul nostru delimitatorul este spatiul, iar grupul nostru de caractere formeaza un cuvant.
- NULL daca nu (mai) gaseste delimitatoare
Daca in loc de un sir de caractere (primul parametru) oferim NULL – se va continua scanarea de unde a ramas ultima scanare cu succes.

char text[101];
cin.getline(text, 101);

char *cuvant = strtok(text, " ");
while(cuvant != NULL)
{
    cout << cuvant << " ";
    cuvant = strtok(NULL, " ");
}

Pentru a rezolva problema din enunt trebuie sa folosim cel de-al doilea algoritm, deoarece ne trebuie cea mai mare cifra cu care incepe un numar (avand la dispozitie doar cifrele 1 si 7). Daca ni se cerea “cea mai mare cifra” – am fi avut “9” si am fi folosit primul algoritm.

Dupa ce spargem sirul de caractere trebuie sa verificam daca este o cifra, si sa memoram aceasta cifra pentru a construii numarul. Iar pentru aceasta problema sunt mai multe variante de a o rezolva.

int main()
{
    char text[101];
    cin.getline(text, 101);

    //int cifraMax = -1;
    int avemCifre = 0;
    char cMax = NULL;
    char *cuvant = strtok(text, " ");
    while(cuvant != NULL)
    {
        if(cuvant[0] >= '0' && cuvant[0] <= '9')
        {
            char c = cuvant[0];
            if(c > cMax)
                cMax = c;
            avemCifre = 1;
            /*
             * int primaCifra = cuvant[0] - '0';
             * if(primaCifra > cifraMax)
             *      cifraMax = primaCifra;
             */
        }
        cuvant = strtok(NULL, " ");
    }
    if(avemCifre == 1)
        cout << cMax << "0";
        // cout << cifraMax * 10;
    else
        cout << "Nu exista";
    return 0;
}

Prima varianta consta in declararea unui caracter initial “cMax” ce il setam cu NULL. Verificam apoi daca avem o cifra si o comparam cu cifra maxima, declarata anterior. Daca este mai mare, actualizam cifra maxima.

La final vom obtine un caracter intre ‘0’ si ‘9’, fiind nevoie sa mai afisam un “0” dupa acesta pentru a obtine rezultatul final.

Subiectul III

Problema 1 (recursivitate)

int f1(int x, int y)
{
    if(x % 2 != 0 || y % 2 != 0)
        return 1;
    else
        return 2 * f1(x / 2, y / 2);
}

int f2(int x, int y) 
{
    if (x == y) 
        return x;
    else 
        if (x > y) 
            return f2(x - y, y);
        else 
            return f2(x, y - x);
}

1. Subprogramele f1 şi f2 sunt definite mai sus. Cel mai mare divizor comun al lui 30 și 50 se obține în urma apelului:
a. f₁(30, 50)
b. f₂(30, 50)
c. f₁(30/2, 50)
d. f₂(30/2, 50)

Pentru a rezolva aceasta problema, va recondam tutorialul nostru: Despre recursivitate in informatica.

Si la fel ca in oricare alta problema de informatica, o vom rezolva folosind un tabel pentru a urmarii cum se modifica valorile pe parcursul apelarii functiilor.

Tabelul subpunctului a
Tabelul subpunctului b
Tabelul subpunctului c
Tabelul subpunctului d

Observam faptul ca functia f2 efectueaza scaderi succesive din numarul mai mare pana cand cele doua numere sunt egale. Am discutat despre aceasta metoda in acest articol: Algoritmul lui Euclid in C++ .

Asadar, varianta corecta de raspuns este subpunctul b.

Problema 2 (backtracking)

2. Utilizând metoda backtracking, se generează toate posibilitățile de a forma cutii cu bomboane de tipuri distincte din mulțimea {fondante, caramele, dropsuri, acadele}. Într-o cutie sunt cel puțin două tipuri de bomboane, dar nu pot fi și dropsuri și acadele simultan. Două cutii sunt distincte dacă ele conțin cel puțin un tip diferit de bomboane. Primele patru soluţii generate sunt, în această ordine, (fondante, caramele), (fondante, caramele, dropsuri), (fondante, caramele, acadele), (fondante, dropsuri). Scrieţi a cincea și a șasea soluție, în ordinea generării acestora.

Dupa cum v-am obisnuit deja, toate problemele de acest tip se rezolva codificand elementele din multime:

fondante – 1
caramale – 2
dropsuri – 3
acadele – 4

Iar daca transformam variantele de raspuns, obtinem: (1, 2), (1, 2, 3), (1, 2, 4), (1, 3).

Urmatoarea solutie generata ar fi fost (1, 3, 4) dar in problema se specifica faptul ca daca avem perechea (3, 4) in aceeasi cutie – aceasta nu este valida. Generand urmatoarele doua cutii, obtinem solutia problemei:

(1, 4) adica (fondante, acadele)
(2, 3) adica (caramele, dropsuri)

Problema 3 (subprograme / functii)

3. Un număr natural este numit echilibrat dacă suma cifrelor sale de pe poziții pare este un număr par, iar suma cifrelor sale de pe poziţii impare este un număr impar. Pozițiile cifrelor sunt numerotate de la dreapta la stânga, astfel: cifra unităților este pe poziția 0, cifra zecilor este pe poziția 1 ș.a.m.d.
Subprogramul echilibrat are un singur parametru, n, prin care primeşte un număr natural (n∈[10,10⁹]). Subprogramul returnează valoarea 1 dacă n este echilibrat sau valoarea 0 în caz contrar.
Scrieţi definiţia completă a subprogramului.
Exemplu: dacă n=25163912, subprogramul returnează valoarea 1, iar dacă n=11211, subprogramul returnează valoarea 0.

Pentru a afla mai multe despre cum functioneaza subprogramele (sau functiile), poti urmarii acest tutorial: Functii si parametrii in C++.

In general la problemele de acest gen se vor utiliza urmatorii algoritmi:

Folosind primul algoritm din lista, construim functia urmatoare:

int echilibrat(int n)
{
    int pozitiaCifra = 0, sumaCifrePare = 0, sumaCifreImpare = 0;
    while(n)
    {
        int cifra = n % 10;
        n = n / 10;
        if(pozitiaCifra % 2 == 0)
            sumaCifrePare = sumaCifrePare + cifra;
        if(pozitiaCifra % 2 == 1)
            sumaCifreImpare = sumaCifreImpare + cifra;
        pozitiaCifra = pozitiaCifra + 1;
    }
    if(sumaCifrePare % 2 == 0 && sumaCifreImpare % 2 == 1)
        return 1;
    else
        return 0;
}

Problema 4 (“ultima problema”)

4. Numim secvență încadrată a unui șir de numere naturale un subșir al acestuia, format din termeni aflați pe poziții consecutive în șirul dat, subșir care începe și se termină cu aceeași valoare. Lungimea secvenței este egală cu numărul de termeni ai acesteia.
Fișierul bac.txt conține un șir de cel puțin două și cel mult 10⁶ numere naturale din intervalul [0, 9]. Numerele sunt separate prin câte un spațiu. În șir există cel puțin doi termeni egali.
Se cere să se determine secvențele încadrate din acest șir care au lungime maximă și să se afișeze pe prima linie a ecranului lungimea maximă determinată, iar pe următoarea linie, pentru fiecare astfel de secvenţă, valoarea primului său termen. Numerele de pe a doua linie sunt afişate în ordine strict crescătoare, separate prin câte un spaţiu.
Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fişierul bac.txt conţine numerele
3 1 5 2 4 5 5 2 5 9 5 7 4 6 8 0 8
atunci pe ecran se afișează valorile:
9
45

Mereu la ultima problema o sa trebuiasca sa implementati un algoritm Greedy. In general nu exista un tipar care sa descrie aceasta problema, trebuie sa cititi cu grija si sa urmariti:

Cu ce structuri de date vei lucra?
- Siruri de caractere
- Tablouri unidimensionale (vectori)
- Tablouri bidimensionale (matrici)
Ce fel de algoritmi vei implementa?
- Algoritmi pentru verificarea unor proprietati (paritate, numar prim, patrat perfect, etc)

O lista completa cu toti algoritmii din liceu, o gasiti aici: Algoritmi elementari de informatica la liceu
(linkurile albastre sunt tutoriale pentru care am scris un articol si filmat pe YouTube).

Mai intai trebuie sa decidem ce fel de structura de date vom folosii. In acest caz, vom avea de-a face cu un vector de cifre. De asemenea, mai trebuie sa memoram pentru fiecare cifra prima pozitie si ultima pozitie.

Asadar vom folosii urmtoarele structuri de date:

un vector cifraInitiala[10]
- cu semnificatia cifraInitiala[i] -> unde apare prima oara cifra “i” in fisier. Vom initializa tot vectorul cu “-1”.
un vector cifraFinala[10]
- cu semnificatia cifraFinala[i] -> unde apare ultima oara cifra “i” in fisier. Vom initializa tot vectorul cu “-1”.
o variabila care sa tina minte pozitia numarului curent
o variabila care sa tina minte cea mai mare diferenta

#include    <iostream>
#include    <fstream>

using namespace std;

ifstream fin("bac.txt");

int main()
{
    int cifraInitiala[10], cifraFinala[10];
    int pozitiaCurenta = 1, diferentaMaxima = 0;

    for(int cifra = 0; cifra < 10; cifra++)
    {
        cifraInitiala[cifra] = -1;
        cifraFinala[cifra] = -1;
    }

    int cifra;
    while(fin >> cifra)
    {
        if(cifraInitiala[cifra] == -1)
            cifraInitiala[cifra] = pozitiaCurenta;
        else
            cifraFinala[cifra] = pozitiaCurenta;

        pozitiaCurenta = pozitiaCurenta + 1;
    }

    for(int cifra = 0; cifra <= 9; cifra++)
    {
        if(cifraFinala[cifra] != -1 && cifraInitiala[cifra] != -1)
        { //Daca avem un interval valid (inceput - final)
            int diferenta = cifraFinala[cifra] - cifraInitiala[cifra];
            if(diferenta > diferentaMaxima)
                diferentaMaxima = diferenta; //determinam diferenta maxima
        }
    }

    cout << diferentaMaxima + 1 << "\n";

    for(int cifra = 0; cifra <= 9; cifra++)
    {
        if(cifraFinala[cifra] != -1 && cifraInitiala[cifra] != -1)
        {
            int diferenta = cifraFinala[cifra] - cifraInitiala[cifra];
            if(diferenta == diferentaMaxima)
                cout << cifra << " ";
        }
    }
    return 0;
}

Descrierea solutiei: Pentru a rezolva aceasta problema nu vom stoca intreg sirul de numere, deoarece nu este eficient sa folosim memoria pentru 100.000 elemente cand avem oportunitatea sa nu o facem.

Mai intai initializam cei doi vectori de aparitii cifraInitiala si cifraFinala cu -1. Deoarece dorim sa ii atribuim pe masura ce avanseaza citirea din fisier.

Mai apoi citim cifra cu cifra fisierul si verificam daca i-am atribuit un indice de pornire.

Daca cifraInitiala[cifra] nu a fost setata, o setam
Daca a fost setata, actualizam cifraFinala[cifra]. Spun actualizam, deoarece aceasta valoare se va suprascrie de fiecare data cand dam de aceeasi cifra mai tarziu.

La final parcurgem cei doi vectori si verificam daca este un interval valid (adica avem setat o pozitie initiala si una finala), iar mai apoi calculam diferenta intre cei doi vectori cifraFinala[cifraCurenta] si cifraInitiala[cifraCurenta]. Dupa ce am calculat diferentaMaxima, vom mai parcurge o data acest vector pentru a afisa cifrele care fac parte din acesta.

Algoritmul este eficient din punct de vedere al memoriei, deoarece folosim tot ceea ce declaram. De exemplu daca am fi stocat cifrele intr-un vector, exista posibilitatea ca o mare parte din acesta sa nu fie folosita. De asemenea, algoritmul are o complexitate in timp liniara O(N) – unde N este numarul de elemente din fisierul bac.txt.

Comentarii

Cum iei cat mai multe puncte la Bacalaureatul de Informatica

Subiectul I

Grila cu instructiunea if (Problema 1)

Problema pseudocod (Problema 2)

Subiectul II

Problema 1 si 2 (grilele pentru grafuri)

Graf neorientat

Graf orientat

Componente conexe

Graf partial

Subgraf

Lant elementar

Lant neelementar

Ciclu

Ciclu Hamiltonian

Ciclu Eulerian

Arbore

Problema 3 (struct)

Problema 4 (matricea)

Exemplul 1 (diagonala principala)

Exemplul 2 (diagonala secundara)

Exemplul 3 (diagonala secundara – triplata)

Exemplul 4 (diagonala principala si cea secundara + o observatie)

Exemplul 5 (numararea pana la n2)

Exemplul 6 (cel din problema)

Problema 5 (siruri de caractere)

Parcurgerea sirului, caracter cu caracter

Despartirea sirului in cuvinte

Subiectul III

Problema 1 (recursivitate)

Problema 2 (backtracking)

Problema 3 (subprograme / functii)

Problema 4 (“ultima problema”)

Cum sa faci un ProgressBar in C#

Generare factura/chitanta in C#

S-ar putea sa iti placa

Exemplul 5 (numararea pana la n²)