คูณพหุนามสองตัวใน C++

โจทย์

สัมประสิทธิ์ของแต่ละพจน์ของพหุนามถูกกำหนดในอาร์เรย์ เราต้องคูณพหุนามสองตัว มาดูตัวอย่างกัน

อินพุต

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

เอาต์พุต

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

อัลกอริธึม

• กำหนดพหุนามสองตัว
• สร้างอาร์เรย์ใหม่ที่มีความยาวเท่าผลรวมของความยาวทั้งสองพหุนาม
• วนลูปผ่านพหุนามทั้งสอง
  • เลือกพจน์หนึ่งจากพหุนามแรกและคูณกับทุกพจน์ในพหุนามที่สอง
  • เก็บผลลัพธ์ในพหุนามผลคูณ

การนำไปใช้งาน

ต่อไปนี้เป็นการนำไปใช้งานของอัลกอริธึมข้างต้นใน 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; 
}

ผลลัพธ์

หากคุณรันโค้ดข้างต้น คุณจะได้ผลลัพธ์ดังนี้

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