Question

Fișierul text bac.in conține, pe prima linie, cel mult 1000000 de numere naturale
nenule, fiecare fiind format din cel mult 9 cifre. Oricare două numere aflate pe poziții
consecutive sunt despărțite printr-un spațiu.
Scrieți un program care, folosind un algoritm eficient din punct de vedere al timpului
de executare și al spațiului de memorie utilizat, determină și scrie în
fișierul bac.out cel mai mare număr natural care se poate obține din cifrele tuturor
numerelor din fișierul bac.in.
Exemplu: dacă fișierul bac.in conține numerele 2117 90 885 515 37, atunci
fișierul bac.out trebuie să conțină numărul 98877555321110.

Answer 1

Program C++

#include <iostream>

#include <fstream>

using namespace std;

ifstream f("bac.in");

ofstream g("bac.out");

int main()

{

   unsigned x, v[10] = { 0 };

   int i;

   //Cat timp exista numere in fisier citeste

   while (f) {

       f >> x;

       //Descompune numar in cifre. Incrementeaza elementele corespunzatoare cifrelor gasite

       while (x) {

           v[x % 10]++;

           x = x / 10;

       }

   }

   //Afiseaza numarul format

   for (i = 9; i >= 0; i--) {

       //Afiseaza cate o cifra pentru fiecare valoare din vector

       while (v[i]) {

           g << i;

           v[i]--;

       }

   }

}

Explicatie :

Folosim un vector v cu 10 pozitii (de la 0 la 9). Pe fiecare pozitie memoram numarul de cifre gasite in toate valorile citite din fisier.

La final, pentru a forma cel mai mare numar cu aceste cifre parcurgem vectorul in sens invers (de la 9 la 0) si afisam pozitia pe care suntem (cifra corespunzatoare) de atatea ori cat indica valoarea din vector.

• Algoritmul e eficient dpdv al timpului de executie pentru ca trecerea prin sirul de numere realizandu-se o singura data.

• Algoritmul e eficient dpdv al spatiului pentru ca valorile citite nu sunt memorate. Sunt folosite doar variabile simple si un tablou unidimensional de 10 elemente.