Question

Fișierul bac.txt conține pe prima linie un număr natural, n (1≤n≤10 la puterea 6), iar pe a doua linie
cel mult 1000000 de numere naturale de forma 2p (0≤p≤9), separate prin câte un spațiu.
Se cere să se afișeze pe ecran numărul care ar apărea pe poziția n în șirul ordonat strict
descrescător obținut din toate numerele distincte aflate pe a doua linie a fișierului. Dacă
șirul are mai puțin de n termeni distincți, se afișează pe ecran mesajul Nu exista.
Pentru determinarea numărului cerut se utilizează un algoritm eficient din punctul de
vedere al timpului de executare.
Exemplu: dacă fisierul bac.txt conine numerele
3
16 32 1 64 128 32 128 32 32
atunci pe ecran se afișează valoarea
32
a) Descrieti în limbaj natural algoritmul utilizat, justificând eficiența acestuia. (4p.)
b) Scrieti programul C/C++ corespunzător algoritmului descris

Answer 1

Indiferent cat este de lung sirul de numere, sunt 10 valori care pot aparea in sir(1,2,4,8,16,32,64,128,256,512) adica 2^p unde p este intre 0 si 9
Putem crea un vector v[10] care are fiecare indice reprezentant pentru o valoare a lui p.Vectorul va avea toate elementele 0 la inceput Cand incepem sa citim numerele, verificam care dintre numerele din sir este si apoi incrementam valoarea din vector cu 1
daca vedem 32, atunci v[5]=v[5]+1 si asa mai departe
La sfarsit, citim vectorul v de la cel mai mare v[9] la cel mai mic v[0] Daca elementul e mai mare decat 0, atunci apare in sir si incrementam o variabila s care sa arate cate elemente distincte sunt. Pornind de la cel mai mare, le luam in ordine descrescatoare. Atunci cand s ajunge la valoarea n, atunci 2 la puterea indicele respectiv reprezinta valoarea din sir.
Programul este eficient pentru ca citeste sirul o singura data, ocupa doar 10 locuri de memorie, si evitam sortarea sirului, doar citim elemente dintr-un vector restrans.
Codul mai jos
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

int v[10];
int main(){

ifstream f("bac.txt");
int n,a,nr,i,s=0,dummy,numere[100];
double rezultat=-1;
f>>n;
while(f>>a){
nr=0;
while(a>1){
nr++;
a=a/2;
}
v[nr]++;
}

for(i=9;i>=0;i--){
if(v[i]>0){
s++;
}
if(s==n){
rezultat=pow(2,i);
break;
}
}
if(rezultat==-1){
cout<<"Nu exista";
}
else{
cout<<"Rezultat:"<<rezultat;
}
return 0;
}