👤
a fost răspuns

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ăspuns :

CROW9920GO

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;

}

Vă mulțumim că ați vizitat site-ul nostru dedicat Informatică. Sperăm că informațiile oferite v-au fost de ajutor. Dacă aveți întrebări sau nevoie de asistență suplimentară, nu ezitați să ne contactați. Ne vedem curând și nu uitați să ne adăugați la marcaje!


Go Studies: Alte intrebari