Fişierul bac.txt conține numere naturale din intervalul [2,106]: pe prima linie n, iar pe a doua linie
un șir de n numere, separate prin câte un spațiu.
Se cere să se afișeze pe ecran, pentru fiecare număr natural i (i[1,n]), cea mai mare dintre primele
i valori ale șirului aflat în fișier. Numerele afișate sunt separate prin câte un spațiu. Proiectați un
algoritm eficient din punctul de vedere al memoriei utilizate şi al timpului de executare.
Exemplu: dacă fișierul are conținutul alăturat, se afișează pe ecran
4 6 6 7 8 8 8 8 8 9 10 10
12
4 6 3 7 8 1 6 2 7 9 10 8
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)
Programul citeste din fisier un numar n si n numere. Acesta, la fiecare pas, calculeaza maximul dintre numerele citite si il afiseaza. Algoritmul este eficient din punct de vedere al memorie utilizate deoarece foloseste un numar restrans de variabile simple. Este eficient si din punct de vedere al timpului de executare deoarece citeste numerele din fisier o singura data, in acelasi timp rezolvand si cerinta ceruta, rezultand o complexitate liniara O(n) unde n este numarul de numere, citit din fisier.
b)
#include<iostream>
#include<fstream>
using namespace std;
int main(){
int maxcurent=-1,n,i;
ifstream f("bac.txt");
f>>n;
while(n!=0){
f>>i;
if(i>maxcurent)
maxcurent=i;
cout<<maxcurent<<' ';
n--;
}
f.close();
return 0;
}