Răspuns :
#include <iostream>
#include <fstream>
using namespace std;
int main()
{ int n1,n2,r,rmax,m,maxim,ok=0,x;
ifstream f("date.in");
f>>n1>>n2; r=n2-n1; maxim=2;rmax=r;
while (f>>x)
{ n1=n2; n2=x; m=2;
while (n2-n1==r) { m++; n1=n2; f>>n2;}
if (m>=3) ok=1;
if (maxim<m){rmax=r; maxim=m;}
if (maxim==m && rmax<r) rmax=r;
r=n2-n1;
}
if (ok) cout<<rmax;
else cout<<"Nu exista ";
}
Descrierea solutiei:
Variabile necesare:
- x - elementul curent citit din fisier
- n1 si n2- doua numere aflate pe pozitii consecutive
- maxim - o variabila in care retin lungimea secventei de nr in progresie aritmetica de lungime maxima
m- lungimea unei secvente de nr aflate in progresie aritmetica
- r= ratia secventei m
- rmax= ratia maxima a secventelor gasite.
- ok- o variabila in care retin 1 daca am gasit in sir minim o secventa de termeni in progresie aritmetica sau 0 in caz contrar.
Modalitate de rezolvare:
Pornesc de la presupunerea ca in sirul aflat in fisier nu am nicio secv de minim 3 termeni in progresie aritmetica (ok=0);
Pentru inceput, citesc din fisier doua numere si le memorez in n1 si n2. Ratia secventei din care ar face parte aceste numere este r=n2-n1;
Initializez lungimea secventei maxime cu 2; (pana in prezent am 2 numere);
Cat timp mai sunt numere in fisier, citesc cate un numar si repet urmatorii pasi:
- Actualizez n1 ca find ultimul numar cunoscut inainte de citire (n1=n2) si n2 cu nr proaspat citit.
- Lungimea secventei actuale este 2 (m=2);
- Citesc cate un numar din fisier, actualizand mereu variabilele n1 si n2 cum am precizat mai sus si maresc cu 1 lungimea secventei actuale, cat timp diferenta dintre cele doua numere este egala cu ratia secventei actuale, r.
-Daca am gasit o secventa de lungime mai mare sau egala cu 3, ok devine 1.
- Daca lungimea secventei actuale este mai mare decat lungimea maxima a secventelor gasite pana in prezent, actualizez ratia maxima (rmax =r) si actualizez si lungimea secventei maxime gasite (maxim=m;)
- Daca gasesc doua secvente de lungimi egale, pastrez in rmax ratia mai mare
- Actualizez ratia r=n2-n1;
In final, la terminarea numerelor din fisier, daca ok este 1 afisez ratia maxima (rmax)
altfel afisez mesajul "nu exista".
Complexitatea algoritmului este O(n) unde n= nr de elemente din sir.
Algoritmul proiectat este eficient deoarece compararile si deciziile sunt luate pe masura ce citesc cate un element din fisier.
Sunt folosite doar 8 variabile; nu folosesc tablouri de date, nu folosesc parcurgeri repetate ale sirului de valori.
Vă mulțumim pentru vizita pe site-ul nostru dedicat Informatică. Sperăm că informațiile furnizate v-au fost utile. Dacă aveți întrebări suplimentare sau aveți nevoie de ajutor, nu ezitați să ne contactați. Vă așteptăm cu drag și data viitoare! Nu uitați să adăugați site-ul nostru la favorite!