Titlul: Secventa
Scris de: Jurj Andrei din Martie 07, 2014, 15:19:23
Problema suna in felul urmator: ,,Determinati o secventa de lungime k care are suma elementelor maxima dintr-un sir de n numere naturale".Daca exista 2 secvente de acest gen se va determina cea mai din stanga(prima).N,K si sirul se citesc din fisier.Numerele din fisier vor fi numere naturale,1<=k<=n<=100000. Eu am rezolvat problema in O(N^2): #include<iostream> #include<fstream> using namespace std; ifstream f("secvk.in"); ofstream g("secvk.out"); int v[100005]; int main() {int n,k,i,st,dr,s,sfinal=0,j; f >> n >> k ; for(i=1;i<=n;++i) f >>v[i]; for(i=1;i+k-1<=n;++i) {j=i;s=0; while(j<=i+k-1) {s=s+v[j]; ++j; } if(s>sfinal) {sfinal=s;st=i;dr=j-1;}
} for(i=st;i<=dr;++i) g<<v[i]<<" ";
f.close(); g.close(); }
Intrebarea mea este cum ar fi gandirea pentru o rezolvare mai rapida ?.
Titlul: Răspuns: Secventa
Scris de: Adrian Craciun din Martie 07, 2014, 15:28:52
Daca ai calculat suma secventei i -> i + k, atunci suma secventei i + 1 -> i + k + 1 e suma secventei anterioare + v[i + k + 1] - v [ i ] . Bafta.
Titlul: Răspuns: Secventa
Scris de: Jurj Andrei din Martie 07, 2014, 16:26:56
Mersi de idee.Am rescris problema si intra in timp dar e interesant ca imi pica un test care inainte nu-mi pica.O sa caut sa vad in ce caz pica. #include<iostream> #include<fstream> using namespace std; ifstream f("secvk.in"); ofstream g("secvk.out"); int v[100005],s[100005]; int main() {int n,k,i,st=0,dr=0,s1=0,sfinal=0,s2=0,j=1,var=0; f >> n >> k ; for(i=1;i<=n;++i) f >>v[i]; i=1; sfinal=v[1],st=i,dr=i+k-1; for(i=1;i<=k;++i) s[j]=s[j]+v[i]; if(s[j]>sfinal) sfinal=s[j],st=i,dr=i+k-1,var=1;
++j; for(i=2;i+k-1<=n;++i) {s[j]=s[j-1]+v[i+k-1]-v[i-1];
if(s[j]>sfinal) sfinal=s[j],st=i,dr=i+k-1,var=1; ++j; } if(var) for(i=st;i<=dr;++i) g <<v[i]<<" "; else for(i=st;i<=dr;++i) g <<v[i]<<" ";
f.close(); g.close(); }
EDIT:Pica cand k==n... #include<iostream> #include<fstream> using namespace std; ifstream f("secvk.in"); ofstream g("secvk.out"); int v[100005],s[100005]; int main() {int n,k,i,st=0,dr=0,s1=0,sfinal=0,s2=0,j=1,var=0; f >> n >> k ; for(i=1;i<=n;++i) f >>v[i];
for(i=1;i<=k;++i) s[j]=s[j]+v[i]; if(s[j]>sfinal) sfinal=s[j],st=1,dr=k,var=1;
++j; for(i=2;i+k-1<=n;++i) {s[j]=s[j-1]+v[i+k-1]-v[i-1];
if(s[j]>sfinal) sfinal=s[j],st=i,dr=i+k-1,var=1; ++j; }
for(i=st;i<=dr;++i) g <<v[i]<<" ";
f.close(); g.close(); }
|