c++ - 再帰を使用したホーナーのルールC/C ++

Question

ここで初めてホーナーのルールについて学び ました。C++でのホーナーのルール 再帰ATMについて学習しているので、再帰を使用してこのアルゴリズムを実装できるかどうか疑問に思いました。

int HornerR( int a[], int n, int x, int index )
{
    if (index==n) return a[n];
    else  
        return x*HornerR(a,n ,x,index+1) + a[index];
} 

私はそれが4番目のパラメータでのみ可能だと思います。

Answer 1

あなたはポインタ演算でそれを行うことができます：

1. 配列の最後のベースケース（nをチェック）は定数パラメーターを返します
2. 変数の乗算された再帰呼び出しに追加された再帰ケース戻り値の現在のセル
3. 再帰呼び出しは、配列を次のセルに移動し、カウンターを更新します（n）

基本的に、これにより、配列全体を毎回送信する代わりに、配列を次の位置に移動して送信する（そして常に最初のセルを使用する）ことでインデックス変数を計算できます。

Answer 2

配列piに、インデックス0から次数+1までの最高次数から0までの係数が含まれている場合、関数内に3つの引数を使用して、次のように関数を実装できます。Ex for 3x ^ 2 + 2x ^ 1 + 1 => pi [3] = {3,2,1}

int compute_by_horner(int *pi, int degree, int x)
{
int i, j;

if (degree == 0)
{
    return pi[0];
}

return compute_by_horner(pi, degree-1, x) * x + pi[degree];

}

Answer 3

インデックスを渡すのではなくa、ポインタとして考えてください（そうなので）。それに伴い、をデクリメントしてn、がゼロになったかどうかを追跡するのではなく、まだゼロになっているかどうかを追跡する必要がありindex==nます。