Рубрики

Умножение больших чисел в виде строк

Даны два числа в виде строк. Числа могут быть очень большими (могут не помещаться в long long int), задача состоит в том, чтобы найти произведение этих двух чисел.

Примеры:

Input : num1 = 4154  
        num2 = 51454
Output : 213739916 

Input :  num1 = 654154154151454545415415454  
         num2 = 63516561563156316545145146514654 
Output : 41549622603955309777243716069997997007620439937711509062916

Идея основана на школьной математике.

Мы начинаем с последней цифры второго числа, умножаем его на первое число. Затем мы умножаем вторую цифру второго числа на первое число и так далее. Мы добавляем все эти умножения. При добавлении ставим умножение i-го смещения.

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

C ++

// C ++ программа для умножения двух представленных чисел
// как строки.
#include<bits/stdc++.h>

using namespace std;

  
// Умножает str1 и str2 и печатает результат.
string multiply(string num1, string num2)
{

    int len1 = num1.size();

    int len2 = num2.size();

    if (len1 == 0 || len2 == 0)

    return "0";

  

    // сохранит номер результата в векторе

    // в обратном порядке

    vector<int> result(len1 + len2, 0);

  

    // Ниже два индекса используются для поиска позиций

    // в результате.

    int i_n1 = 0; 

    int i_n2 = 0; 

      

    // Идем справа налево в num1

    for (int i=len1-1; i>=0; i--)

    {

        int carry = 0;

        int n1 = num1[i] - '0';

  

        // Сдвигать позицию влево после каждого

        // умножение цифры в num2

        i_n2 = 0; 

          

        // Перейти справа налево в num2

        for (int j=len2-1; j>=0; j--)

        {

            // Взять текущую цифру второго числа

            int n2 = num2[j] - '0';

  

            // Умножаем на текущую цифру первого числа

            // и добавляем результат к ранее сохраненному результату

            // в текущей позиции.

            int sum = n1*n2 + result[i_n1 + i_n2] + carry;

  

            // перенос для следующей итерации

            carry = sum/10;

  

            // Сохранить результат

            result[i_n1 + i_n2] = sum % 10;

  

            i_n2++;

        }

  

        // хранить перенос в следующей ячейке

        if (carry > 0)

            result[i_n1 + i_n2] += carry;

  

        // Сдвигать позицию влево после каждого

        // умножение цифры в num1.

        i_n1++;

    }

  

    // игнорируем нули справа

    int i = result.size() - 1;

    while (i>=0 && result[i] == 0)

    i--;

  

    // Если бы все были '0' - означает либо оба, либо

    // один из num1 или num2 был '0'

    if (i == -1)

    return "0";

  

    // генерируем строку результата

    string s = "";

      

    while (i >= 0)

        s += std::to_string(result[i--]);

  

    return s;

}

  
// Код драйвера

int main()

{

    string str1 = "1235421415454545454545454544";

    string str2 = "1714546546546545454544548544544545";

      

    if((str1.at(0) == '-' || str2.at(0) == '-') && 

        (str1.at(0) != '-' || str2.at(0) != '-' ))

        cout<<"-";

  

  

    if(str1.at(0) == '-' && str2.at(0)!='-')

        {

            str1 = str1.substr(1);

        }

        else if(str1.at(0) != '-' && str2.at(0) == '-')

        {

            str2 = str2.substr(1);

        }

        else if(str1.at(0) == '-' && str2.at(0) == '-')

        {

            str1 = str1.substr(1);

            str2 = str2.substr(1);

        }

    cout << multiply(str1, str2);

    return 0;

}

Джава

// Java программа для умножения двух чисел
// представлены в виде строк.

class GFG

{

      
// Умножает str1 и str2 и печатает результат.

static String multiply(String num1, String num2)

{

    int len1 = num1.length();

    int len2 = num2.length();

    if (len1 == 0 || len2 == 0)

        return "0";

  

    // сохранит номер результата в векторе

    // в обратном порядке

    int result[] = new int[len1 + len2];

  

    // Ниже два индекса используются для

    // найти позиции в результате.

    int i_n1 = 0

    int i_n2 = 0

      

    // Идем справа налево в num1

    for (int i = len1 - 1; i >= 0; i--)

    {

        int carry = 0;

        int n1 = num1.charAt(i) - '0';

  

        // Сдвигать позицию влево после каждого

        // множитель числа в num2

        i_n2 = 0

          

        // Перейти справа налево в num2

        for (int j = len2 - 1; j >= 0; j--)

        {

            // Взять текущую цифру второго числа

            int n2 = num2.charAt(j) - '0';

  

            // Умножаем на текущую цифру первого числа

            // и добавляем результат к ранее сохраненному результату

            // charAt текущая позиция.

            int sum = n1 * n2 + result[i_n1 + i_n2] + carry;

  

            // Нести для следующего itercharAtion

            carry = sum / 10;

  

            // Сохранить результат

            result[i_n1 + i_n2] = sum % 10;

  

            i_n2++;

        }

  

        // хранить перенос в следующей ячейке

        if (carry > 0)

            result[i_n1 + i_n2] += carry;

  

        // Сдвигать позицию влево после каждого

        // множитель числа в num1.

        i_n1++;

    }

  

    // игнорируем нули справа

    int i = result.length - 1;

    while (i >= 0 && result[i] == 0)

    i--;

  

    // Если бы все были '0' - означает либо оба

    // или один из num1 или num2 был '0'

    if (i == -1)

    return "0";

  

    // genercharAte Строка результата

    String s = "";

      

    while (i >= 0)

        s += (result[i--]);

  

    return s;

}

  
// Код драйвера

public static void main(String[] args) 

{

    String str1 = "1235421415454545454545454544";

    String str2 = "1714546546546545454544548544544545";

  

    if ((str1.charAt(0) == '-' || str2.charAt(0) == '-') && 

        (str1.charAt(0) != '-' || str2.charAt(0) != '-'))

        System.out.print("-");

  

    if (str1.charAt(0) == '-' && 

        str2.charAt(0) != '-'

    {

        str1 = str1.substring(1);

    

    else if (str1.charAt(0) != '-' && 

             str2.charAt(0) == '-')

    {

        str2 = str2.substring(1);

    

    else if (str1.charAt(0) == '-' && 

             str2.charAt(0) == '-')

    {

        str1 = str1.substring(1);

        str2 = str2.substring(1);

    }

    System.out.println(multiply(str1, str2));

}
}

  
// Этот код предоставлен ankush_953

python3

# Python3 программа для умножения двух чисел
# представлен в виде строк.

  
# Умножает str1 и str2 и печатает результат.

def multiply(num1, num2):

    len1 = len(num1)

    len2 = len(num2)

    if len1 == 0 or len2 == 0:

        return "0"

  

    # сохранит номер результата в векторе

    # в обратном порядке

    result = [0] * (len1 + len2)

      

    # Ниже два индекса используются для

    # найти позиции в результате.

    i_n1 = 0

    i_n2 = 0

  

    # Идти справа налево в num1

    for i in range(len1 - 1, -1, -1):

        carry = 0

        n1 = ord(num1[i]) - 48

  

        # Сдвигать позицию влево после каждого

        # умножение цифры в num2

        i_n2 = 0

  

        # Идти справа налево в num2

        for j in range(len2 - 1, -1, -1):

              

            # Взять текущую цифру второго числа

            n2 = ord(num2[j]) - 48

          

            # Умножить на текущую цифру первого числа

            # и добавить результат к ранее сохраненному результату

            # в текущей позиции.

            summ = n1 * n2 + result[i_n1 + i_n2] + carry

  

            # Продолжить для следующей итерации

            carry = summ // 10

  

            # Сохранить результат

            result[i_n1 + i_n2] = summ % 10

  

            i_n2 += 1

  

            # магазин нести в следующую клетку

        if (carry > 0):

            result[i_n1 + i_n2] += carry

  

            # Сдвигать позицию влево после каждого

            # умножение цифры в num1.

        i_n1 += 1

          

        # печать (результат)

  

    # игнорировать нули справа

    i = len(result) - 1

    while (i >= 0 and result[i] == 0):

        i -= 1

  

    # Если бы все были '0' - означает либо оба, либо

    # один из num1 или num2 был '0'

    if (i == -1):

        return "0"

  

    # сгенерировать строку результата

    s = ""

    while (i >= 0):

        s += chr(result[i] + 48)

        i -= 1

  

    return s

  
# Код драйвера

str1 = "1235421415454545454545454544"

str2 = "1714546546546545454544548544544545"

  

if((str1[0] == '-' or str2[0] == '-') and 

   (str1[0] != '-' or str2[0] != '-')):

    print("-", end = '')

  

  

if(str1[0] == '-' and str2[0] != '-'):

    str1 = str1[1:]

elif(str1[0] != '-' and str2[0] == '-'):

    str2 = str2[1:]

elif(str1[0] == '-' and str2[0] == '-'):

    str1 = str1[1:]

    str2 = str2[1:]

print(multiply(str1, str2))

  
# Этот код предоставлен ankush_953

C #

// C # программа для умножения двух чисел
// представлены в виде строк.

using System;

  

class GFG 

      
// Умножает str1 и str2 и печатает результат.

static String multiply(String num1, String num2) 

    int len1 = num1.Length; 

    int len2 = num2.Length; 

    if (len1 == 0 || len2 == 0) 

        return "0"

  

    // сохранит номер результата в векторе

    // в обратном порядке

    int []result = new int[len1 + len2]; 

  

    // Ниже два индекса используются для

    // найти позиции в результате.

    int i_n1 = 0; 

    int i_n2 = 0; 

    int i;

      

    // Идем справа налево в num1

    for (i = len1 - 1; i >= 0; i--) 

    

        int carry = 0; 

        int n1 = num1[i] - '0'

  

        // Сдвигать позицию влево после каждого

        // множитель числа в num2

        i_n2 = 0; 

          

        // Перейти справа налево в num2

        for (int j = len2 - 1; j >= 0; j--) 

        

            // Взять текущую цифру второго числа

            int n2 = num2[j] - '0'

  

            // Умножаем на текущую цифру первого числа

            // и добавляем результат к ранее сохраненному результату

            // charAt текущая позиция.

            int sum = n1 * n2 + result[i_n1 + i_n2] + carry; 

  

            // Нести для следующего itercharAtion

            carry = sum / 10; 

  

            // Сохранить результат

            result[i_n1 + i_n2] = sum % 10; 

  

            i_n2++; 

        

  

        // хранить перенос в следующей ячейке

        if (carry > 0) 

            result[i_n1 + i_n2] += carry; 

  

        // Сдвигать позицию влево после каждого

        // множитель числа в num1.

        i_n1++; 

    

  

    // игнорируем нули справа

    i = result.Length - 1; 

    while (i >= 0 && result[i] == 0) 

    i--; 

  

    // Если бы все были '0' - означает либо оба

    // или один из num1 или num2 был '0'

    if (i == -1) 

    return "0"

  

    // genercharAte Строка результата

    String s = ""

      

    while (i >= 0) 

        s += (result[i--]); 

  

    return s; 

  
// Код драйвера

public static void Main(String[] args) 

    String str1 = "1235421415454545454545454544"

    String str2 = "1714546546546545454544548544544545"

  

    if ((str1[0] == '-' || str2[0] == '-') && 

        (str1[0] != '-' || str2[0] != '-')) 

        Console.Write("-"); 

  

    if (str1[0] == '-' && str2[0] != '-'

    

        str1 = str1.Substring(1); 

    

    else if (str1[0] != '-' && str2[0] == '-'

    

        str2 = str2.Substring(1); 

    

    else if (str1[0] == '-' && str2[0] == '-'

    

        str1 = str1.Substring(1); 

        str2 = str2.Substring(1); 

    

    Console.WriteLine(multiply(str1, str2)); 


}

  
// Этот код предоставлен Rajput-Ji

Выход:

2118187521397235888154583183918321221520083884298838480662480

Приведенный выше код адаптирован из кода, предоставленного Gaurav.

Сложность времени: O (m * n), где m и n — длина двух чисел, которые необходимо умножить.
Другой метод:

// Java-программа для умножения двух представленных чисел
// как строки.

import java.util.Scanner;

  

public class StringMultiplication

{

    // Код драйвера

    public static void main(String[] args) 

    {

        String num1 = "1235421415454545454545454544";

        String tempnum1 = num1;

        String num2 = "1714546546546545454544548544544545";

        String tempnum2 = num2;

          

        // Проверяем условие, если одна строка отрицательна

        if(num1.charAt(0) == '-' && num2.charAt(0)!='-')

        {

            num1 = num1.substring(1);

        }

        else if(num1.charAt(0) != '-' && num2.charAt(0) == '-')

        {

            num2 = num2.substring(1);

        }

        else if(num1.charAt(0) == '-' && num2.charAt(0) == '-')

        {

            num1 = num1.substring(1);

            num2 = num2.substring(1);

        }

        String s1 = new StringBuffer(num1).reverse().toString();

        String s2 = new StringBuffer(num2).reverse().toString();

          

        int[] m = new int[s1.length()+s2.length()];

                  

                // Идем справа налево в num1

        for (int i = 0; i < s1.length(); i++) 

        {

            // Перейти справа налево в num2

            for (int j = 0; j < s2.length(); j++) 

            {

                m[i+j] = m[i+j]+(s1.charAt(i)-'0')*(s2.charAt(j)-'0');

              

            }

        }

          

      

        String product = new String();

        // Умножаем на текущую цифру первого числа

        // и добавляем результат к ранее сохраненному продукту

        // в текущей позиции.

        for (int i = 0; i < m.length; i++)

        {

            int digit = m[i]%10;

            int carry = m[i]/10;

            if(i+1<m.length)

            {

                m[i+1] = m[i+1] + carry;

            }

            product = digit+product;

              

        }

          

        // игнорируем нули справа

        while(product.length()>1 && product.charAt(0) == '0')

        {

            product = product.substring(1);

        }

          

        // Проверяем условие, если одна строка отрицательна

        if(tempnum1.charAt(0) == '-' && tempnum2.charAt(0)!='-')

        {

            product = new StringBuffer(product).insert(0,'-').toString();

        }

        else if(tempnum1.charAt(0) != '-' && tempnum2.charAt(0) == '-')

        {

            product = new StringBuffer(product).insert(0,'-').toString();

        }

        else if(tempnum1.charAt(0) == '-' && tempnum2.charAt(0) == '-')

        {

            product = product;

        }

        System.out.println("Product of the two numbers is :"+"\n"+product);

    }

}

Выход:

2118187521397235888154583183918321221520083884298838480662480

Связанная статья:
Алгоритм Карацубы для быстрого умножения

Эта статья предоставлена Адитьей Кумаром . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Умножение больших чисел в виде строк

0.00 (0%) 0 votes