Eliminarea a doi termeni situati pe pozitii consecutive => numar asociat maxim (SⅢ, 4 – Simulare BAC 2014)

Vreau sa o rezolv in C. Ma gandeam sa fac alte doua array-uri , unul in care se incarca posibilitatea si altul in care se compara posibilitatea urmatoare, iar numerele se masoara dupa slotul din array  if ( v[i] > a[i] ) , in final ramanand cel mai mare numar. Din punct de vedere al timpului si memoriei, ar exista ceva mai eficient de atat ?

Dupa cateva mazgaleli pe hartie ( cum se lucreaza la bac) m-am mai gandit sa compar o cifra de pe pozitia i cu una de pe pozitia i+2, si daca e mai mare atunci un contor max ii ia in calcul pozitia ei, max2 ia pozitia i+1. In cazul in care v[i]==v[i+2]  ,comparam v[i+1] cu v[i+3], asa scap de memorie si am complexitate O(n)

Editat de VladBtz, 12 februarie 2017 - 01:21.

 Untitled.png   38,54K   58 download-uri

Timp: O(n)
Memorie: 3 valori

Sirul ramane modificat in memorie nu ?

Care sir, care memorie ?

 MarianG, on 12 februarie 2017 - 12:51, said:

Sirul obtinut din fisier. Memoria stivei, cred. Rezolvarea mea, care functioneaza:

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
int v[80],nr,pi,max1=0,max2=0;
ifstream f("bac.txt");
for(nr=0; f>>v[nr]; nr++)
{
	 if(nr>=3)
	 {
		 if(v[nr-1]>v[nr-3]&&v[nr-1]>max1)
		 {
				 max1=v[nr-1];
				 max2=v[nr];
				 pi=nr-3;
		 }
		 else if(v[nr-1]==v[nr-3]&&v[nr]>v[nr-2]&&v[nr]>max2)
		 {
			 max1=v[nr-1];
			 max2=v[nr];
			 pi=nr-3;
		 }
	 }
}
for(int i=0;i<nr;i++)
{
	 if(i==pi)
	 {
		for(int j=i; j<nr-2; j++)v[j]=v[j+2];
		nr-=2;
	 }
	 cout<< v[i]<<'\x0';
}

return 0;
}

Editat de VladBtz, 12 februarie 2017 - 13:17.

Codul meu tocmai aici stralueste, ca nu are nevoie sa incarce tot sirul deodata in memorie, doar 3 elemente si atat (fara nici o alta variabila auxiliara).

Daca ai zis ca rezolvi in C, de ce ai fstream prin cod?
De ce faci ceva pe if iar pe else faci acelasi lucru?

Editat de dani.user, 12 februarie 2017 - 15:22.

 dani.user, on 12 februarie 2017 - 15:20, said:

1. din obisnuinta
2. pe if verific daca primul element e mai mare decat ala de doua pozitii in fara, pe else verific cazul in care e egal, dar elementul urmator e mai mare decat ala cu 2 pozitii in fata. in ambele cazuri se intampla acelasi lucru. vrei sa pun toate 4 intr-un singur if ?

poate n-ai inteles intrebarea, sau ce problema evidentia intrebarea

if ( status == condition1 ) { TRUE } esle if ( status == condition2 ) { TRUE } 

si un caz in care nu trebuie sa faci

max1=v[nr-1];
max2=v[nr];
pi=nr-3;

ai ?

Editat de MarianG, 15 februarie 2017 - 00:42.

ok, dar de ce e asa gresit ?
cum as putea sa reformulez instructiunile?

Cerinta problemei ai inteles-o?

Si tine minte ca citesti numarul de la stranga la dreapta

Si nu l-am citit bine ? Din moment ca am rezolvat corect problema eu zic c i-am inteles cerinta . Raspunde-mi te rog la intrebarile de mai sus.

Ce este greșit sau cum reformulezi condițiile?
Repet, faptul că citești numărul de la stânga la dreapta înseamnă că citești de la "cifre importante" către "cifre mai puțin importante", de aceea te poți opri la prima detecție a  condiției (ce mai semnificativă)
Pentru reformularea condițiilor trebuie să intelegi algebra booleana

 VladBtz, on 12 februarie 2017 - 01:07, said:

ti-am pus aici rezolvare.Fii atent cum am format numarul.
https://ideone.com/xLcHd5

Editat de lightpoint, 23 februarie 2017 - 23:05.

Te intreb si pe tine, ce rost isi are acel max ?

 MarianG, on 23 februarie 2017 - 23:11, said:

retine cel mai mare numar asociat .Codul sursa este destul de explicit.

inteleg ca ai un sliding window, de lungime 2, care inlatura numerele tot timpul
dar daca alegi sa inlaturi doar atunci cand prima cifra din fereastra este mai mica decat cifra de dupa fereastra,
atunci este destul o singura inlaturare

https://en.wikipedia...significant_bit

plus ca in problema se mentioneaza un sir de 80 de cifre

Editat de MarianG, 23 februarie 2017 - 23:30.

 MarianG, on 23 februarie 2017 - 23:28, said:

se mentioneaza cel mult 80 de cifre. Cel mult diferit de "exact".Adica avem un interval intre 3 si 80
Dar ia pune si tu solutie ta.Sunt tare curios.

Editat de lightpoint, 23 februarie 2017 - 23:40.

pai a pus-o dani.user