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

Wielomiany cz. 2

· część 1 · część 2 · część 3 · Algorytm Hornera ·

Wstęp

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

Implementacja

Pobieranie jednomianu

Definiujemy funkcję zwrocWyrazStn(), która pozwoli nam pobrać współczynnik jednomianu stopnia n z wielomianu w. Jako argumenty przyjmuje wskaźnika na wielomian w, liczbę całkowitą n, która określa jakiego stopnia jednomian chcemy wydobyć oraz liczbę rzeczywistą defValue, która jest zwracana jako wynik jeśli jednomian danego stopnia nie istnieje. Domyślnie defValue powinien zostać ustawiony na 0.

  1. double zwrocWyrazStn(wielomian* a, int n, double defValue = 0){
  2.   if(n <= a->stopien){
  3.     return a->wspolczynniki[a->stopien-n];
  4.   } else {
  5.     return defValue;
  6.   }
  7. }

(1.) Definiujemy funkcję: zwracamy liczbę rzeczywistą czyli współczynnik jednomianu. Argumenty to wskaźnik na wielomian a, liczba całkowita n i liczba rzeczywista defValue, która jeśli nie została podana to przyjmuje wartość 0. (2.) Sprawdzamy czy wielomian ma jednomian takiego stopnia. Jeśli tak to (3.) zwracamy wartość jednomianu, ale jeśli nie to (5.) zwracamy wartość domyślną (czyli defValue).

Dodawanie wielomianów

Skorzystamy tu z własności, że jeśli mamy wielomiany a i b i ich stopnie to odpowiedni n i m to stopień sumy tych wielomianów jest mniejszy lub równy n+m.

Funkcja dodajWielomiany() ma przyjmować dwa wielomiany i stworzyć nowy wielomian, który będzie sumą dwóch podanych.

  1. wielomian* dodajWielomiany(wielomian* a, wielomian* b){
  2.   wielomian* w = new wielomian;
  3.   w->stopien = (a->stopien > b->stopien) ? a->stopien : b->stopien;
  4.   while(w->stopien > 0 && (zwrocWyrazStn(a, w->stopien) + zwrocWyrazStn(b, w->stopien)==0))
  5.     w->stopien--;

Nasz nowy wielomian będzie maksymalnie stopnia wielomianu o największym stopniu, dlatego (3.) sprawdzamy, który wielomian ma większy stopień i ustalamy go jako stopień nowego wielomianu. Suma wielomianu jednak może być mniejsza. W celu zoptymalizowania wykorzystania pamięci musimy sprawdzić jaki będzie prawdziwy stopień nowego wielomianu. Osiągamy to (4.) sprawdzając czy suma współczynników przy jednomianach stopnia wielomianu w nie jest równy 0. Jeśli jest to (5.) zmniejszamy stopień nowego wielomianu. Powtarzamy to, aż stopień wielomianu będzie 0 lub któraś suma jednomianów któregoś stopnia nie jest równa 0.

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

(6.) Deklarujemy nową listę współczynników wielomianu w. (7. - 8.) Na liście umieszczamy sumę współczynników jednomianów i-tego stopnia.

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

(10.) Wskaźnik na nową listę przekazujemy zmiennej w i (11.) ją zwracamy.

Odejmowanie wielomianów

Odejmowanie wielomianów jest analogiczne do dodawania, dlatego kod też będzie podobny. Należy jednak pamiętać, że podczas odejmowania może się zmniejszyć stopień wielomianu. Różnica tkwi w operacji wykonywanej w linijce (4.) i (8.).

  1. wielomian* odejmijWielomiany(wielomian* a, wielomian* b){
  2.   wielomian* w = new wielomian;
  3.   w->stopien = (a->stopien > b->stopien) ? a->stopien : b->stopien;
  4.   while(w->stopien > 0 && (zwrocWyrazStn(a, w->stopien) - zwrocWyrazStn(b, w->stopien)==0))
  5.     w->stopien--;
  6.   double* lista = new double [w->stopien + 1];
  7.   for(int i = 0; i <= w->stopien; i++)
  8.     lista[w->stopien - i] = zwrocWyrazStn(a,i) - zwrocWyrazStn(b,i);
  9.   w->wspolczynniki = lista;
  10.   return w;
  11. }

Testowanie programu

Poniższa funkcja main() wczyta od użytkownika dwa wielomiany, wypisze je, a następnie wypisze na ekran sumę jak i różnicę wprowadzonych wyrażeń.

  1. int main () {
  2.   wielomian* w1 = wczytajWieloman();
  3.   wypiszWieloman(w1);
  4.   wielomian* w2 = wczytajWieloman();
  5.   wypiszWieloman(w2);
  6.   wielomian* w1p2 = dodajWielomiany(w1, w2);
  7.   wypiszWieloman(w1p2);
  8.   wielomian* w1m2 = odejmijWielomiany(w1, w2);
  9.   wypiszWieloman(w1m2);
  10.   usunWielomian(w1);
  11.   usunWielomian(w2);
  12.   usunWielomian(w1p2);
  13.   usunWielomian(w1m2);
  14.   system("pause");
  15.   return 0;
  16. }

Przykładowo dla:

  1. 3
  2. 3 2 1 0
  3. 2
  4. 2 1 0

program powinien wypisać na ekran:

  1. 3x^3+2x^2+x
  2. 2x^2+x
  3. 3x^3+4x^2+2x
  4. 3x^3

Zadania

Zadanie 1

Napisz funkcję mnozWielomianLiczba(), która pomnoży wszystkie współczynniki wielomianu przez określoną liczbę a. Funkcja powinna przyjmować dwa argumenty: wskaźnik na wielomian oraz liczbę rzeczywistą a i nic nie zwracać - operacje wykonujemy na podanym wielomianie.

Zadanie 2

Napisz funkcję podzielWielomianLiczba(), która podzieli wszystkie współczynniki wielomianu przez określoną liczbę b. Funkcja powinna przyjmować dwa argumenty: wskaźnik na wielomian oraz liczbę rzeczywistą b i nic nie zwracać - operacje wykonujemy na podanym wielomianie. Wykorzystaj do tego funkcję mnozWielomianLiczba().

Zadanie 3

Napisz funkcję sumaWspolczynnikow(), która zwróci sumę współczynników wielomianu. Jako argument przyjmuje wskaźnik na wielomian i zwraca sumę jako liczbę rzeczywistą.