Написано: 11.03.2023
43. Перемножение строк (Multiply Strings)
Задание.
Получены два неотрицательных целых числа num1 и num2, представленных в виде строк.
Нужно вернуть произведение num1 и num2, также представленное в виде строки.
Примечание: Нельзя использовать какую-либо встроенную библиотеку BigInteger или напрямую преобразовывать входные данные в целое число.
Пример 1.
Входные данные: num1 = “2”, num2 = “3”
Результат: “6”
Пример 2.
Входные данные: num1 = “123”, num2 = “456”
Результат: “56088”
Решение.
string multiply(string a, string b) {
if (a=="0" || b=="0") {
return "0";
}
int m = a.size() - 1, n = b.size() - 1, carry = 0;
string product;
for (int i = 0; i <= m+n || carry; ++i) {
for (int j = max(0, i-n); j <= min(i, m); ++j) {
carry += (a[m-j] - '0') * (b[n-i+j] - '0');
}
product += carry % 10 + '0';
carry /= 10;
}
reverse(begin(product), end(product));
return product;
}
Пояснение.
Используется внешний цикл (0:m+n), для определения цифры в соответствующем разряде произведения.
Предположим, перемножаются числа a = 1234 и b = 5678.
a = 1234 = 1*1000 + 2*100 + 3*10 + 4
b = 5678 = 5*1000 + 6*100 + 7*10 + 8
a * b = 1234 * 5678 = (1*1000 + 2*100 + 3*10 + 4) * (5*1000 + 6*100 + 7*10 + 8)
= 4 * 8
+ (3 * 8 + 4 * 7) * 10
+ (2 * 8 + 3 * 7 + 4 * 6) * 100
+ (1 * 8 + 2 * 7 + 3 * 6 + 4 * 5) * 1000
+ (1 * 7 + 2 * 6 + 3 * 5) * 10000
+ (1 * 6 + 2 * 5) * 100000
+ (1 * 5) * 1000000
| разряд | вычисление | пример | цифра | carry |
|---|---|---|---|---|
| младший | a[3] * b[3] | 4 * 8 = 32 | 2 | 3 |
| десятки | carry + a[2] * b[3] + a[3] * b[2] | 3 + 3 * 8 + 4 * 7 = 3 + 24 + 28 = 55 | 5 | 5 |
| сотни | carry + a[1] * b[3] + a[2] * b[2] + a[3] * b[1] | 5 + 2 * 8 + 3 * 7 + 4 * 6 = 5 + 16 + 21 + 24 = 66 | 6 | 6 |
| тысячи | carry + a[0] * b[3] + a[1] * b[2] + a[2] * b[1] + a[3] * b[0] | 6 + 1 * 8 + 2 * 7 + 3 * 6 + 4 * 5 = 6 + 8 + 14 + 18 + 20 = 66 | 6 | 6 |
| 10000 | carry + a[0] * b[2] + a[1] * b[1] + a[2] * b[0] | 6 + 1 * 7 + 2 * 6 + 3 * 5 = 6 + 7 + 12 + 15 = 40 | 0 | 4 |
| 100000 | carry + a[0] * b[1] + a[1] * b[0] | 4 + 1 * 6 + 2 * 5 = 4 + 6 + 10 = 20 | 0 | 2 |
| 1000000 | carry + a[0] * b[0] | 2 + 1 * 5 = 2 + 5 = 7 | 7 | 0 |
Результат: product = '7' + '0' + '0' + '6' + '6' + '5' + '2'