多項式の計算：ホーナー法

例題4.1多項式

多項式

y = 14.4375 x⁶ - 19.6875 x⁴ - 6.5625 x² - 0.3125

に対してｘの値を6個読み込んで、各値に対するyの値を計算せよ。

ホーナー法

多項式

a₀xⁿ + a₁x^n-1 + ...+ a_n-1x + a_n

の値を計算するのに、

(...((a₀x + a₁)x+a₂)x +...+ a_n-1)x + a_n

を計算する方法のことをホーナー法と呼ぶ。

前者の計算には、

xⁱ (i=2,..,n)の計算で掛け算は、(n-1)回

a_ix^n-i(i=0,..,n-1)の計算で掛け算は、計n回

各項の足し算がn回

合計で掛け算が2n-1回、足し算がn回は必要になるが、ホーナー法では、掛け算がn回と足し算がn回ですむ。

program polynomial(input,output);
const imax = 6;
var x,t,y:real; i:integer;
begin
   for i:=1 to imax do
   begin read(x); t:=sqr(x);
      y:=((14.4375*t-19.6875)*t+6.5625)*t-0.3125;
      writeln('x=',x,'y=',y)
   end
end.      

(実行例）

sino% pc polynomial
sino% polynomial
0 0.2 0.4 0.6 0.8 1
 x =  0.0000000000000E+0000 y = -3.1250000000000E-0001
 x =  2.0000000000000E-0001 y = -8.0576000000001E-0002
 x =  4.0000000000000E-0001 y =  2.9263600000000E-0001
 x =  6.0000000000000E-0001 y =  1.7209599999999E-0001
 x =  8.0000000000000E-0001 y = -3.9179600000001E-0001
 x =  1.0000000000000E+0000 y =  1.0000000000000E+0000
sino%           

文法：演算子の優先順位

x+y*zという式を例に考えてみます。数学では通常、「xにyとzの積をたしたもの」と解釈します。さらに、明確に記述するときにはx+(y*z)と書くこともあると思います。これを(x+y)*zと考えてしまう人はいないと思います。Pascalも数学とほとんど同じなのですが、数学のときよりも明確に規則を与えます。

そこで設けられた概念が「演算子の優先順位」というものです。これは、「演算子の結合力」のようなもので、小括弧を省略したときに演算子がどちらにまとまるかということをあらわしています。

たとえば、

    a + b * c

の場合は、bという変数を+と*が競合（とりあっている）わけですが、上の表によると優先順位は、*のほうが強力なので、b*cの部分がくっついて、

    a+(b*c)

ということになります。

同様に、a-b/cはa-(b/c)であるわけです。結合力に差がある場合は、このようにしてどういうふうに解釈するかは定まります。一方、二つの演算子が隣り合ったときにはどうなるのでしょうか？

二つの同じ優先順位の演算子が隣り合う場合には、右の方が強力であるということになってます。すなわち、

    a+b+c

の場合は、右の+方が強力であるとみなします。従って、

    a+(b+c)

なのです。a+b-cはa+(b-c)ですし、a-b-cはa-(b-c)です。

問題：

次の式に小括弧を挟みなさい。

    a <= b or c <= d

    a = b = c = d = e

    a+b+c+d / e

while文

while文は、for文同様、何らかの作業を反復して実行するような命令です。for文は初期値と最終値が決まると反復の回数も決まります。したがって、for文を実行する途中でどうあがいても、反復の回数は変更できません。それに対して、while文とrepeat文は、そのような制限はなく、繰り返しの途中で反復回数が決まるような計算手順を表現することができます。

while文は次のような文です。

while <論理型の式> do <文>

この文の意味は次の通りです。

1. <論理型の式>を計算します。

2. その計算結果がtrueならば、<文>を実行して、1の段階に再び戻ります。そうでなければ、すなわち、falseのときはこのwhile文は終了します。

ユークリッドの互除法

正の整数pとqとの最大公約数を求めるための計算法でユークリッドの互除法というものがありました。

r には pをqで割ったときの余りを書き込みます。

rが0、すなわち、pがqで割り切れたときは、qがpとqとの最大公約数になります。

そうでないときは、pとqとの最大公約数はqとrの最大公約数に等しくなります。

これをプログラムで書くと次のようになります。

program gcd(input,output);
var p,q,r : integer;
begin
   read(p,q);
   r:=p mod q;
   while r <> 0 do 
   begin p := q;
      q := r;
      r := p mod q
   end;
   writeln(q)
end.

このプログラムの結果が正しいということは、while文の本体の文を実行してもpとqのGCDは不変であることからわかります。あと、プログラムが停止することは、rが真に減少していくことからわかります。