Subsir

Rezolvarea problemelor de matematica prin realizarea unor programe.
Alex Stoica
utilizator
utilizator
Mesaje: 31
Membru din: 04 Mar 2018, 17:23

Subsir

Mesaj de Alex Stoica » 30 Mai 2018, 16:29

Cine m-ar putea ajuta la acest exercitiu ?


PhantomR
guru
guru
Mesaje: 2855
Membru din: 27 Apr 2011, 18:16

Re: Subsir

Mesaj de PhantomR » 02 Iun 2018, 01:08

Explicatia algoritmului (am fost nevoit sa scriu intre tag-uri code pentru ca

Cod: Selectaţi tot

[i] (notatia pentru indice) este exact tag-ul pentru text Italic.. 
:(.

Cod: Selectaţi tot

O solutie ar fi urmatoarea. Vom parcurge numerele o singura data si, de fiecare data, la numarul curent (a[i]), 
vom vedea daca suntem deja intr-o secventa care incepe cu el (caz in care indicele de start al acestei secvente e pastrat 
in sequenceStart[a[i]] si trebuie sa fie >=0). Daca suntem, vom seta pozitia curenta ca POTENTIAL final pentru secventa 
de lungime maxima ce incepe cu a[i]. Daca mai tarziu o sa gasim alt element egal cu acest [tex]a[i][/tex], acela va 
deveni un nou final potential. Daca nu suntem intr-o secventa, vom seta pozitia curenta, i, ca startul  secventei i
ncepand cu a[i].
 
 Dupa aceasta parcurgere, vom avea stocati indicii pentru inceputurile si sfarsiturile tuturor secventelor de lungime
 maxima care incep cu fiecare din numerele [tex]0-9[/tex]. Daca pentru un anumit numar nu exista o secventa corecta 
 (aceasta se intampla in cazul in care numarul nu apare deloc in secventa sau apare o singura data), valoarea 
 sequenceEnd pentru acel numar va ramane -1, indicand seceventa invalida.
 
 Ne-am bazat pe faptul ca pentru un numar exista cel mult o secventa de lungime maxima care incepe cu el. Intr-adevar, 
daca ar fi doua, ele s-ar putea concatena obtinand una mai mare, contradictie. Deci, ne ajung vectori de 10 elemente 
pentru a stoca inceputurile, sfarsiturile si, la final, lungimile acestor secvente.
De asemenea, prima aparitie a unui numar x in sirul citit din fisier este neaparat inceputul secventei de lungime maxima
care incepe cu x (daca ea chiar exista, deci daca mai exista inca o aparitie ulterioara a lui x in sirul citit).
 
Algoritmul in sine (cod de C/C++).. anumiti pasi (marcati) i-am lasat ca tema.

Cod: Selectaţi tot

int a[1000000]; // 10^6 = 1000000 elemente maxim
int n; // numarul de elemente din sirul citit
int sequenceStart[10], sequenceEnd[10], sequenceLength[10];
int length[10];

// TEMA: citire din fisier a numerelor in vectorul a si numarul lor in n 

for(int i = 0 ; i < 10; i++)
{
	sequenceStart[i] = -1; // -1 indica faptul ca nu am gasit inca inceputul pentru secventa care incepe cu i
	sequenceEnd[i] = -1;  //  -1 indica tot faptul ca nu am gasit inca un potential final pentru secventa
}

for(int i = 0 ; i < n ; i++)
{
	if(sequenceStart[a[i]] < 0)
		sequenceStart[a[i]] = i;
	else
		sequenceEnd[a[i]] = i;
}

for(int i = 0 ; i < 10; i++)
{
	if(sequenceEnd[i] < 0)
		length[i] = 0; // secventa invalida
        else
        	length[i] = sequenceEnd[i] - sequenceStart[i] + 1;
}

// TEMA: gasirea elementului maxim (max) din vectorul length[i]

// TEMA: afisare max pe prima linie din fisier

for(int i = 0 ; i < 10; i++)
{
	if(length[i] == max)
		// TEMA: afisare i urmat de spatiu pe a doua linie din fisier..
}

PhantomR
guru
guru
Mesaje: 2855
Membru din: 27 Apr 2011, 18:16

Re: Subsir

Mesaj de PhantomR » 02 Iun 2018, 14:32

Am uitat sa comentez eficienta... Avem 2 bucle ce parcurg intreg sirul (cea de citire si cea in care parcurgem sirul pentru a determina sequenceStart si sequenceEnd) si alte cateva bucle de lungime 10 (fixa). In bucle se intampla doar operatii de baza, operatii care putem zice ca ruleaza in timp constant. Deci, algoritmul este liniar in numarul de elemente ale secventei citite din fisier. Nu se poate obtine eficienta mai buna decat una liniara pentru ca trebuie parcurs tot sirul cel putin o data pentru a putea fi siguri ca am gasit secventa de lungime maxima (in cel mai rau caz, secventa incepe cu primul element din sir si se gata cu ultimul - e chiar intreg sirul).

Scrie răspuns