Question

Fisierul numere.in memorează numere naturale astfel:
- pe prima linie o valoarea naturală n (n<=100)
- pe a doua linie n valori naturale, de cel mult 9 cifre, ordonate crescător, separate prin spațiu
- pe a treia linie o valoare naturală m (m<=1000000)
- pe a patra linie m valori naturale, de cel mult 9 cifre, ordonate crescător, separate prin spațiu
Se cere să se afișeze crescător toate valorile distincte, din cele două șiruri, divizibile cu 3. Dacă nu există valori divizibile cu 3 se va afișa mesajul nu exista. Pentru determinarea valorilor cerute se utilizează un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.
Exemplu: dacă fisierul numere.in conține:
10
8 13 19 24 36 52 63 84 108 135
10
6 15 20 24 50 56 63 68 70 71
Pe ecran se va afișa:
6 15 24 36 63 84 108 135
a) Descrieţi în limbaj natural algoritmul utilizat, justificând eficienţa acestuia. (2p.)
b) Scrieţi programul C/C++ corespunzător algoritmului descris.

Answer 1

Răspuns:

#include <iostream>

#include <algorithm> // pentru functia sort (modalitate efficienta)

using namespace std;

int x[101], y[1000001], sir[1000103]; // initializam vectorii unde memoram valorile citite pe a doua, a patra linie, respectiv vectorul unde vom avea sortati vectorii

int main()

{

   int n, m, cnt = 0; // initializam n si m

   bool ok = false; // facem o variabila de tip boolean pentru a verifica daca avem numere divizibile cu 3

   // x reprezinta vectorul citita de n ori

   // y reprezinta vectorul citita de m ori

   cin >> n; // citim n

   for (int i = 1; i <= n; ++i) // for de la 1 la n, citim x de n ori

       cin >> x[i]; // citim x[i]

   cin >> m; // citim m

   for (int j = 1; j <= m; ++j) // for de la 1 la n, citim y de m ori

       cin >> y[j]; // citim y[i]

   

   for (int i = 1; i <= n; ++i) // for de la 1 la n, verificam care numere sunt divizibile cu 3

       if (x[i] % 3 == 0) // verificam daca numarul este divizibil cu 3

       {

           sir[cnt++] = x[i]; // dam valoare la sir, cea divizibila cu 3

           ok = true;

       }

   for (int j = 1; j <= n; ++j) // for de la 1 la n, verificam care numere sunt divizibile cu 3

       if (y[j] % 3 == 0) // verificam daca numarul este divizibil cu 3

       {

           sir[cnt++] = y[j]; // dam valoare la sir, cea divizibila cu 3

           ok = true;

       }

if (ok == true)

{

sort(sir + 1, sir + cnt + 1); // sortam efficient crescator

   for (int j = 2; j <= cnt; ++j) // for de la 2 (declaram global primul este 0, de accea de la 2) la cnt, unde am memorat cate numere divizibile avem

       cout << sir[j] << " "; // afisam sirul final, sortat

}

else

       cout <<  "NU EXISTA";

   return 0;

}

Explicație:

Explicația este făcut pe parcursul fiecărei linii .

Aici ai documentația pentru sortare : https://www.pbinfo.ro/articole/10743/stl-sort