2 raspunsuri

1. 

   PhantomR expert (VI)

   2018-06-01T22:08:22+03:00A raspuns pe 1 iunie 2018 la 10:08 PM

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

    (notatia pentru indice) este exact tag-ul pentru text Italic.. 

   🙁.

   O solutie ar fi urmatoarea. Vom parcurge numerele o singura data si, de fiecare data, la numarul curent (a),
   	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] si trebuie sa fie >=0). Daca suntem, vom seta pozitia curenta ca POTENTIAL final pentru secventa
   	de lungime maxima ce incepe cu a. Daca mai tarziu o sa gasim alt element egal cu acest , 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.
   	
   	 Dupa aceasta parcurgere, vom avea stocati indicii pentru inceputurile si sfarsiturile tuturor secventelor de lungime
   	 maxima care incep cu fiecare din numerele . 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.
   

   <i>
   	</i>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 = -1; // -1 indica faptul ca nu am gasit inca inceputul pentru secventa care incepe cu i
   		sequenceEnd = -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] < 0)
   			sequenceStart[a] = i;
   		else
   			sequenceEnd[a] = i;
   	}
   	
   	for(int i = 0 ; i < 10; i++)
   	{
   		if(sequenceEnd < 0)
   			length = 0; // secventa invalida
   	        else
   	        	length = sequenceEnd - sequenceStart + 1;
   	}
   	
   	// TEMA: gasirea elementului maxim (max) din vectorul length
   	
   	// TEMA: afisare max pe prima linie din fisier
   	
   	for(int i = 0 ; i < 10; i++)
   	{
   		if(length == max)
   			// TEMA: afisare i urmat de spatiu pe a doua linie din fisier..
   	}
   	

   • • 0
   • Raspunde
2. 

   PhantomR expert (VI)

   2018-06-02T11:32:04+03:00A raspuns pe 2 iunie 2018 la 11:32 AM

   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).

   • • 0
   • Raspunde