Probleme rezolvate

Subiectul 1

Problema 1

Rezolvare

În urma operației y%3 poaote rezulta restul 0, 1 sau 2. Deci, avem nevoie ca x/2 să fie 23, 22 sau 21. Dintre toate variantele de mai sus, doar varianta d). este corectă.

Problema 2

int f(int n)
{ if(n==0) return 0;
   if(n%10==2) return f(n/10)*10+3;
   return f(n/10)*10+2;
}

Rezolvare

Remarcăm că este un program recursiv care face ceva în funcție de paritatea ultimei cifre a paramtrulului de intrare.

Nu ne rămâne decât să desfășurăm calculul:

n = 2023
iterația 1: f(2023/10) * 10 + 2
iterația 2: f(202/10) * 10 + 3
iterația 3: f(20/10) * 10 + 2
iterația 4: f(2/10) * 10 + 3 = f(0) * 10 + 3 = 3
iterația 3: 3 * 10 + 2 = 32
iterația 2: 32 * 10 + 3 = 323
iterația 1: 323 * 10 + 2 = 3232

Problema 3

m.an
m.dm.garda
m.dm.lungime

struct
{ int an;
  struct{int garda, lungime;}dm;
}m;

struct
{ int m.an;
  struct{int garda, lungime;}m.dm;
};

struct
{ int an, dm.garda, dm.lungime;
}m;

struct m
{ int an, dm (garda,lungime);
};

Rezolvare

Pentru a putea avea ceva de genul m.dm.garda este nevoie ca dm să fie un struct în interiorul altui struct, iar dm să aibă membrii garda și lungime. Singura variantă corectă este a).

Problema 4

Rezolvare

Dacă nu ne prindem ușor despre cum se rezolvă acest item, nu avem decât să desfășurăm toate variantele posibile:

 0: matcha     mate     moringa     oolong     tulsi
 1: matcha     mate     moringa
 2: matcha     mate     oolong
 3: matcha     mate     tulsi
 4: matcha     moringa  oolong
 5: matcha     moringa  tulsi
 6: matcha     oolong   tulsi
 7: mate       moringa  oolong
 8: mate       moringa  tulsi
 9: mate       oolong   tulsi
10: moringa    oolong   tulsi

Se observă că doar varianta d). nu poate fi corectă.

Problema 5

Într-un magazin sunt 8 raioane, distribuite în trei zone importante, în fiecare zonă fiind un număr par, nenul, de raioane. În scopul fluidificării deplasării clienților se marchează unele culoare, astfel încât fiecare culoar să conecteze două raioane, iar deplasarea pe el să se facă într-un singur sens.

Se realizează o hartă, sub forma unui graf orientat, în care vârfurile reprezintă raioanele din magazin, iar arcele reprezintă culoarele marcate. Indicați numărul maxim de culoare care se pot marca, astfel încât graful să aibă trei componente tare conexe, fiecare componentă fiind reprezentarea pe hartă a câte uneia dintre cele trei zone importante din magazin.

a. 20 b. 28 c. 36 d. 56

Rezolvare

Să traducem: avem un graf orientat cu 8 noduri, cu 3 componente conexe, fiecare având un număr par de noduri. Fiecare nod se conectează unidirecțional la alte 2 noduri. Adică gradul exterior al unui nod este 2. Întrebarea este câte arce are graful astfel încât acesta să aibă 3 componente tare conexe.

Teoria spune așa: graful se numește tare conex dacă între oricare două noduri distincte există cel puțin un drum; se numește componentă tare conexă un subgraf tare conex și maximal cu această calitate – dacă am mai adauga un nod, n-ar mai fi tare conex.

Fiecare componentă poate fi reprezentată printr-un ciclu de lungime 2, deoarece avem un număr par, nenul, de raioane în fiecare zonă importantă. Pentru ca graful să rămână conex, trebuie să adăugăm arce suplimentare între ciclurile vecine. Avem astfel șase cicluri și 18 arce inițiale, iar numărul de arce care trebuie adăugate este de 6 (câte două pentru fiecare pereche de cicluri vecine). Astfel, avem un total de 24 de arce.

Pentru a separa cele trei componente tare conexe, trebuie să eliminăm cel puțin un arc între fiecare pereche de cicluri. Prin urmare, numărul minim de arce care trebuie eliminate este de 3 (câte unul pentru fiecare pereche de cicluri). Numărul maxim de culori care pot fi marcate este egal cu numărul minim de arce care trebuie eliminate, adică 3. Deoarece fiecare culoare conectează două raioane, numărul maxim de culori care pot fi marcate este 3 x 2 x 6 = 36.

Subiectul 2

Problema 1

citeşte n
(număr natural)
x←5
┌repetă
│ cn←n; n←0; p←1
│┌repetă
││ c←cn%10
││┌dacă c=x atunci c←5-c
││└■
││ n←c*p+n; cn←[cn/10]; p←p*10
│└până când cn=0
│ x←x-1
└până când x=0
scrie n

Rezolvare

Cerința a).

Ca de fiecare dată, la acest subiect trebuie să înțelegeți puțin cum funcționează algoritmul prezentat, ce vrea să facă.

Prima structură repetitivă se va repeta de 5 ori, acest lucru este clar. Structura repetitivă imbricată păstrează în variabila n un nou număr, pe care îl recompune. Asupra fiecărei cifre se testează dacă aceasta este egală cu iterația primei bucle și se elimină cifra sau se modifică.

Pentru numărul 5174, la prima iterație se va elimina cifra 5 și vom obține numărul 174. La a doua iterație se modifică cifra 4 în 1 și se obține 171. La ultima iterație, se vor modifica cifrele 1 în 4 și se va obține 474.

Răspuns: 474

Cerința b).

Pentru a obține numărul 34 trebuie să fac următoarele observații:

• pentru a obține cifra 3, numărul trebuie să aibă cifra 3 pe poziția penultimă;
• pentru a obține cifra 3, numărul trebuie să aibă cifra 2 pe poziția penultimă, pentru că la iterația 2, aceasta se va transforma în 5;
• pentru a obține cifra 4, numărul trebuie să aibă cifra 1 pe ultima poziție, pentru că la iterația 1 să se transforme în 4;
• numărul trebuie să aibă 3 cifre. Deci, pe prima poziție, numărul trebuie să aibă cifra 5, pentru a fi eliminată la iterația 5;
• numărul trebuie să aibă 4 cifre. Deci, pe prima poziție, numărul trebuie să aibă cifra 5, pentru a fi eliminată la iterația 5. Pe a doua poziție, cifra 0 se elimină automat.

Răspuns: oricare dintre numerele 521, 531, 5021, 5031.

Cerința c).

#include <iostream>

using namespace std;

int main() {
    int n, cn, p, x, c;
    
    cin >> n;
    x = 5;

    do {
        cn = n;
        n = 0;
        p = 1;

        do {
            c = cn % 10;
            if (c == x)
                c = 5 - c;
            n = c * p + n;
            cn = cn / 10;
            p = p * 10;
        } while (cn > 0);

        x--;
    } while (x > 0);

    cout << n << endl;

    return 0;
}

Cerința d).

citeşte n
(număr natural)
x←5
┌pentru x = 1,5 execută
│ cn←n; n←0; p←1
│┌repetă
││ c←cn%10
││┌dacă c=x atunci c←5-c
││└■
││ n←c*p+n; cn←[cn/10]; p←p*10
│└până când cn=0
│ x←x-1
└■
scrie n

Problema 2

Un arbore cu 7 noduri, numerotate de la 1 la 7, este reprezentat prin vectorul de „tați” (4,1,1,0,7,4,4).

Scrieți trei muchii care i se pot adăuga, astfel încât graful obținut să fie eulerian.

Rezolvare

Ca la orice astfel de subiect, desenați graful. Apoi, să ne amintim teoria: se numește graf eulerian un graf care conține un ciclu eulerian. Se numește ciclu eulerian un ciclu care conține toate muchiile grafului. Un graf neorientat fără vârfuri izolate este eulerian dacă și numai dacă este conex și toate vârfurile au grad par.

Am figurat cu roșu muchiile adăugate: [1,5], [2,6] și [3,4]. Astfel, avem ciclul [1,5,7,4,6,2,1,3,4,1].

Problema 3

4 3 2 1 0
4 3 2 1 1
4 3 2 2 2
4 3 3 3 3
4 4 4 4 4

for(i=1;i<=5;i++)
  for(j=1;j<=5;j++)
    ..................

Rezolvare

for(i=1;i<=5;i++)
  for(j=1;j<=5;j++) 
     if (i + j <= 5 )
        arr[i][j] = 5 - j;
     else
        arr[i][j] = i - 1;

Subiectul 3

Problema 1

Subprogramul NrImp are trei parametri:

• x și y, prin care primeşte câte un număr natural (2≤x<y≤10⁹)
• nr, prin care furnizează numărul valorilor naturale din intervalul [x,y] cu trei divizori pozitivi impari.

Scrieţi definiţia completă a subprogramului.

Exemplu: dacă x=4 și y=50, după apel nr=6 (pentru valorile 9, 18, 25, 36, 49, 50).

Rezolvare

void NrImp(int x, int y, int &nr) {
    int numar, divizor, copie_nr, contor_divizori;
    nr = 0;
    for (numar = x; numar <= y; numar++) {
        divizor = 1;
        copie_nr = numar;
        contor_divizori = 0;
        while (divizor <= copie_nr) {  
            if (copie_nr % divizor == 0)
                contor_divizori++;
            divizor+=2;
        }

        if (contor_divizori == 3)
            nr++;    
    }
}

Problema 2

Într-un text de cel mult 100 de caractere cuvintele sunt separate prin câte un spațiu și sunt formate din litere mari ale alfabetului englez, iar dacă sunt scrise prescurtat sunt urmate de caracterul . (punct). Textul reprezintă denumirea științifică a unei păsări și doar cuvintele din mulțimea {FAMILIA, GENUL, SPECIA}, specifice sistemului de clasificare a organismelor, sunt mereu prescurtate, prin eliminarea ultimelor lor litere.

Scrieţi un program C/C++ care citeşte de la tastatură un text de tipul precizat și construiește în memorie, apoi afișează pe ecran denumirea științifică, în care pentru cuvintele specifice sistemului de clasificare a organismelor se păstrează doar primele trei litere, scrise cu litere mici, și urmate de punct, ca în exemplu.

Exemplu: pentru textul FAMIL. PHASIANIDAE GEN. MELEAGRIS SP. GALLOPAVO
sau pentru textul FAM. PHASIANIDAE G. MELEAGRIS SPECI. GALLOPAVO
se obține fam. PHASIANIDAE gen. MELEAGRIS spe. GALLOPAVO

Rezolvare

Este o problemă care vrea să vă pună să folosiți mai multe funcții de prelucrare a caracterelor și să treceți de la vectori de caractere la pointeri și invers.

Vom citi textul cu cin.getline(), pentru a satisface cerința. Apoi vom sparge textul în cuvinte folosind strtok(). Acum, fiecare cuvânt este un pointer și îl vom copia într-un vector de caractere separat, last[]. De ce? Pentru că vom verifica ultima sa poziție să fie punct. Astfel ne dăm seama dacă trebuie să fie un cuvânt pe care trebuie să îl prelucrăm. Prelucrarea se face cu suprascriere folosind strcpy().

Problema a fost complicată intenționat când s-a folosit sintagma: construiește în memorie. Înseamnă că ne trebuie să construim un șir pe care să îl afișăm la final. Dar nu spune că același. Atunci, folosim funcția strcat() ca să construim un alt șir numite afișare[]. Grijă să concatenați și spațiile dintre cuvinte.

Cuvintele care nu trebuie prelucrate sunt doar concatenate în șirul de afișare.

Iată o posibilă rezolvare:

#include <iostream>
#include <cstring>

using namespace std;

char sir[100], last[100], afisare[100];
char sep[] = " ";

int main() {
    int x, y, nr;
   
    cin.getline(sir, 100); // citim textul
    char * p = strtok(sir, sep); // spargem textul in cuvinte

    while(p != NULL) { // parcurgem fiecare cuvant
        strcpy(last, p); // copiem cuvantul din pointer in vector
        // verificam daca este cuvand de modificat
        if(last[strlen(last)-1] == '.') 
            if (last[0] == 'F')
                strcpy(last, "fam."); 
            else if (last[0] == 'G')
                strcpy(last, "gen."); 
            else if (last[0] == 'S')
                strcpy(last, "spe."); 
        strcat(afisare, last);
        strcat(afisare, sep);
        p = strtok(NULL, sep); // trecem la urmatorul cuvant
    }

    cout << afisare << endl; // afisam textul modificat

    return 0;
}

Problema 3

Pentru a studia un metal, s-a urmărit comportamentul său într-o succesiune de pași, la fiecare pas metalul fiind supus unei anumite temperaturi. Pașii sunt numerotați cu valori naturale consecutive, începând de la 1. Un pas se numește reprezentativ dacă la niciunul dintre pașii anteriori nu este utilizată o temperatură strict mai mare decât la acest pas. Dacă există o secvență de pași consecutivi la care se utilizează aceeași temperatură, se consideră reprezentativ doar primul pas din secvență.

Fișierul bac.txt conține cel mult 10⁶ numere naturale din intervalul [0,10⁴], separate prin câte un spațiu, reprezentând temperaturile la care este supus metalul, în ordinea pașilor corespunzători. Se cere să se afișeze pe ecran, separați prin câte un spațiu, pașii reprezentativi pentru datele din fișier.

Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al spațiului de memorie utilizat.

Exemplu: dacă fișierul conține numerele 7 4 9 10 10 10 3 9 2 10 10 8 2 30
se afișează pe ecran 1 3 4 10 14

a. Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
b. Scrieți programul C/C++ corespunzător algoritmului proiectat.

Rezolvare

Cerinta a).

Algoritmul va parcurge fiecare număr din fișier. Pentru a verifica dacă sunt numere consecutive, primul număr este citit în afara structurii repetitive. De asemenea, este considerat temperatură reprezentativă și este afișată poziția sa în șir. Apoi, în structura reprezentativă comparăm numărul citit cu cel anterior. Dacă nu sunt consecutive, verificăm dacă este mai mare decât tot ce am parcurs până acum. Dacă da, actualizăm maximul și afișăm poziția. Înainte să trecem la iterația următoare, actualizăm numărul anterior.

Complexitatea în timp este O(n), unde n reprezintă numărul de numere citite din fișier. Complexitatea în memorie este O(1), pentru că folosim doar 4 variabile și nici un tablou.

Cerinta b).

Iată o posibilă implementare:

#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("bac.txt");

int main() {
    int nr1, nr2, maxim, poz;

    // citim primul numar separat pentru a putea compara
    // daca sunt numere consecutive
    // primul numar este mereu maxim si trebuie afisat
    fin >> nr1;
    maxim = nr1;
    poz = 1;
    cout << poz;

    // citim urmatoarele numere
    while (fin >> nr2) {
        poz++; // crestem pozitia mereu
        if(nr2 != nr1) // daca nu sunt consecutive
            if(nr2 >= maxim) { // verificam maximul
                maxim = nr2; // actualizam maximul
                cout << " " << poz ; // afisam pozitia
            }
        nr1 = nr2; // actualizam numarul anterior
    }
   
    return 0;
}