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

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

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

ป้อนข้อมูล

15
2

ผลผลิต

30

อัลกอริทึม

• เริ่มต้นตัวเลขในสตริง

• เริ่มต้นสตริงที่มีความยาว number_one_length + number_two_length

• วนซ้ำตัวเลขแรกจากจุดสิ้นสุด

  • วนซ้ำตัวเลขที่สองจากจุดสิ้นสุด

    • คูณสองหลักและเพิ่มตัวเลขแถวก่อนหน้าที่เกี่ยวข้อง

    • อัพเดทเลขแถวก่อนหน้า

    • จัดเก็บการพกพาในดัชนีก่อนหน้าของสตริงผลลัพธ์

• แปลงอักขระเป็นตัวเลขโดยเพิ่ม 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