Strona główna » Algorytmy » Artykuły » Wielomiany cz. 3
 

Wielomiany cz. 3

https://mattomatti.com/a34c
· część 1 · część 2 · część 3 · Algorytm Hornera ·

Wstęp

Na podstawie poprzednich części przygotowałem biblioteke wielomiany.h z której będę korzystać w dalszej implementacji.

Twierdzenie (o mnożeniu wielomianów)

Iloczyn wielomianów stopnia m i n jest stopnia m+n.

Implementacja

Mnożenia wielomianów

Definiujemy funkcję mnozWielomiany(), która przyjmie dwa argumenty: wielomian a i wielomian b. Jako wynik zwrócimy wskaźnik na nowy wielomian, który będzie iloczynem a i b.

  1. wielomian* mnozWielomiany(wielomian* a, wielomian* b){
  2.   wielomian* w = new wielomian;
  3.   w->stopien = a->stopien + b->stopien;

(2.) Alokujemy pamięć na nowy wielomian. (3.) Korzystamy z twierdzenia o iloczynie wielomianów i ustalamy stopień nowego wielomianu.

  1.   double* wspol = new double[w->stopien + 1];
  2.   for(int i = 0; i < w->stopien + 1; i++)
  3.     wspol[i] = 0;

(4.) Deklarujemy nową listę liczb rzeczywistych, która będzie przechowywać współczynniki nowego wielomianu. (5. - 6.) Wszystkie wartości na liście zerujemy.

  1.   for(int i = 0; i < a->stopien + 1; i++)
  2.     for(int j = 0; j < b->stopien + 1; j++)
  3.       wspol[w->stopien - i - j] += zwrocWyrazStn(a,i) * zwrocWyrazStn(b,j);

Mnożenie wielomianu przez wielomian to pomnożenie każdego składnika z każdym. Zwykle trzeba potem uprościć wielomian dokonując redukcji. Cały proces będziemy rozpatrywać na samych współczynnikach, ponieważ w uproszczonej formie i-ty współczynnik to suma współczynników wszystkich składników (tj. jednomianów) tego samego stopnia.

(7.) Dla każdego elementu z jednomianu a i (8.) każdego elementu z jednomianu b zwiększamy odpowiedni stopień wielomianu wynikowego o iloczyn jednomianów na pozycji i w a i j w b. Przy ustalaniu, który współczynnik wyniku zwiększyć korzystamy z twierdzenia.

  1.   w->wspolczynniki = wspol;
  2.   return w;
  3. }

(10.) Nową listę przypisujemy do wielomianu. (11.) Zwracamy wielomian.

Mnożenie przez xn

Definiujemy funkcję mnozWielomianxn_w_miejscu(), która będzie podnosiła stopień wielomianu mnożąc go przez xn. Jako argument przyjmuje wielomian w, stopień n zmiennej x. Funkcja nie zwraca nic: modyfikuje wielomian w miejscu.

  1. void mnozWielomianxn_w_miejscu(wielomian* w, int n){
  2.   double* wspol = new double[w->stopien + n + 1];
  3.   for(int i = 0; i < w->stopien + 1; i++)
  4.     wspol[i] = w->wspolczynniki[i];
  5.   for(int i = 0; i < n; i++)
  6.     wspol[w->stopien + i + 1] = 0;
  8.   delete[] w->wspolczynniki;
  10.   w->stopien += n;
  11.   w->wspolczynniki = wspol;
  12. }

(2.) Tworzymy nową listę współczynników. (3. - 4.) Przepisujemy dotychczasową listę na nową począwszy od indeksu 0. (5. - 6.) Pozostałe współczynniki zerujemy. (7.) Usuwamy dotychczasową tablicę współczynników. (8.) Zwiększamy stopień wielomianu. (9.) Przypisujemy nową listę do danego wielomianu.

Testowanie programu

Poniższa funkcja main() wczyta od użytkownika dwa wielomiany, wypisze je, a następnie wypisze na ekran wynik ich pomnożenia. Wynik zostanie później pomnożony przez xn.

  1.         cout << "+";
  2.       }
  3.       if(w->wspolczynniki[i] < 0){
  4.         cout << "-";
  5.       }
  6.       if(abs(w->wspolczynniki[i]) != 1 || i==w->stopien){
  7.         cout << abs(w->wspolczynniki[i]);
  8.       }
  9.       if(i < w->stopien){
  10.         cout << "x";
  11.         if(i < w->stopien - 1){
  12.           cout << "^" << (w->stopien-i);
  13.         }

Przykładowo dla:

  1. 1
  2. 2 -3
  3. 2
  4. 1 -2 2

program powinien wypisać na ekran:

  1. 2x-3
  2. x^2-2x+2
  3. 2x^3-7x^2+10x-6
  4. 2x^5-7x^4+10x^3-6x^2

Zadania

Zadanie 1

Napisz funkcję mnozWielomianxn(), która będzie podobna do mnozWielomianxn_w_miejscu() z tą różnicą, że nie będzie modyfikować podanego wielomianu. Powinien zostać utworzony nowy wielomian, który będzie przechowywał wynik operacji, a funkcja powinna zwrócić wskaźnik na niego.