คูณตัวเลขขนาดใหญ่ที่แทนด้วยสตริงใน C++

โจทย์

ได้รับตัวเลขสองตัวในรูปแบบสตริง เราต้องคูณพวกมันกัน แนวคิดในการแก้ปัญหาคือการเก็บคำตอบการคูณหลักก่อนหน้าและตัวลอย (carry) เราสามารถใช้คำตอบการคูณหลักก่อนหน้าและตัวลอยเพื่อหาการคูณชุดหลักถัดไป

มาดูตัวอย่างกัน

อินพุต

15 2

เอาต์พุต

30

อัลกอริธึม

• กำหนดตัวเลขในรูปสตริง
• กำหนดสตริงความยาว ความยาวตัวเลขตัวแรก + ความยาวตัวเลขตัวที่สอง
• วนลูปผ่านตัวเลขตัวแรกจากท้ายสุด
  • วนลูปผ่านตัวเลขตัวที่สองจากท้ายสุด
    • คูณสองหลักและบวกกับหลักที่ตรงกันในแถวก่อนหน้า
    • อัปเดตหลักในแถวก่อนหน้า
    • เก็บตัวลอยในดัชนีก่อนหน้าของสตริงผลลัพธ์
• แปลงตัวอักษรเป็นตัวเลขโดยการบวกตัวอักษร 0 เข้าไปในทุกตัวอักษรในผลลัพธ์
• คืนค่าผลลัพธ์โดยข้ามศูนย์นำหน้า

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

ต่อไปนี้เป็นการนำไปใช้งานของอัลกอริธึมข้างต้นใน C++

#include <bits/stdc++.h> 
using namespace std; 

string multiplyTwoNumbers(string num1, string num2) { 
    if (num1 == "0" || num2 == "0") { 
        return "0"; 
    } 
    string product(num1.size() + num2.size(), 0); 
    for (int i = num1.size() - 1; i >= 0; i--) { 
        for (int j = num2.size() - 1; j >= 0; j--) { 
            int n = (num1[i] - '0') * (num2[j] - '0') + product[i + j + 1]; 
            product[i + j + 1] = n % 10; 
            product[i + j] += n / 10; 
        } 
    } 
    for (int i = 0; i < product.size(); i++) { 
        product[i] += '0'; 
    } 
    if (product[0] == '0') { 
        return product.substr(1); 
    } 
    return product; 
} 

int main() { 
    string num1 = "34"; 
    string num2 = "57"; 
    if((num1.at(0) == '-' || num2.at(0) == '-') && (num1.at(0) != '-' || num2.at(0) != '-')) { 
        cout << "-"; 
    } 
    if(num1.at(0) == '-') { 
        num1 = num1.substr(1); 
    } 
    if(num2.at(0) == '-') { 
        num2 = num2.substr(1); 
    } 
    cout << multiplyTwoNumbers(num1, num2) << endl; 
    return 0; 
}

ผลลัพธ์

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

1938