12/14 - Probleme eficiente BAC

1. Fişierul BAC.TXT are pe prima linie două numere naturale n şi m (0<n<1000, 0<m<1000)
separate prin câte un spaţiu, pe linia a doua n numere întregi ordonate strict crescător, iar
pe linia a treia m numere naturale distincte. Numerele din fişier aflate pe linia a doua şi a
treia au cel mult 6 cifre fiecare şi sunt despărţite în cadrul liniei prin câte un spaţiu. Să se
scrie un program care citeşte toate numerele din fişier şi afişează pe ecran, despărţite prin
câte un spaţiu, toate numerele de pe a doua linie a fişierului care apar şi pe linia a treia a
acestuia.
Exemplu: dacă fişierul are următorul conţinut:
6 5
2 3 4 5 8 9
4 5 2 11 8
atunci se va afişa: 5 2 8 4, nu neapărat în această ordine.
a) Descrieţi în limbaj natural o metodă de rezolvare eficientă ca timp de executare. (4p.)
b) Scrieţi programul C/C++ corespunzător metodei descrise la punctul a). (6p.)

#include<fstream>
#include<iostream>
using namespace std;
int binar(int a[],int x, int st, int dr)
{int m;
if(st>dr)
    return -1;
m=(st+dr)/2;
if(a[m]>x)
    return binar(a,x,st,m-1);
else if(a[m]<x)
    return binar(a,x,m+1,dr);
else return m;
}
int main()
{int n,m,a[100],p;
ifstream f("bac.txt");
clock_t x,y;
x=clock();
f>>n>>m;
for(int i=1;i<=n;i++)
    f>>a[i];
while(f>>p)
    if(binar(a,p,1,n)!=-1)
        cout<<p<<" ";
f.close();
y=clock();
cout<<endl<<"Timp de executie "<<(double)(y-x)/CLOCKS_PER_SEC<<" secunde";
}

2. Fişierul text bac.in conţine pe prima sa linie un număr natural n (0<n<10000), iar pe
următoarea linie n numere naturale din intervalul [1,100] separate prin câte un spaţiu.
Se cere să se citescă din fişier toate numerele şi să se afişeze pe ecran numărul sau
numerele care apar de cele mai multe ori printre numerele citite de pe a doua linie a
fişierului. Numerele afişate vor fi separate prin câte un spaţiu. Alegeţi un algoritm de
rezolvare eficient atât din punctul de vedere al timpului de executare cât şi al gestionării
memoriei. .
Exemplu: dacă fişierul bac.in are următorul conţinut:
12
1 2 2 3 2 9 3 3 9 9 7 1
pe ecran se vor afişa valorile 2, 3 şi 9, nu neapărat în această ordine.
a) Explicaţi în limbaj natural metoda utilizată justificând eficienţa acesteia (4-6 rânduri) (4p.)
b) Scrieţi programul C/C++ ce rezolvă problema enunţată, corespunzător metodei
descrise la punctul a). (6p.)

#include<fstream>
#include<iostream>
using namespace std;
int main()
{int n,m=0,mm=0,v[100]={0},i;
ifstream f("bac.txt");
clock_t x,y;
x=clock();
f>>n;
while(f>>n)
{v[n]++;
if(v[n]>m)
    m=v[n];
if(n>mm)
    mm=n;}
for(i=1;i<=mm;i++)
    if(v[i]==m)
        cout<<i<<" ";
f.close();
y=clock();
cout<<endl<<"Timp de executie "<<(double)(y-x)/CLOCKS_PER_SEC<<" secunde";
}

3. Se citeşte de pe prima linie a fişierului numere.in un număr natural n (0<n<10000) şi, de pe a doua linie a fişierului, n numere naturale din intervalul [1,100] şi se cere să se
afişeze pe ecran, în ordine crescătoare, despărţite prin câte un spaţiu, numărul sau
numerele întregi din intervalul [1,100] care nu apar printre numerele citite. Dacă pe a
doua linie a fişierului apar toate numerele din intervalul precizat, se va afişa mesajul NU
LIPSESTE NICIUN NUMAR. Alegeţi un algoritm de rezolvare eficient din punctul de
vedere al timpului de executare.
Exemplu: pentru fişierul numere.in cu următorul conţinut
12
4 2 3 1 6 5 7 8 9 11 10 100
se vor afişa valorile 12 13 … 99.
a) Explicaţi în limbaj natural metoda utilizată, justificând eficienţa acesteia (4-6 rânduri).
(4p.)
b) Scrieţi programul C/C++ ce rezolvă problema enunţată, corespunzător metodei
descrise la punctul a). (6p.)

#include<fstream>
#include<iostream>
using namespace std;
int main()
{int n,m=0,mm=0,v[100]={0},i;
ifstream f("bac.txt");
clock_t x,y;
x=clock();
f>>n;
while(f>>n)
{v[n]++;
if(v[n]>m)
    m=v[n];
}
for(i=1;i<=100;i++)
    if(v[i]==0)
        cout<<i<<" ";
f.close();
y=clock();
cout<<endl<<"Timp de executie "<<(double)(y-x)/CLOCKS_PER_SEC<<" secunde";
}

4. Fişierul text bac.in conţine pe prima sa linie un număr natural n (0<n<10000), iar pe
următoarea linie n numere naturale din intervalul [1,100]. Se cere să se citescă din fişier
toate numerele şi să se afişeze pe ecran, în ordine descrescătoare, toate numerele care
apar pe a doua linie a fişierului şi numărul de apariţii ale fiecăruia. Dacă un număr apare de
mai multe ori, el va fi afişat o singură dată. Fiecare pereche „valoare - număr de apariţii” va
fi afişată pe câte o linie a ecranului, numerele fiind separate printr-un spaţiu, ca în exemplu.
Alegeţi un algoritm de rezolvare eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fişierul bac.in are următorul conţinut:
12
1 2 2 3 2 2 3 3 2 3 2 1
pe ecran se vor afişa, în această ordine, perechile:
3 4
2 6
1 2
a) Explicaţi în limbaj natural metoda utilizată justificând eficienţa acesteia (4-6 rânduri) (4p.)
b) Scrieţi programul C/C++ ce rezolvă problema enunţată, corespunzător metodei
descrise la punctul a). (6p.)

#include<fstream>
#include<iostream>
using namespace std;
int main()
{int n,m=0,mm=0,v[100]={0},i;
ifstream f("bac.txt");
clock_t x,y;
x=clock();
f>>n;
while(f>>n)
{v[n]++;
if(v[n]>m)
    m=v[n];
if(n>mm)
    mm=n;}
for(i=mm;i>=1;i--)
    cout<<i<<" "<<v[i]<<endl;
f.close();
y=clock();
cout<<endl<<"Timp de executie "<<(double)(y-x)/CLOCKS_PER_SEC<<" secunde";
} 

Problema BAC s1, s2

#include<fstream>
#include<iostream>
using namespace std;
int main()
{int s1,s2,a,b,c1,c2,c3,c4,c5,nr=0;
clock_t x,y;
x=clock();
cin>>s1>>s2;
a=s1;b=s2;
if(s1>9)a=9;
if(s2>9)b=9;
for(c1=1;c1<=a;c1++)
{c2=s1-c1;
for(c3=0;c3<=9;c3++)
    for(c4=0;c4<=b;c4++)
    {c5=s2-c4;
    if(c5<10 && c2<10)
    {cout<<c1*10000+c2*1000+c3*100+c4*10+c5<<endl;
    nr++;}
    }
}
y=clock();
cout<<endl<<"Timp de executie "<<(double)(y-x)/CLOCKS_PER_SEC<<" secunde";
cout<<endl<<nr;
}