Lungime maxima secventa descrescatoare intr-o lista simplu inlantuita

Salut!Am incercat astazi sa rezolv o problema,doar ca fara foarte mare progres.Enunt:Se da o lista simplu inlantuita(o aloc dinamic).Trebuie sa scriu o functie care imi printeaza indicii de inceput si de sfarsit ale secventei de lungime maxima ,descrescatoare (daca sunt 2 astfel de secvente,o printez pe prima).
   Exemplu:
4,2,3 ,  4   ,6  , 5,   -10,   2 ,  1,   0

   Se printeaza indicii 5 si 7 intrucat prima si cea mai mare secventa descrescatoare este "6 , 5 , -10" ;

Ma gandesc ca trebuie sa parcurg lista.
Daca  Exista L->urm si L-info < L->urm->info


void IndiciSecvMaxDesc(TLista L )  //TLista e o structura ; Celula de lista are campul "info" , un int si campul adresa "urm".
{   int poz=0,inc=1,sf=1,lungime=1;
for( ; L!=NULL ; L=L->urm ) //parcurgere lista
{  poz++;
if(L-urm != NULL)
   if(L->info < L->urm->info) // ordine crescatoare si trebuie reactualizat indice inceput.
/* acum nu stiu cat de departe sa ma duc si cum sa gasesc lungimea maxima a secventei */
}   
}


Multumesc pentru ajutor!

Edited by Cognitivul, 22 March 2019 - 20:34.

Programul trebuie facut doar in C si cum as putea sa ordonez lista ?Daca puteam folosi vectori,era usor.Doar ca nu stiu cum sa ma descurc cu legaturile.Trebuie sa folosesc doar Liste Simplu Inlantuite.

Edited by Cognitivul, 22 March 2019 - 21:03.

 BraviaAmpero, on 22 martie 2019 - 20:52, said:

Nu trebuie sa ordonezi crescator sirul. Problema se rezolva in O(n) cu o singura parcurgere a sirului

Tii inceputul si lungimea celei mai lungi secvente gasite pana acum, respectiv cea curenta, precum si (pointerul la) elementul anterior. Initial sunt ambele zero, unu, si primul element.
Parcurgi lista, incepand cu al doilea element.
Daca e mai mic decat cel de dinainte sau ai ajuns la capatul listei, incrementezi lungimea secventei curente.
Altfel, secventa curenta s-a terminat. Daca e mai lunga decat cea mai lunga de pana acum, copiezi acolo valorile. Resetezi lungimea secventei curente.
Cand ajungi la capatul listei ai raspunsul.
Comparatia include egalitatea, daca secventele nu trebuie sa fie _strict_ descrescatoare.

Problema trebuie rezolvata doar cu Liste Simplu Inlantuite fara alocari statice de memorie.
Ideea e ca stiu sa fac parcurgerea.Pseudocodul,sa zic,nu mi-ar fi clar.

Multumesc,incerc acum.

Edited by Cognitivul, 22 March 2019 - 21:21.

 _bcristian_, on 22 martie 2019 - 21:19, said:

superb pseudocodu !A mers.Multumesc mult!

ia pune aici codul sursa rezulat.Sunt foarte curios ce ai inteles si "ce a mers".

Multumesc pentru ajutor!

void PozIncFinSecvPoz(TLista L)
{
	int incmax, sfmax, l, max = 0;
	int poz = 1, inc = 1, sf = 1;
	TLista p = L;
	if (L != NULL) {
		if (L->urm != NULL)
			L = L->urm;
	}
	for (; L != NULL; L = L->urm) {
		poz++;
		if (p->info > L->info) {
			sf = poz;
			l = sf - inc + 1;
			if (l > max) {
				incmax = inc;
				sfmax = sf;
				max = l;
			}
		}
		if (p->info < L->info) {
			inc = poz;
		}
		p = p->urm;
	}

	printf("\n%d %d\n ", incmax, sfmax);
}

Edited by dani.user, 24 March 2019 - 10:47.
ne place sa citim cod formatat

pune si declaratia tipului TLista

Edited by BraviaAmpero, 23 March 2019 - 23:24.

Congnitivule este o problema: nu se printeaza indecsii 5 si 7 ,conform sirului dat initial:
Avem lista :

valoare_nod=4
valoare_nod=2
valoare_nod=3
valoare_nod=4
valoare_nod=6
valoare_nod=5
valoare_nod=-10
valoare_nod=2
valoare_nod=1
valoare_nod=0

ia uite ce se intampla in solutia data de tine (in bucla for), da click pe poza pt marire:
 cognitivul.PNG   3.97K   4 downloads
Orit tu ai zis ca este absolut perfect, insa indecsii ies ca 6 si 8.
Poti te rog sa clarifici aceste diferente?

2.Esti absolut sigur ca virgula codul sursa de tine la sfarsit sigur se compileaza in C ?

Edited by BraviaAmpero, 24 March 2019 - 00:22.

LE: ti-am atasat si variatia valorilor nodurilor in bucla for:
 cognitivul.PNG   5.48K   5 downloads

Da sunt sigur ! Eu in C l-am compilat.
Cat despre pozitie, primul elelement din lista are pozitia 1.Daca se presupune ca primul element are pozitia 0,atunci int poz=0 ( pe al doilea rand);

ia pune aici tot codul, absolut tot codul.

 BraviaAmpero, on 24 martie 2019 - 11:48, said:

Asa i-am cerut si pe https://forum.softpe...plu-inlantuite/ si a ignorat. Am impresia ca trolleaza.

Cine vrea sa exerseze C++ e invitat sa vina cu o solutie generica la aceasta problema, solutie ce ar functiona cu orice forward iterator si mod de comparare.