ALG)9

13.1. Kodowanie danych i arytmetyka dużych liczb 299

(

int w[n]-{1,4,-2,O,7(; // współczynniki wielomianu cout << oblicz_wielomianl(2,w,n) << endl; cout << oblicz_wielomian2(2,w,n) << endl/ ł

Przy użyciu reprezentacji tablicowej, nieskomplikowane staje się również dodawanie i mnożenie wielomianów:

wielom.cpp

void dodaj_wiel(int x[],int y[],int z[], int rozm)

(

for(int i=0;i<rozm;i++!

z[i]-x[i]+y[i] ;    // wielomian z-x+y

)

void mnoz_wiel(int x[],int y[],int z[), int rozm)

I

int i,j;

for(i=0; i<2*rozm-l; i++i

z[i]=0;    // zerowanie rezultatu

// wielomian z=x*y for(i=0;i<rozm;i++)

for{i =0;jcrozm;j++!

z[i+j]=z[i+j] + x[i]*y[j);

)

Zacytowane powyżej algorytmy sa bezpośrednim tłumaczeniem praktycznych sposobów znanych nam ze szkoły podstawowej lub średniej. Co jest ich podstawową wadą? Otóż to, co wydawało nam się zaletą: reprezentacja tablicowa (a więc prosty dostęp do współczynników)! Jest ona mało ekonomiczna, jeśli chodzi o zużycie pamięci, o czym najlepiej niech świadczy próba pomnożenia następujących wielomianów:

(2x^IAno + 3x^9on) X (3x⁸⁵ +1).

Owszem, można zarezerwować tablice o rozmiarach 1600, 85 i 1600+85 (na wynik), ale biorąc pod uwagę, że będą się one składały głównie z zer, nie jest to najrozsądniejszym pomysłem...

Na pomoc przychodzi tutaj reprezentacja wielomianu przy pomocy listy jednokierunkowej: wybierzemy najprostsze rozwiązanie, w którym nowe składniki wielomianu są dokładane na początek listy (użytkownik musi jednak pamiętać o wstawianiu nowych składników w określonej kolejności: od potęg najwyższych do najniższych lub odwrotnie). Nie będą zapamiętywane składniki zerowe:

wielom2.cpp

typedef struct W3p

I

int c; int j;