━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
データ構造・アルゴリズム論 確認問題１
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

●問 (アルゴリズムの表現と時間量)

(1) ホーナーの方法は，1変数の整数多項式 an x^n + … + a1 x + a0 の値を

        (( … ((0・x ＋ an)・x ＋ a{n-1}) … )・x＋ a1)・x ＋ a0

    の順で計算する．このアルゴリズムをC言語の関数として表したい．
    次のプログラムの空欄 (a) と (b) を埋めよ．

        int eval(int n, int a[], int x) {
            int val = 0, i;
            for (       (a)        ) {
                val =     (b)     ;
            }
            return val;
        }

(2) 問題 (1) の関数が，多項式の値を求めるために実行する演算(加算と乗算)の
    総回数を，n を使った式で表せ．

(3) 問題 (1) の関数を，C言語の再帰関数を使って書き直せ．

──────────────────────────────────────

●答 (アルゴリズムの表現と時間量)

(1) (a) i = n; i >= 0; i-- (b) val*x + a[i]．
(2) 2n+2 回
(3) eval() を再帰関数として次のように再定義する．

        int eval(int n, int a[], int x, int val) {
            if (n < 0) return val;
            else       return eval(n-1, a, x, val*x + a[n]);
        }

eval(n, a, x) の代わりに eval(n, a, x, 0) を呼べばよい．

[解説]

(1) ホーナーの方法では，添え字 i を n から 0 まで変化させながら，
0 を初期値として「x を掛けて ai を足す」という計算を繰り返せばよい．
C言語の関数で表したアルゴリズムを以下に示す．

        int eval(int n, int a[], int x) {
            int val = 0, i;
            for (i = n; i >= 0; i--) {
                val = val*x + a[i];
            }
            return val;
        }

なお，val を a[n] で初期化して，for 文の反復回数を1回減らしてもよい．
ただし，n が負の場合に a[n] をアクセスしないよう配慮が必要．
また，i を 0 から始めて 1 ずつ増やすなら，配列要素 a[n-i] を参照する．

(2) 上記の関数 eval() では，繰り返しごとに，乗算1回と加算1回の計2回実行する．
繰り返し回数は n+1 なので，演算の総回数はその積 2(n+1) ＝ 2n+2 回．

(3) 第4引き数で累計値を受け渡すことに注意．

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
授業のホームページ

山田 俊行
https://www.cs.info.mie-u.ac.jp/~toshi/