C++ でホーナーの法則を使用して多項式の値を求める

  2. プログラミングのヒント
  3. C++ ハウツー
  4. C++ でホーナーの法則を使用して多項式の値を求める
Jay Shaw 2023年10月12日
C++ C++ Math
  1. ループを後方に反復することにより、C++ でホーナーの規則を使用して多項式の値を見つける
  2. C++ でホーナーの法則を使用してループ フォワードを反復して多項式の値を求める
  3. 再帰を使用して、C++ でホーナーの規則を使用して多項式の値を見つける
  4. まとめ
C++ でホーナーの法則を使用して多項式の値を求める

ホーナーの規則は、多項式の値を計算するための効率的なアルゴリズムです。

x = 4 における多項式 p(x) = 6x^3 - 2x^2 + 7x + 5 を考えてみましょう。 C++ でホーナーの法則を使用して計算するには、最初の係数 6 に x の値 4 を掛け、2つの積 24 を次の係数 -2 に加算します。

結果は 4 倍され、次の係数に加算されます。

このプロセスは、式の係数の数だけ繰り返されます。 残った最終積は多項式の値です。

この記事では、上記のルールをコンピューター コードに変換することにより、C++ でホーナーのルールを使用して多項式の値を見つける方法について説明します。

多項式を考えてみましょう:

$$ p(x) = 6(x^3) - 2(x^2) + 7x + 5 $$

x = 4 の場合、多項式の値は 385 です。

ループを後方に反復することにより、C++ でホーナーの規則を使用して多項式の値を見つける

逆方向ループによって C++ でホーナーの規則を使用して多項式の値を見つけるプログラムを見てみましょう。

  1. コードの最初の行は、ライブラリ パッケージ iostream をインポートします。 2 行目では、ネームスペースは std として定義されています。

  2. メソッド int Horner() が 3つのパラメーターで作成されます。係数のリストを渡すポインター配列 a、多項式の次数を格納する整数変数 n、および別の整数変数 x です。 多項式の値を x に格納します。

    int Horner(int* a, int n, int x)

  3. これは、多項式の積を相互に加算する方法を説明しています。 整数変数 result が作成され、配列 a[n] の最後の要素で初期化されます。

    int result = a[n];

    注: 配列のサイズと間違えないでください。 n 番目の位置にある配列 a の要素で変数 result を初期化します。

  4. for ループが作成され、配列 a の最後の要素から 0 番目のインデックスまでループが反転します。 result 変数の値は、ループの反復ごとに更新されます。

    for (int i = n - 1; i >= 0; --i)

    最初の反復では、a[n] の値が x で乗算され、配列の前の要素である a[n-1] に追加されます。 配列 - {2,3,4} の場合、ループは最後の要素 a[n] (4) を取り、それを x で乗算し、n-1 要素に加算します。 配列の 3 です。

    このため、main 関数で初期化する際に係数を逆にする必要があります。 result の値は、メソッドの最後に返されます。

  5. main 関数内で配列が作成され、それをメソッド Horner の最初のパラメーターに渡します。 ループが逆方向に繰り返されるため、配列内の係数の値が逆になることに注意してください。

  6. Horner という名前のメソッドから返された結果を格納するために整数変数 sol が作成されます。

    最初のパラメーターには、作成中の配列が渡されます。 2 番目のパラメーターは方程式の多項式の次数 3 を渡し、3 番目のパラメーター値は x で渡されます。

    int sol = Horner(arr, 3, 4);

コード：

#include <iostream>
using namespace std;
int Horner(int* a, int n, int x) {
  int result = a[n];
  for (int i = n - 1; i >= 0; --i) result = result * x + a[i];
  return result;
}

int main() {
  int arr[4] = {5, 7, -2, 6};
  int sol = Horner(arr, 3, 4);
  cout << sol;
}

出力 (C++ での後方ループ ホーナーの規則):

385

C++ でホーナーの法則を使用してループ フォワードを反復して多項式の値を求める

ループを順方向に実行する必要がある場合は、最後の例とは異なり、配列の ポインターを逆参照 して最初の要素を取得し、ループを逆方向に実行する代わりに順方向に実行できます。 これは、C++ でホーナーの規則を実装するためにループを使用する別の方法です。

コードの機能を理解しましょう。

  1. コードの最初の行は、ライブラリ パッケージ iostream をインポートします。

  2. 前の例と同様に、メソッド Horner が 3つのパラメーターで作成されます。

    int Horner(int a[], int n, int x)

  3. 変数 result が作成され、ポインターを逆参照することによって配列の最初の要素で初期化されます。 ポインタ *a は arr[0] を書くのと同じです。

    int result = *a;

    前の例では、メソッド Horner はその配列にアタッチされたサイズ コンポーネントを必要としていました: int result = a[n]; 最後の要素を指す。 ここでは、逆参照されているだけです。

  4. 1 から n まで反復する for ループが作成されます。 各反復で、result 変数の値は多項式の値で更新されます。

    result の値は、メソッドの最後に返されます。

    for (int i = 1; i < n; i++) result = result * x + a[i];
return result;

  5. main 関数内で、係数の値で配列が作成されます。 ここで使用される多項式は次のとおりです。

    $$
    p(x) = 5x^4 + 3x^3 - 2x^2 + 4x - 6; x=-2
    $$

    配列は、多項式の係数を取ることによって作成されます - int arr[] = {5,3,-2,4,-6};.

  6. 変数 n は多項式の次数を保持します。 n の値は、n = 配列のサイズ -1 によって計算されます。

    int n = (*(&arr + 1) - arr) - 1;
//  n =	  size of the array		    -   1;

  7. メソッド Horner は、配列、n の値、および x の値を渡すことによって呼び出されます。 返された結果は新しい整数変数に格納され、出力されます。

    int sol = Horner(arr, n, -2);
std::cout << "Value of polynomial = " << sol;

コード：

#include <iostream>
int Horner(int a[], int n, int x) {
  int result = *a;
  for (int i = 1; i < n; i++) result = result * x + a[i];
  return result;
}

int main() {
  int arr[] = {5, 3, -2, 4, -6};
  int n = (*(&arr + 1) - arr) - 1;
  int sol = Horner(arr, n, -2);
  std::cout << "Value of polynomial = " << sol;
}

出力 (C++ でのホーナーの規則の順方向ループ):

Value of polynomial = -20

再帰を使用して、C++ でホーナーの規則を使用して多項式の値を見つける

これまでのところ、C++ でホーナーの規則を使用して多項式の値を見つける方法を学びました。 これは、ループを繰り返し、アキュムレータ変数を使用してカウントを更新することによって行われました。

この例では、多項式の値は再帰によって計算されます。 コードを見てみましょう。

  1. コードの最初の行は、パッケージ iostream をインポートし、名前空間を std として定義します。

    #include <iostream>
using namespace std;

  2. 3つのパラメータを持つメソッド Horner が作成されます - ポインター整数 *pi、多項式の次数である別の整数変数 degree (前の例では n として使用)、および x で値を渡すための x。

    int Horner(int* pi, int degree, int x)

  3. 再帰関数の特徴は、条件が満たされるまでループのように自分自身を呼び出し続けることで、時間の複雑さを軽減します。 条件の場合、次数の値が 0 に減少した場合にのみ、if ステートメントは 0 番目のインデックスで pi の値を返します。

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

  4. 再帰を適用するために、値を返す代わりに Horner メソッドが再度呼び出されます。

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

    上記の構文は、存在する多項式の次数に対して Horner メソッドを繰り返し呼び出し続けます。 方程式では、多項式の次数はその最高指数です。

    最後の例で使用された式を考慮すると、次のようになります。

    $$ p(x) = 5x^4 + 3x^3 - 2x^2 + 4x - 6; x=-2 $$

    多項式の次数は 4 です。

    これは、再帰が n+1 = 5 回 (配列のサイズ) 繰り返されることを意味します。 各反復で、メソッドは次数の値が 0 に減少するまで自分自身を呼び出します。

    0 に達すると、再帰は *p[0] 要素を取り、それを前のメソッド呼び出しに渡します。

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

    これは、最後の封筒に到達するまで封筒を封筒の内側で開き、再び折りたたむのと同じです。 最後のメソッド呼び出しの値が前のメソッド呼び出しに渡され、計算が実行されます。

  5. main 関数内で、方程式の係数をメソッド Horner に渡すために整数配列が作成されます。 次に、パラメーターの値がメソッドに渡されます。

    int sol = Horner(arr, 4, -2);

    配列は arr、次数 - 4 で、x の値は -2 です。

  6. 最後に、返された結果が整数変数 sol に格納され、出力されます。

コード：

#include <iostream>
using namespace std;

int Horner(int* pi, int degree, int x) {
  if (degree == 0) {
    return pi[0];
  }
  return Horner(pi, degree - 1, x) * x + pi[degree];
}
int main() {
  int arr[] = {5, 3, -2, 4, -6};
  int sol = Horner(arr, 4, -2);
  cout << "Value of Polynomial using recursion = " << sol;
}

出力：

Value of Polynomial using recursion = 34

まとめ

この記事では、C++ でホーナーの規則を使用して多項式の値を見つける方法について説明します。 3つの方法は時間の複雑さが異なり、読者にとって優れた学習ツールとなります。

自分でコードを書いてみて、ヒントを得るために戻ってくることをお勧めします。 読者は、C++ でホーナーの規則を使用して多項式の値を求める概念を簡単に理解できます。

関連記事 - C++ Math