C++で2つの多項式を乗算する方法：アルゴリズムと実装例を解説

多項式の各項の係数は、配列として与えられることが一般的です。本記事では、配列形式で表された2つの多項式を乗算する方法を、具体的な例とともに解説します。

入力

A = [1, 2, 3, 4]
B = [4, 3, 2, 1]

出力

4x6 + 11x5 + 20x4 + 30x3 + 20x2 + 11x1 + 4

この例では、配列 A は多項式 1 + 2x + 3x² + 4x³ を、配列 B は多項式 4 + 3x + 2x² + x³ を表しています。これらを掛け合わせると、次数6の多項式が得られます。

アルゴリズム

• 2つの多項式（係数配列）を初期化します。

• 積の多項式を格納するため、長さ (m + n − 1) の新しい配列を作成します。ここで m と n はそれぞれの多項式の項数です。

• 2つの多項式を反復処理します。

  • 最初の多項式から1つの項を取り出し、2番目の多項式のすべての項と掛け合わせます。

  • 計算結果を、インデックス (i + j) に対応する位置の積の多項式に加算していきます。

この手法の計算量は O(m × n) であり、単純な二重ループで実装できるため理解しやすいのが特徴です。

実装

以下は、上記のアルゴリズムをC++で実装したコードです。

#include <bits/stdc++.h>
using namespace std;
int *multiplyTwoPolynomials(int A[], int B[], int m, int n) {
    int *productPolynomial = new int[m + n - 1];
    for (int i = 0; i < m + n - 1; i++) {
        productPolynomial[i] = 0;
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            productPolynomial[i + j] += A[i] * B[j];
        }
    }
    return productPolynomial;
}
void printPolynomial(int polynomial[], int n) {
    for (int i = n - 1; i >= 0; i--) {
        cout << polynomial[i];
        if (i != 0) {
            cout << "x^" << i;
            cout << " + ";
        }
    }
    cout << endl;
}
int main() {
    int A[] = {1, 2, 3, 4};
    int B[] = {4, 3, 2, 1};
    int m = 4;
    int n = 4;
    cout << "First polynomial: ";
    printPolynomial(A, m);
    cout << "Second polynomial: ";
    printPolynomial(B, n);
    int *productPolynomial = multiplyTwoPolynomials(A, B, m, n);
    cout << "Product polynomial: ";
    printPolynomial(productPolynomial, m + n - 1);
    return 0;
}

コードのポイント

• multiplyTwoPolynomials 関数では、まず結果を格納する配列をすべて0で初期化しています。

• 外側のループ変数 i は最初の多項式の項、内側の j は2番目の多項式の項に対応し、積 A[i] * B[j] は x^(i+j) の係数に加算されます。

• printPolynomial 関数は、最高次の項から順に降べきの順で多項式を出力します。

出力

上記のコードを実行すると、次のような結果が得られます。

First polynomial: 4x^3 + 3x^2 + 2x^1 + 1
Second polynomial: 1x^3 + 2x^2 + 3x^1 + 4
Product polynomial: 4x^6 + 11x^5 + 20x^4 + 30x^3 + 20x^2 + 11x^1 + 4

このように、係数同士の積を適切な次数の位置に足し合わせていくことで、2つの多項式の積を簡単に求めることができます。より大規模な多項式の乗算が必要な場合は、FFT（高速フーリエ変換）を利用することで O(n log n) への高速化も可能です。