Question

Test3 antrenament 2021 prob eficienta
-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 106 numere naturale din intervalul [10,109], 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. (2p.)
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:

folosim un vector de frecvență a cifrei zecilor a numerelor citite din fișier.

Astfel vom memora câte numere precedente numărului curent citit au aceeași cifră a zecilor. Totodată memorăm în vectorul poz poziția în șir a ultimului număr citit care are cifra zecilor z.

Aflăm valoarea maximă m din vectorul de frecvență vf

Parcurgem vf, și afișem din poz poziția numărului din șir cu valoarea în vf egală cu m.

Sper că codul e clar...