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

Wielomiany cz. 1

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

Definicja

Wielomiany to funkcja stopnia n jednej zmiennej rzeczywistej x. Jest dana wzorem:

W podanym wzorze , a

Implementacja

Struktura

Podczas pisania programu utworzymy strukturę. Będzie to nowy typ danych, który pozwoli w łatwy sposób operować na wielomianach. Struktura będzie się nazywać wielomian i będziemy w niej przechowywać stopień wielomianu oraz kolejne jego współczynniki.

  1. struct wielomian{
  2.   int stopien;
  3.   double* wspolczynniki;
  4. };

Zakładamy, że na indeksie 0 znajduje się współczynnik stopnia stopien, a na indeksie stopien wyraz wolny (czyli ).

Tworzenie wielomianu

Funkcja nowyWielomian(), która tworzy wielomian ma za zadanie zwrócić wskaźnik na nowo utworzony wielomian. Jako argumenty przyjmuje stopień wielomianu oraz listę liczb rzeczywistych.

  1. wielomian* nowyWielomian(int n, double* a){
  2.   wielomian* w = new wielomian;
  3.   w->stopien = n;
  4.   w->wspolczynniki = a;
  5.   return w;
  6. }

(2.) Alokujemy nową pamięć dla zmiennej w. (3.) Do zmiennej w przypisujemy stopień wielomianu oraz (4.) przekazujemy wskaźnik na listę liczb rzeczywistych - współczynników wielomianu. (5.) Na sam koniec zwracamy wskaźnik do wielomianu.

Wczytywanie wielomianu

Zakładamy, że funkcja wczytajWieloman() nie przyjmuje żadnego argumentu, a jedynie zwraca wskaźnik na strukturę. Użytkownik będzie wprowadzał kolejno: stopień wielomianu, a potem kolejne współczynniki od do .

  1. wielomian* wczytajWieloman(){
  2.   int n;
  3.   cin >> n;
  4.   double* wspol = new double[n + 1];
  5.   for(int i = 0; i < n + 1; i++)
  6.     cin >> wspol[i];
  7.   wielomian* w = nowyWielomian(n, wspol);
  8.   return w;
  9. }

(2.) Deklarujemy zmienną n do której (3.) wczytujemy jakiego stopnia użytkownik chce wprowadzić wielomian. Kolejnym etapem jest (4.) utworzenie dynamicznej listy, która będzie przechowywać wprowadzone przez użytkownika liczby. (5. - 6.) wczytujemy kolejne liczby na listę. (8.) Tworzymy nowy wielomian na podstawie zebranych informacji. (9.) Zwracamy wskaźnik na wielomian.

Uwaga: Tablica musi być rozmiaru n+1, ponieważ mamy n+1 współczynników.

Wypisywanie wielomianu

Funkcja wypiszWieloman() będzie najbardziej skomplikowana, dlatego warto pisać ją częściami. Zakładamy, że funkcja otrzymuje wskaźnik na strukturę wielomianu i nic nie zwraca. Jej działanie polega na wypisaniu na ekran dobrze sformatowanego wielomianu.

  1. void wypiszWieloman(wielomian* w){
  2.   for(int i = 0; i <= w->stopien; i++){

(1.) Deklarujemy funkcje. (2.) Naszą pętle wykonamy dla wszystkich współczynników prócz - ten przypadek rozpatrzymy osobno na koniec.

  1.     if(w->wspolczynniki[i] != 0){

(3.) Pierwsza instrukcja if gwarantuje nam, że nie zostanie wypisany żaden jednomian, którego współczynnikiem jest 0.

  1.       if (w->wspolczynniki[i] > 0 && i!=0){
  2.         cout << "+";
  3.       }

W związku z próbą ładnego sformatowania nie będziemy polegać na formatowaniu domyślnym strumienia cout. (4.) Jeśli współczynnik jest dodatni to (5.) wypiszemy +, ale nie może to też być pierwszy współczynnik, ponieważ + mógłby wystąpić na początku wielomianu co byłoby błędem.

  1.       if(w->wspolczynniki[i] < 0){
  2.         cout << "-";
  3.       }

(8.) W przypadku wypisania minusa robimy to zawsze kiedy (7.) liczba jest ujemna.

  1.       if(abs(w->wspolczynniki[i]) != 1 || i==w->stopien){
  2.         cout << abs(w->wspolczynniki[i]);
  3.       }

Jeśli współczynnik wynosi 1 to go nie chcemy wypisać. Tak samo w przypadku -1. Możemy sprawdzić (10.) czy wartość bezwzględna nie wynosi 1 i wtedy nie wypisać współczynnika, ponieważ wypisanie minusa mamy zapewnione wcześniej. Dla innych liczb (11.) Wypisujemy bezwzględną wartość współczynnika. Należy pamiętać, że ostatnie wykonanie dotyczy wyrazu wolnego, który musi być wypisany nawet jeśli jest jedynką.

  1.       if(i < w->stopien){
  2.         cout << "x";
  3.         if(i < w->stopien - 1){
  4.           cout << "^" << (w->stopien-i);
  5.         }
  6.       }
  7.     }
  8.   }
  9. }

(13.) Dopóki nie jesteśmy w ostatniej iteracji - czyli przy wyrazie wolnym to zawsze (14.) dopisujemy x. Jednak już (15.) potęgę podajemy, gdy wypisywany jednomian ma stopień > 1. (16.) Ustaliliśmy, że na indeksie 0 jednomian ma stopień n, więc na i-tym jednomian ma stopień n-i.

Testowanie programu

Poniższa funkcja main() wczyta od użytkownika stopień wielomianu n, a następnie kolejne jego współczynniki. Następnie program wypisze na ekran odpowiednio sformatowany wielomian.

  1. int main () {
  2.   wielomian* w = wczytajWieloman();
  3.   wypiszWieloman(w);
  4.   system("pause");
  5.   return 0;
  6. }

Przykładowo dla:

  1. 4
  2. -1 5 0 -4 -10

program powinien wypisać na ekran:

  1. -x^4+5x^3-4x-10

Zadania

Zadanie 1

Napisz funkcję usunWielomian(), która prawidłowo zdealokuje zadeklarowaną pamięć. Jako argument przyjmuje tylko wskaźnik wielomianu.