Va roggg
Numim pereche asemenea (x,y) două numere naturale, x și y, cu proprietatea că ultima cifră a lui x
este egală cu ultima cifră a lui y.
Fișierul numere. In conține numere naturale din intervalul [1,105]: pe prima linie două numere na și
nb, pe a doua linie un șir A de na numere, iar pe a treia linie un șir B de nb numere. Numerele aflate
pe aceeași linie a fișierului sunt separate prin câte un spațiu.
Se cere să se afișeze pe ecran numărul de perechi asemenea (x,y), cu proprietatea că x este un
termen al șirului A, iar y este un termen al șirului B. Proiectați un algoritm eficient din punctul de vedere
al timpului de executare.
Exemplu: dacă fișierul conține numerele
7 5
112 7 4 112 5013 824 10012
405 1024 321 52 6542
se afișează pe ecran numărul 8
deoarece sunt 8 perechi asemenea: (112,52), (112,6542), (4,1024), (112,52), (112,6542),
(824,1024), (10012,52), (10012,6542).
a. Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p. )
b. Scrieți programul C/C++ corespunzător algoritmului proiectat.
Răspunsuri la întrebare
a.
Algoritmul este eficient din punct de vedere al timpului de executare, întrucât are o structură liniară. Sunt citite ambele șiruri și sunt memorate aparițiile fiecărei cifre în ambele șiruri prin 2 vectori de frecvență. Numărul de perechi este aflat calculând suma produselor aparițiilor fiecărei cifre în cele 2 șiruri.
b.
#include <iostream>
#include <fstream>
using namespace std;
int main() {
ifstream fin("date.in");
int Na, Nb;
int cifrea[10] = {0}, cifreb[10] = {0};
fin >> Na >> Nb;
int x;
for (int i = 0; i < Na; i++) {
fin >> x;
int ultcifra = x % 10;
cifrea[ultcifra]++;
}
for (int i = 0; i < Nb; i++) {
fin >> x;
int ultcifra = x % 10;
cifreb[ultcifra]++;
}
int nrperechi = 0;
for (int i = 0; i < 10; i++)
nrperechi += cifrea[i] * cifreb[i];
cout << nrperechi << "\n";
return 0;
}