Buna!
Imi explica cineva cum e ideea cu un vector de frecventa in care poti gasi cifrele, daca ridici la puterea a doua indicele unui element.
Va atasez explicatiile pe care nu le am inteles :)) precum si codul, ambele gasite aici pe brainly. Multumeesc!
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.
#include
#include
#include
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:"<
}
return 0;
}
cel mult 1000000 de numere naturale de forma 10p (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
crescător obținut din toate numerele distincte aflate pe a doua linie a fișierului.
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ă fişierul bac.txt conţine numerele
4
100 100000 1 100000 1000 100 10 100
atunci pe ecran se afișează valoarea
1000
Răspunsuri la întrebare
Răspuns:
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("bac.txt");
ofstream g("bac.out");
int n, distincte, fr[10], num, nrzero, i, z, exista;
int main()
{
f >> n;
while (f >> num)
{
nrzero=0;
while (num>1)
{
++nrzero;
num=num/10;
}
if (fr[nrzero]==0) { fr[nrzero]=1; ++distincte; };
}
if (distincte>=n)
{
exista=1;
i=0; num=0;
while (num<n)
{
if (fr[i]==1)
{
++num;
z=i;
}
++i;
}
}
if (exista)
{
num=1;
for (i=1; i<=z; ++i) num=num*10;
g << num;
}
else g << "Nu exista";
}
Explicație:
da, problema dată diferă de puteri6, deoarece aici se caută distincte.
Am folosit un singur vector caracteristic, fr[10]. Citind linia a doua a fişierului aflu pentru fiecare numar citit nr de zerouri ale lui. Dacă e 100, el are două zerouri şi atunci pun fr[2]=1. Dacă cândva mai întîlnesc pe 100, nu mai schimb valoarea lui fr[2], deoarece ne trebuiesc numerele distincte. Când în fr pun următorul 1, măresc distincte, şi astfel numărăm câte distincte vom avea. Variabila num, am folosit-o în diferite roluri: mai întîi citeam în ea numerele din fişier, apoi am folosit-o ca contor să ajung la al n-ulea distinct, şi în fine am folosit-o pentru numărul rezultant la care trebuia de adăugat z zerouri. z a semnalizat indicele elementului din vector care este al n-lea distinct. ... Mai meditează, ... :))))