О переводе числа из символьной формы в числовую и обратно обсуждалось здесь.
Умножение положительных многоразрядных чисел ведется начиная с младшего разряда в следующем порядке
- Рассматриваем массивы символов, представляющих числа начиная с конца.
- Организуем вложенный цикл чтобы рассмотреть каждый разряд каждого числа.
- Перемножаем рассматриваемые разряды чисел.
- Выбираем текущий разряд результата как сумму номеров разрядов двух множителей.
- Организуем цикл для разрядов полученного произведения начиная с младшего.
- добавляем к текущему разряду остаток от деления произведения на 10
- если число в текущем разряде результата превышает 9, заменяем его остатком от деления на 10 и увеличиваем на 1 предыдущий разряд
- заменяем произведение частным от деления его на 10
- Переходим к следующей итерации вложенных циклов.
Пусть первый множитель имеет N1 разрядов, а второй множитель - N2 разрядов. Количество разрядов результата выбирается как
N = N1 + N2
Например,
999 * 99 = 98901
3 разряда + 2 разряда = 5 разрядов
Реализация на C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
using namespace std;
char * mult(char *a, char *b)
{
int lena = strlen(a); // количество разрядов первого числа
int lenb = strlen(b); // количество разрядов второго числа
int k = lena + lenb; // количество разрядов результата
char *c = new char[k + 1]; // выделяем память для результата
c[k] = '\0'; // заканчиваем результат концом строки - '\0'
k--; // переходим к младшему разряду результата
int s; // индекс разряда результата начиная с младшего
for (int i = 0; i <= k; i++) // обнуляем все разряды результата
c[i] = 0;
for(int i=0; i<lena; i++) // цикл для всех разрядов первого множителя
for (int j = 0; j < lenb; j++) // цикл для всех разрядов второго множителя
{
int digit = (a[lena - i - 1] - '0') * // получаем цифру разряда первого множителя
(b[lenb - j - 1] - '0'); // получаем цифру разряда второго множителя и перемножаем их
s = i + j; // находим текущий разряд произведения
while (digit > 0) // пока произведение разрядов положительно
{
// к текущему разряду результата добавляем остаток от деления произведения разрядов множителей на 10
c[k - s] += digit % 10;
if (c[k - s] > 9) // если получилась не цифра
{
c[k - s] = c[k - s] % 10; // оставляем в этом разряде остаток от деления на 10
c[k - s - 1]++; // добавляем 1 к предыдущему разряду
}
digit /= 10; // корректируем предыдущую цифру разряда результата
s++; // переходим к предыдущему разряду результата
if (s > k) s = k; // не выходить за границы числа
}
}
int begin = k - s; // определяем первый значащий разряд результата, не равный 0
while (c[begin] == 0 && begin <k) begin++; // пропускаем ведущие нули
for (int i = begin; i <= k; i++) // все значащие разряды результата заменяем соответствующей цифрой
c[i] += '0';
return &c[begin]; // передаем указатель на первый значащий разряд результата.
}
int main()
{
char a[1000] = { 0 }; // описываем массивы символов для хранения введенных чисел
char b[1000] = { 0 };
// Вводим два числа
cout << "a = ";
cin.getline(a, 1000);
cout << "b = ";
cin.getline(b, 1000);
// Выводим результат произведения
cout << a << "*" << b << "=" << mult(a, b) << endl;
cin.get();
return 0;
}
using namespace std;
char * mult(char *a, char *b)
{
int lena = strlen(a); // количество разрядов первого числа
int lenb = strlen(b); // количество разрядов второго числа
int k = lena + lenb; // количество разрядов результата
char *c = new char[k + 1]; // выделяем память для результата
c[k] = '\0'; // заканчиваем результат концом строки - '\0'
k--; // переходим к младшему разряду результата
int s; // индекс разряда результата начиная с младшего
for (int i = 0; i <= k; i++) // обнуляем все разряды результата
c[i] = 0;
for(int i=0; i<lena; i++) // цикл для всех разрядов первого множителя
for (int j = 0; j < lenb; j++) // цикл для всех разрядов второго множителя
{
int digit = (a[lena - i - 1] - '0') * // получаем цифру разряда первого множителя
(b[lenb - j - 1] - '0'); // получаем цифру разряда второго множителя и перемножаем их
s = i + j; // находим текущий разряд произведения
while (digit > 0) // пока произведение разрядов положительно
{
// к текущему разряду результата добавляем остаток от деления произведения разрядов множителей на 10
c[k - s] += digit % 10;
if (c[k - s] > 9) // если получилась не цифра
{
c[k - s] = c[k - s] % 10; // оставляем в этом разряде остаток от деления на 10
c[k - s - 1]++; // добавляем 1 к предыдущему разряду
}
digit /= 10; // корректируем предыдущую цифру разряда результата
s++; // переходим к предыдущему разряду результата
if (s > k) s = k; // не выходить за границы числа
}
}
int begin = k - s; // определяем первый значащий разряд результата, не равный 0
while (c[begin] == 0 && begin <k) begin++; // пропускаем ведущие нули
for (int i = begin; i <= k; i++) // все значащие разряды результата заменяем соответствующей цифрой
c[i] += '0';
return &c[begin]; // передаем указатель на первый значащий разряд результата.
}
int main()
{
char a[1000] = { 0 }; // описываем массивы символов для хранения введенных чисел
char b[1000] = { 0 };
// Вводим два числа
cout << "a = ";
cin.getline(a, 1000);
cout << "b = ";
cin.getline(b, 1000);
// Выводим результат произведения
cout << a << "*" << b << "=" << mult(a, b) << endl;
cin.get();
return 0;
}
Результат выполнения
