Умножение многоразрядных чисел

Алгоритмизация / Умножение многоразрядных чисел

 

О переводе числа из символьной формы в числовую и обратно обсуждалось здесь.
Умножение положительных многоразрядных чисел ведется начиная с младшего разряда в следующем порядке

  • Рассматриваем массивы символов, представляющих числа начиная с конца.
  • Организуем вложенный цикл чтобы рассмотреть каждый разряд каждого числа.
  • Перемножаем рассматриваемые разряды чисел.
  • Выбираем текущий разряд результата как сумму номеров разрядов двух множителей.
  • Организуем цикл для разрядов полученного произведения начиная с младшего.
    • добавляем к текущему разряду остаток от деления произведения на 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
#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;
}


Результат выполнения
Произведение многоразрядных чиселПроизведение многоразрядных чиселПроизведение многоразрядных чиселПроизведение многоразрядных чисел


Назад: Алгоритмизация

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *