Fișierul bac.txt conține un șir de cel mult 106 numere naturale din intervalul [0,109].
Se cere să se determine și să se afișeze pe ecran, separate printr-un spațiu, ultimele două numere
impare (nu neapărat distincte) din șirul aflat în fișier, sau mesajul nu exista, dacă nu există două
astfel de numere. Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului
de executare.
Exemplu: dacă fișierul conține valorile 122 1635 628 1413 1647 900 3001 4252
se afișează pe ecran 1647 3001
a. Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
b. Scrieți programul C/C++ corespunzător algoritmului proiectat.
Răspunsuri la întrebare
a) Programul citeste numere din fisier, iar daca numarul curent este impar, se salveaza in z, y fiind rescris cu valoarea lui z, pentru a retine ultimul numar impar citit drept penultimul. La final, daca y este -1, sau z, se afiseaza "nu exista", altfel se vor afisa numerele cerute. Algoritmul este eficient din punct de vedere al memoriei utilizate deoarece foloseste un numar restrans de variabile simple. Este eficient si din punct de vedere al timpului de executare deoarece rezolva problema liniar, rezultand o complexitate O(n), n fiind numarul de numere din fisier.
b)
#include<iostream>
#include<fstream>
using namespace std;
int main(){
int x,y=-1,z=-1;
ifstream f("bac.txt");
while(f>>x)
if(x%2==1){
y=z;
z=x;
}
f.close();
if(y==-1||z==-1)
cout<<"nu exista";
else
cout<<y<<' '<<z;
return 0;
}