Sari la conținut
EduCamp

Probleme rezolvate pe categorii

Tablouri unidimensionale

3 probleme Exerciții: 2Simulare bacalaureat: 1

Înainte de probleme Tiparul problemelor cu tablouri unidimensionale

Un tablou unidimensional, numit și vector, memorează mai multe valori de același tip, așezate una după alta. Fiecare element se accesează prin numele tabloului și indicele lui: a[i] este elementul de pe poziția i.

Problemele din această categorie folosesc aceleași operații:

  • citirea tabloului: întâi numărul de elemente, n, apoi cele n elemente;
  • parcurgerea tabloului, pentru prelucrarea fiecărui element;
  • construirea unui tablou nou din elementele altuia: copierea, divizarea;
  • numărarea aparițiilor fiecărei valori, cu un vector de frecvență;
  • afișarea elementelor, separate prin câte un spațiu.

Parcurgerea unui tablou

Parcurgerea unui tablou înseamnă vizitarea pe rând a elementelor lui, pentru una dintre prelucrările următoare:

  • atribuirea de valori elementelor;
  • folosirea valorilor elementelor în calculele cerute de problemă;
  • afișarea valorilor elementelor.

Elementele se vizitează în ordinea indicilor. Parcurgerea se poate face în două sensuri:

  • de la primul element la ultimul, cu indicele i de la 1 la n;
  • de la ultimul element la primul, cu indicele i de la n la 1.

Parcurgerea este o prelucrare repetitivă cu număr cunoscut de pași, deci se scrie cu instrucțiunea for.

Vectorul de frecvență

Când valorile din date sunt numere naturale mici, de exemplu din intervalul [0, 1000], aparițiile lor se numără într-un al doilea tablou, numit vector de frecvență. Elementul fr[v] reține de câte ori apare valoarea v. Tabloul are câte o poziție pentru fiecare valoare posibilă, iar toate elementele lui pornesc de la 0.

Pentru datele 4 9 4 1 9 4 2 se obține:

Valoarea v1249celelalte
fr[v]11320

Fiecare valoare citită mărește cu 1 elementul de pe poziția ei. Datele se parcurg o singură dată, iar apoi vectorul de frecvență se parcurge în ordinea valorilor.

Programul-șablon

Programul de mai jos are părțile care se repetă: declararea tabloului cu indici de la 1, citirea, parcurgerea în cele două sensuri și numărarea aparițiilor cu un vector de frecvență.

Problema 1 · Exercițiu Copierea unui tablou în alt tablou

Ce cere problema

După copiere, fiecare element al lui b are valoarea elementului de pe aceeași poziție din a:

Poziția i12345
a[i]7−21508
b[i]7−21508

Copierea se face prin parcurgerea simultană a vectorilor a și b, cu același indice i. La fiecare pas, elementul curent din b primește valoarea elementului curent din a.

Programul și descrierea metodei

În stânga este programul. În dreapta este metoda de rezolvare, descrisă în limbaj natural, cu pașii așezați pe niveluri după structura programului.

Problema 2 · Exercițiu Divizarea unui tablou în două tablouri

Ce cere problema

Primele m elemente ale lui a trec în b, pe aceleași poziții. Celelalte n − m elemente trec în c, începând de la poziția 1:

Poziția în a1234567
a[i]1258213106
Unde ajungeb[1]b[2]b[3]c[1]c[2]c[3]c[4]

Vectorul b are m elemente, iar vectorul c are n − m elemente. Elementul a[i], cu i > m, ajunge în c[i − m].

Programul și descrierea metodei

În stânga este programul. În dreapta este metoda de rezolvare, descrisă în limbaj natural, cu pașii așezați pe niveluri după structura programului.

Problema 3 · Simulare bacalaureat 2024 Șirul de tip api

Ce cere problema

Pentru fiecare valoare care apare în șir se verifică două condiții:

  • numărul de apariții este mai mic sau egal cu valoarea;
  • numărul de apariții și valoarea au aceeași paritate.

Pentru șirul din exemplu:

ValoareaAparițiiApariții ≤ valoare?Aceeași paritate?
22da, 2 ≤ 2da, amândouă pare
64da, 4 ≤ 6da, amândouă pare
142da, 2 ≤ 14da, amândouă pare
273da, 3 ≤ 27da, amândouă impare

Toate valorile îndeplinesc ambele condiții, deci se afișează DA. Dacă al doilea 2 din șir ar fi 3, valoarea 3 ar apărea o dată, iar valoarea 2 tot o dată: 1 și 2 au parități diferite, deci s-ar afișa NU.

Numerele din șir sunt cel mult 10³, deci aparițiile se numără într-un vector de frecvență cu 1001 de elemente.

Programul și descrierea metodei

În stânga este programul. În dreapta este metoda de rezolvare, descrisă în limbaj natural, cu pașii așezați pe niveluri după structura programului.

#include <iostream>
#include <fstream>
using namespace std;

int fr[1001];     // fr[v] = numarul de aparitii ale lui v

int main() {
    ifstream f("bac.in");
    int x;
    while (f >> x)
        fr[x]++;
    f.close();

    bool api = true;
    for (int v = 1; v <= 1000 && api; v++)
        if (fr[v] != 0)
            if (fr[v] > v || fr[v] % 2 != v % 2)
                api = false;

    if (api)
        cout << "DA";
    else
        cout << "NU";
    return 0;
}

Programul

  • vectorul de frecvență fr are câte o poziție pentru fiecare valoare de la 0 la 1000
    • fiind declarat în afara funcțiilor, are toate elementele egale cu 0
  • cât timp se poate citi un număr x din fișier
    • fr[x] crește cu 1
    • f >> x dă valoarea fals când nu mai sunt numere în fișier, deci citirea se oprește singură
  • api pornește de la true
  • pentru fiecare valoare v, de la 1 la 1000, cât timp api este true
    • dacă v apare în șir, adică fr[v] este diferit de 0
      • dacă fr[v] > v sau fr[v] și v au resturi diferite la împărțirea la 2, api devine false
  • se afișează DA dacă api este true, altfel NU

Materialul acesta se citește pe educamp.ro și nu se tipărește.

Vezi problemele rezolvate ca și cursant

Lista categoriilor, cu problemele date la examen în fiecare, se citește gratuit și integral. Pentru a citi rezolvările, te înscrii la cursul de pregătire.

Te înscrii, alegi în cont când începe cursul și plătești prima lună prin transfer bancar. Pentru a vedea mai întâi ce probleme s-au dat, poți reveni la lista categoriilor.

Acces la suportul de curs

25 RON / lună, fără ședințe

Ce cuprinde:

  • Acces la toate lecțiile disponibile
  • Suport de curs pentru tematica științifică și metodică
  • Exemple, explicații și exerciții
  • Acces la materialele noi adăugate pe platformă
  • Posibilitatea de a adresa întrebări

Înscrie-te Cum plătești Login