Page 38 - MATINF Nr. 8

38 5 IMPLEMENTARE S , I REZULTATE

4 Rezolvarea ecuatiilor de forma f(x) + g(y) = 0 ˆın multimea numerelor
,
,
ˆıntregi

ˆ n m dou˘a
In continuare vom considera f = a 0 + a 1 X + . . . + a n X s , i g = b 0 + b 1 X + . . . + b m X
polinoame de gradul n, respectiv m, unde n, m ≥ 1 cu coeficient , i ˆıntregi. Dorim s˘a scriem un
algoritm eficient de determinare a solut , iilor ˆıntregi pentru ecuat , ia:

f(x) + g(y) = 0, x s , i y numere ˆıntregi din [u, v]. (2)

u s , i v sunt numere ˆıntregi date, u ≤ v.
n
m
a
a
(2) este echivalent˘ cu a 0 + a 1 x + . . . + a n x + b 0 + b 1 y + . . . + b m y = 0, adic˘
n
(a 0 + g(y)) + a 1 x + . . . + a n x = 0. (3)
Pentru rezolvarea ecuat , iei (3) vom parcurge toate valorile lui y : u, u + 1, . . . , v s , i pentru fiecare
folosim Algoritmul 2 cu termenul liber a 0 + g(y).
Algoritmul 3. Date de intrare: n, a 0 , a 1 , . . . , a n , m, b 0 , b 1 , . . . , b m , u, v

Date de ies , ire: x, y (solut , iile ecuat , iei 3)

Pasul 1. citim n, a 0 , a 1 , . . . , a n , m, b 0 , b 1 , . . . , b m , u, v

Pasul 2. pentru y = u, v execut˘
a
Pasul 3. Folosim algoritmul 2 cu termenul liber a 0 + g(y) s , i la fiecare solut , ie afis , ˘am x, y

sfˆars , it pentru
a
Observat ,ia 4. Algoritmul 3 calculeaz˘ valoarea f(x) folosind (n + 1)(2 + a 0 + g(y)) comparat , ii
de v − u ori, y cu valorile u, u + 1, . . . , v. Astfel num˘arul de comparat , ii este (n + 1)(2 + a 0 )(v −
u) + (g(u) + g(u + 1) + . . . + g(v))(n + 1).

5 Implementare si rezultate
,

Pentru implementarea Algoritmilor 2 s , i 3 am folosit limbajul C++. Programele sunt prezentate
ˆın continuare.
5.1 Implementarea algoritmului 2

# include <iostream >
# include <math.h>
using namespace std;

int n, a[100];
void read_data (){
int i;
cin >>n;
for(i=0;i<=n;i++)
cin >>a[i];
}
unsigned long long f(int n, int a[],int x){