Cho hai số ở định dạng chuỗi. Chúng ta cần nhân chúng lên. Ý tưởng để giải quyết vấn đề là duy trì một câu trả lời nhân chữ số trước đó và mang. Chúng ta có thể sử dụng câu trả lời phép nhân các chữ số trước và mang theo để nhận được phép nhân các chữ số tiếp theo.
Hãy xem một ví dụ.
Đầu vào
15 2
Đầu ra
30
Thuật toán
-
Khởi tạo các số trong chuỗi.
-
Khởi tạo một chuỗi có độ dài number_one_length + number_two_length.
-
Lặp lại số đầu tiên từ cuối.
-
Lặp lại số thứ hai từ cuối.
-
Nhân hai chữ số và thêm chữ số hàng trước tương ứng.
-
Cập nhật chữ số hàng trước.
-
Lưu trữ giá trị mang trong chỉ mục trước của chuỗi kết quả.
-
-
-
Chuyển đổi biểu đồ thành chữ số bằng cách thêm 0 ký tự cho mọi ký tự trong kết quả.
-
Trả về kết quả bằng cách bỏ qua số 0 ở đầu.
Thực hiện
Sau đây là cách thực hiện thuật toán trên trong 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;
} Đầu ra
Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.
1938