SOUČET POLYNOMŮ

PROBLÉM
Naším cílem je provádět výpočty jako

(2 + 3*X + 6*X**2) + (2 - X**2) = (4 + 3*X + 5*X**2)

Jsou-li polynomy reprezentovány poli, pak následující podprogram pro součet polynomů je přímočarým řešením:

IMPLEMENTACE
Jednotka: vnitřní podprogram
 
Globální proměnné: pole A. s N+1 koeficienty, pole B. s N+1 koeficienty.
 
Parametr: přirozené číslo N - stupeň polynomů A. a B.
 
Výsledek: Pole A. obsahuje koeficienty výsledného součtu polynomů.

 

POLYADD: procedure expose A. B.
parse arg N
do J = 0 to N; A.J = A.J + B.J; end
return

 

PŘÍKLAD
(12*X**54 + 65*X**80 + 3*X*10000) +
(3*X**12 - 13*X**54 + 13*X**98 + 7*X**10000) =
3*X**12 - X**54 + 65*X*80 + 13*X*98 + 10*X**10000

N = 10000
A. = 0; A.54 = 12; A.80 = 65; A.10000 = 3
B. = 0; B.12 = 3; B.54 = -13
B.98 = 13; B.10000 = 7
call POLYADD N
do I = 1 to N
  if A.I <> 0 then say I A.I
end
exit
POLYADD: procedure expose A. B.
...

zobrazí

12 3
54 -1
80 65
98 13
10000 10

 

"ŘÍDKÉ" POLYNOMY
Při práci s "řídkými" polynomy, tj. s polynomy, které mají mnoho nulových koeficientů, můžeme pracovat jen s nenulovými koeficienty. Řídký polynom

A.N*X**N+...+A.J*X**J+...+A.1*X+A.0

pak bude reprezentován polem dvojic J A.J jen pro nenulové koeficienty A.J

IMPLEMENTACE
Jednotka: nerekurzívní vnitřní podprogram
 
Globální proměnné: Globální proměnné: vzestupně uspořádané pole A. obsahující M dvojic koeficient mocnina, vzestupně uspořádané pole B. obsahující N dvojic koeficient mocnina, výstupní vzestupně uspořádané pole C. dvojic, jako součet polynomů A. a B.
 
Parametry: přirozená čísla M, N - počet dvojic pole A. resp. pole B.
 
Výsledek: Vrací počet dvojic výsledného pole C., které obsahuje dvojice reprezentující součet polynomů.

 

SPARSE_POLYADD: procedure expose A. B. C.
parse arg M, N
K = 1; L = 1; J = 0
do while K <= M & L <= N
  parse var A.K Apower Acoef
  parse var B.L Bpower Bcoef
  select
    when Apower < Bpower
      then do; J = J + 1; C.J = A.K; K = K + 1; end
    when Apower > Bpower
      then do; J = J + 1; C.J = B.L; L = L + 1; end
    otherwise
      Sum = Acoef + Bcoef
      if Sum <> 0
        then do; J = J + 1; C.J = Apower Sum; end
      K = K + 1; L = L + 1
  end
end
do while K <= M; J = J + 1; C.J = A.K; K = K + 1; end
do while L <= N; J = J + 1; C.J = B.L; L = L + 1; end
return J

 

PŘÍKLAD
Následující program

M = 3
A.1 = 54 12; A.2 = 80 65; A.3 = 10000 3
N = 4
B.1 = 12 3; B.2 = 54 "-13"; B.3 = 98 13
B.4 = 10000 7
J = SPARSE_POLYADD(M, N)
do I = 1 to J; say C.I; end
exit
SPARSE_POLYADD: procedure expose A. B. C.
...

vypíše na obrazovku

12 3
54 -1
80 65
98 13
10000 10

 

SOUVISLOSTI


Obálka Obsah Index Hlavní stránka

změněno 30. července 2001
Copyright © 2000-2001 Vladimír Zábrodský, RNDr.