Question

Două numere naturale sunt numite z-prietene dacă au aceeași cifră a zecilor.
Fișierul bac.in conține un șir de cel mult 10⁶ numere naturale din intervalul [10,10⁹], separate prin
câte un spațiu. Se cere să se afișeze pe ecran pozițiile din șir pe care se află termeni precedați de un
număr maxim de valori z-prietene cu ei. Numerele afișate sunt separate prin câte un spațiu. Proiectați
un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul conține numerele 726 358 98 157 20 49 128 879 659 271
pe ecran se afișează numerele 7 9 (termenii 128, respectiv 659 respectă proprietatea cerută).
a. Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
b. Scrieți programul C/C++ corespunzător algoritmului proiectat.

Answer 1

Răspuns:

#include <iostream>

#include <fstream>

using namespace std;

ifstream f("bac.in");

int num, vf[10], z, n, poz[10];

int main()

{

   while (f >> num) {

       ++n;

       z=(num/10)%10;

       ++vf[z]; poz[z]=n;

   }

   int m=0;

   for (int i=0; i<10; i++) {

       if (vf[i]>m) m=vf[i];

   }

   for (int i=0; i<10; i++) {

       if (vf[i]==m) {

           cout << poz[i] << " ";

       }

   }

   return 0;

}

Explicație:

Paralel cu citirea numerelor din fișier se completează vectorul frecvenței cifrei zecilor și poziția numărului citit în șir.

Se determină valoarea maximă din vectorul frecvenței

Se afișează pozițiile numerelor în șir cu cele mai multe z-prietene