Exerciții rezolvate pentru tipul CHAR la BAC

Operații de bază cu siruri de caractere

Sirurile de caractere în C++ sunt colecții de caractere stocate succesiv în memorie. Trebuie să înțelegi funcțiile principale pentru manipularea lor.

Funcția strlen(s) returnează lungimea efectivă a sirului, adică numărul de caractere până la caracterul null ('\0'). Când lucrezi cu siruri, această funcție este esențială pentru a itera prin toate caracterele.

Funcția strcpy(destinație, sursă) copiază conținutul unui sir în altul. Un exemplu clasic este strcpy(s2, s+4) care copiază în s2 sirului s începând de la poziția 4.

💡 Amintește-ți că indicii în sirurile de caractere încep de la 0, iar orice sir valid se termină cu '\0'.

Funcția strcat(destinație, sursă) concatenează (adaugă) sirul sursă la finalul sirului destinație. Funcția strchr(sir, caracter) caută prima apariție a unui caracter într-un sir și returnează un pointer către acea poziție sau NULL dacă nu găsește caracterul.

Pentru verificarea condițiilor în siruri (dacă un caracter este literă mică, mare, cifră), se folosesc operatorii de comparație și intervalele de caractere ASCII, cum ar fi s[i]>='a' && s[i]<='z' pentru a verifica dacă caracterul este literă mică.

Manipularea avansată a sirurilor

Când elimini caractere dintr-un sir, o tehnică frecventă este folosirea strcpy(s+i, s+i+1) care "șterge" caracterul de la poziția i prin suprascriere cu restul sirului. Această operație trebuie folosită cu atenție în bucle, deoarece lungimea sirului se modifică.

Pentru iterarea prin sir și manipularea caracterelor specifice, putem folosi bucle combinate cu funcții precum strchr. De exemplu, pentru eliminarea vocalelor:

while (i<strlen(s))
  if (strchr("aeiou", s[i]) != NULL)
    strcpy(s+i, s+i+1);
  else
    i++;

Compararea sirurilor se realizează cu strcmp(s1, s2), care returnează 0 dacă sirurile sunt identice, o valoare negativă dacă s1 este lexicografic mai mic decât s2, sau o valoare pozitivă în caz contrar.

Când modifici un sir în timpul iterării, trebuie să fii atent la actualizarea indexurilor. Dacă elimini un caracter, nu trebuie să incrementezi indexul, deoarece următorul caracter s-a mutat deja la poziția curentă.

💡 După fiecare operație care modifică un sir, verifică dacă trebuie să actualizezi și alți indici sau contori!

Funcții avansate și tehnici de procesare

Funcția strstr(sir, subsir) este extrem de utilă - caută un subsir în cadrul unui sir mai mare și returnează un pointer către prima apariție sau NULL dacă subsirul nu este găsit. Poți combina această funcție cu alte operații pentru manipulări complexe.

Pentru a verifica dacă un caracter face parte dintr-un set specific, folosește:

if(strchr("aeiou", s[i]) != NULL) 
  // caracterul s[i] este o vocală

Palindromul este un concept important - un sir care se citește la fel de la stânga la dreapta și de la dreapta la stânga. Pentru a verifica dacă un sir este palindrom, compari caracterele de la început cu cele de la sfârșit:

i=0; j=strlen(s)-1;
while (i<j)
  if (s[i] != s[j]) return false;
  else { i++; j--; }
return true;

💡 Când lucrezi cu expresii complicate care implică siruri, analizează pas cu pas ce face fiecare funcție și urmărește cum se modifică valorile variabilelor.

Transformarea între litere mari și mici se realizează folosind diferența dintre codurile ASCII: s[i] = s[i] - ('a' - 'A') transformă o literă mică în litera mare corespunzătoare.

Tehnici și funcții speciale pentru siruri

Funcția strncpy(dest, src, n) copiază cel mult n caractere din src în dest. Este utilă când vrei să copiezi doar o porțiune dintr-un sir.

Când lucrezi cu siruri în C++, gestionarea memoriei este esențială. După operații precum strncpy, trebuie adesea să adaugi manual caracterul nul:

strncpy(s, "informatica", 5);
s[5] = '\0'; // Asigurăm terminarea corectă a sirului

Numărarea caracterelor specifice dintr-un sir este o operație frecventă. De exemplu, pentru a număra cifrele:

k = 0;
for (i=0; i<strlen(s); i++)
  if (s[i]>='0' && s[i]<='9')
    k++;

Compararea sirurilor folosind strcmp este esențială pentru verificarea egalității. Expresia strcmp(s1, s2)==0 este adevărată când s1 și s2 sunt identice.

💡 Amintește-ți că strcmp este sensibil la majuscule, deci "abc" și "ABC" sunt considerate diferite!

Pentru a lucra cu caractere specifice într-un sir, poți folosi bucle for combinate cu condiții pentru a identifica și procesa doar caracterele dorite (litere, cifre, semne de punctuație).

Algoritmi pentru siruri de caractere

Verificarea parității lungimii unui sir se face elegant cu expresia strlen(s) % 2 == 0. Acest lucru este util în multe probleme practice.

Când concatenezi siruri folosind strcat, trebuie să te asiguri că sirul destinație are suficient spațiu alocat pentru a primi și caracterele din sirul sursă:

char s3[50] = "ritm";
strcat(s3, s1); // s3 devine "ritmalgoritmi"

Funcția strcat adaugă sirul sursă la finalul sirului destinație și actualizează automat caracterul nul.

Pentru a găsi anumite caracterele într-un sir, poți folosi strchr. O expresie ca strchr(s, 'a') != 0 && strchr(s, 'b') != 0 verifică dacă sirul s conține atât caracterul 'a' cât și caracterul 'b'.

Extragerea subșirurilor se realizează folosind combinații de funcții precum strstr și strcpy. De exemplu, pentru a extrage un subsir după un anumit caracter:

strcpy(s, strstr(s, "+")+1); // Copiază în s textul de după primul "+"

💡 În probleme reale, va trebui adesea să combini mai multe funcții de sir pentru a obține rezultatul dorit. Scrie și testează codul pas cu pas!

Transformări și algoritmi complexi pentru siruri

Transformarea literelor între majuscule și minuscule este o operație frecventă. Diferența dintre codul ASCII al unei litere mari și al celei mici corespunzătoare este constantă:

for(i=0; i<strlen(x); i++)
  if(x[i] >='A' && x[i] <='N')
    x[i] = x[i] + 'a'-'A'; // Transformă în literă mică

Verificarea proprietăților unui sir este esențială în multe aplicații. Pentru a verifica dacă un sir conține doar cifre:

bool numericOnly = true;
for(i=0; i<strlen(s); i++)
  if(s[i]<'0' || s[i]>'9')
    numericOnly = false;

Când lucrezi cu palindroame, verificarea se simplifică pentru siruri de lungime fixă. Pentru un sir de 3 caractere, verifici doar dacă s[0]==s[2].

💡 În probleme complexe, împarte soluția în pași mai mici. De exemplu, pentru a verifica dacă un sir conține doar litere, mai întâi definește ce înseamnă "literă" și apoi verifică fiecare caracter.

Funcțiile de sir combinate cu bucle condiționate pot crea algoritmi puternici. De exemplu, pentru a filtra doar literele dintr-un sir:

for(i=0; i<strlen(s); i++)
  if((s[i]>='a' && s[i]<='z') || (s[i]>='A' && s[i]<='Z'))
    cout<<s[i];

Probleme practice și tehnici avansate

Funcțiile de prelucrare a sirurilor îți permit să rezolvi probleme complexe prin combinarea lor inteligentă. Iată câteva tehnici esențiale:

Generarea prefixelor unui sir înseamnă afișarea tuturor subșirurilor care încep de la primul caracter:

for(i=1; i<=strlen(s); i++) {
  strncpy(temp, s, i);
  temp[i] = '\0';
  cout << temp << endl;
}

Generarea sufixelor implică afișarea tuturor subșirurilor care se termină cu ultimul caracter:

for(i=0; i<strlen(s); i++) {
  cout << s+i << endl;
}

💡 Mulți algoritmi eficienți pentru siruri încep prin identificarea caracteristicilor importante ale datelor, cum ar fi separatorii, vocalele sau cifrele.

Probleme precum înlocuirea vocalelor cu perechi vocală-Vocală se rezolvă parcurgând sirul și identificând vocalele:

for(i=0; i<strlen(s); i++) {
  if(strchr("aeiou", s[i]) != NULL) {
    // Înlocuiește cu vocala urmată de versiunea sa majusculă
  }
}

Transformarea textului cu reguli specifice, cum ar fi capitalizarea primelor litere, este utilă în multe aplicații practice:

bool newWord = true;
for(i=0; i<strlen(s); i++) {
  if(s[i] == ' ') newWord = true;
  else if(newWord) {
    s[i] = toupper(s[i]);
    newWord = false;
  }
}

Algoritmi avansați pentru procesarea sirurilor

Când lucrezi cu texte și propoziții complexe, trebuie să manipulezi sirurile la nivel de cuvânt. Pentru a extrage cuvinte dintr-un text, poți folosi separatori precum spațiile:

char *p = strtok(text, " ");
while(p != NULL) {
  // Prelucrează cuvântul p
  p = strtok(NULL, " ");
}

Problema găsirii clonelor (variante ale unui cuvânt cu o vocală eliminată) este un exemplu bun de algoritm recursiv pentru siruri:

for(char v : "aeiou") {
  // Creează o clonă eliminând vocala v
  // Afișează clona
}

Pentru a rezolva problema căutării celui mai lung sufix comun, compari caracterele de la sfârșitul sirurilor:

i = strlen(s1) - 1;
j = strlen(s2) - 1;
while(i >= 0 && j >= 0 && s1[i] == s2[j]) {
  i--; j--;
}
// Extrage sufixul comun

💡 În probleme complexe, desenează pe hârtie ce se întâmplă cu sirurile pas cu pas. Este mult mai ușor să vizualizezi operațiile decât să încerci să le păstrezi toate în minte.

Pentru a găsi secvențe de caractere care respectă anumite reguli (de exemplu, perechi de caractere identice), folosește o buclă pentru a verifica fiecare poziție:

for(i=0; i<strlen(s)-1; i++) {
  if(s[i] == s[i+1]) {
    cout << s[i] << s[i+1] << endl;
  }
}

Rezolvarea și urmărirea exemplelor

Pentru a rezolva problemele cu siruri de caractere, este esențial să înțelegi cum se execută codul pas cu pas. Urmărirea execuției îți permite să vezi cum se modifică valorile variabilelor.

Problema abcdefghoid devine abedghd după eliminarea vocalelor. Iată cum se execută algoritmul:

i=0: 'a' este vocală -> elimină -> s="bcdefghoid", i rămâne 0
i=0: 'b' nu este vocală -> i=1
i=1: 'c' nu este vocală -> i=2
i=2: 'd' nu este vocală -> i=3
i=3: 'e' este vocală -> elimină -> s="bcdfghoid", i rămâne 3
... și așa mai departe

💡 Pentru a evita erorile, scrie pe hârtie starea sirului după fiecare operație, mai ales când lucrezi cu bucle și modifici sirul în proces.

Pentru problema cu palindromul, analizând abcduecda, algoritmul verifică dacă caracterele de la pozițiile simetrice sunt egale:

s[0]='a' și s[8]='a' -> sunt egale -> continuă
s[1]='b' și s[7]='d' -> nu sunt egale -> nu este palindrom

Algoritmul care elimină anumite caractere și apoi verifică restul trebuie urmărit cu atenție, deoarece lungimea sirului se modifică în timpul execuției.

Exemple și probleme complexe rezolvate

Pentru problema în care se afișează doar caracterele care nu sunt cifre din bac 2009, algoritmul parcurge sirul și verifică fiecare caracter:

s[0]='b': nu este cifră -> afișează 'b'
s[1]='a': nu este cifră -> afișează 'a'
s[2]='c': nu este cifră -> afișează 'c'
s[3]=' ': nu este cifră -> afișează ' '
s[4]='2': este cifră -> ignoră
...

Rezultatul va fi "bac ".

În problema unde a = "alphabet" și se execută strlen(strcpy(s, s+2)), rezultatul este 5 deoarece:

1. s+2 reprezintă sirul începând de la poziția 2: "phabet"
2. strcpy(s, s+2) copiază "phabet" în s
3. strlen(s) returnează lungimea lui s, care acum este 6

💡 Când operezi cu funcții care returnează pointeri la siruri, cum ar fi strstr sau strchr, asigură-te că verifici dacă rezultatul nu este NULL înainte de a-l folosi!

Pentru a verifica dacă un sir este palindrom, compari primul caracter cu ultimul, al doilea cu penultimul și așa mai departe:

bool isPalindrome = true;
for(i=0; i<strlen(s)/2; i++) {
  if(s[i] != s[strlen(s)-i-1]) {
    isPalindrome = false;
    break;
  }
}

Problemele complexe se rezolvă adesea prin descompunerea lor în subprobleme mai simple și aplicarea tehnicilor de bază pentru siruri.