Question

Un șir format din cel puțin trei termeni formează o progresie aritmetică de rație r dacă diferența dintre

oricare termen al acestuia și cel aflat pe poziția consecutivă în șir este egală cu r.

Fișierul text bac.txt conține un șir de cel puțin trei și cel mult 106 numere întregi din intervalul

[-10^8,10^8]. Numerele sunt separate prin câte un spațiu. Se cere să se afișeze pe ecran rația unei

secvențe din șir cu număr maxim de termeni, secvență care formează o progresie aritmetică. Dacă

există mai multe astfel de secvențe de lungime maximă se afișează rația cea mai mare, iar dacă nu

există nicio astfel de secvență, se afișează pe ecran mesajul nu exista. Proiectați un algoritm eficient

din punctul de vedere al memoriei utilizate și al timpului de executare.

Exemplu: dacă fișierul conține numerele 4 9 14 19 18 17 8 5 3 1 -1 -3 -5 -7

pe ecran se afișează valoarea -2 (corespunzătoare secvenței 5 3 1 -1 -3 -5 -7).

a. Scrieți programul C/C++ corespunzător algoritmului proiectat. (8p.)

b. Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
p.s nu folositi vectori

Answer 1

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