Długie dzielenie wielomianów

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Długie dzielenie wielomianów jest techniką podziału jednego wielomianu przez drugi o tym samym lub niższym stopniu. Dzielimy wielomian A przez wielomian B (różny od zera) w rezultacie otrzymując iloraz Q oraz resztę R.

A = BQ + R,

Reszta może być równa zero lub być wielomianem stopnia niższego niż stopień B. Dzielimy w ten sposób że (modyfikując wielomian A lub działając na jego kopii R) dzielimy kolejne wyrazy przez najstarszy wyraz B a następnie odejmujemy od wielomianu B pomnożony przez ten wyraz

Przykład[edytuj | edytuj kod]

Znaleźć iloraz oraz resztę dzielenia przez

Dzielna jest na początek przepisana jako:

iloraz oraz reszta mogą być określone następująco:

Dzielimy pierwszy człon dzielnej przez najwyższy człon dzielnika. Wpisujemy rezultat nad kreskę (x3 ÷ x = x2).

Mnożymy dzielnik przez właśnie otrzymany rezultat (pierwszy człon ilorazu). Wpisujemy rezultat poniżej pierwszych dwu członów dzielnej

Odejmujemy otrzymany iloraz od odpowiednich członów oryginalnej dzielnej (należy pamiętać, że odejmowanie czegoś mającego znak minus odpowiada dodaniu czegoś ze znakiem plus), i zapisujemy rezultat pod spodem. Następnie "sprowadzamy" następny człon dzielnej.

Powtarzamy poprzednie trzy kroki, tylko tym razem używamy dwóch członów, które zostały zapisane jako dzielna.

Powtarzamy 4. Tym razem nie ma nic sprowadzenia.


Wielomian powyżej kreski jest ilorazem q(x), a liczba, która pozostała, czyli 5, jest resztą r(x).

Algorytm długiego dzielenia w arytmetyce jest bardzo podobny do poniższego algorytmu, tylko zmienna x jest zastąpiona przez podstawę, np. liczbę 10 dla systemu dziesiętnego.

Kod[edytuj | edytuj kod]

void divPoly(double *Q, double *R, const double *A, const double *B, int &degQ, int &degR, const int degA, const int degB)
{
	const double Eps = 1e-14;
	for (int i = 0; i <= degA; i++)
		R[i] = A[i];
	degQ = degA - degB;
	degR = degB - 1;
	for (int j = 0; j <= degQ; j++)
	{
		Q[degQ - j]  = R[degA - j] / B[degB];
		for (int i = degA - j; i >= degQ - j; i--) 
			R[i] -= Q[degQ - j] * B[i - degQ + j];
	}
	for (int i = degR - 1; i>=0; i--)  
		if (fabs(R[i])<Eps) R[i] = 0;	
}