Mnożenie pisemne dużych liczb
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!

Mnożenie pisemne dużych liczb

AutorWiadomość
Temat założony przez niniejszego użytkownika
Mnożenie pisemne dużych liczb
» 2019-10-21 23:31:17
Zastanawiam się jak przemnożyć przez siebie liczby mocno wykraczające poza zakres obsługiwany przez zmienne domyślnie w C++, na przykład chciałbym wyświetlić 900!. Myślałem nad zapisaniem cyfr kolejnych silni w dwóch tablicach, na początku tab1 tab2 jako zapisane cyfry 1! i 2!, potem pod tab 2 podstawiona wyliczona kolejna silnia.

Rozumiem że żeby mnożyć pisemnie 2 liczby muszę przemnożyć każdą cyfrę z 2giej liczby po kolei przez każdą cyfrę 1szej liczby, i zostawić w rzędzie w którym zacząłem mnożyć %10 iloczynu tych 2 mnożonych w danym momencie liczb. Nie wiem jednak jak przenosić dalej liczbę dziesiątek, tzn. w jaki sposób zadeklarować to aby była ona cały czas przenoszona w lewo, jeśli jest taka potrzeba. Raz to nie problem sprawdzić, ale nie wiem jak zdefiniować to tak żeby szła w lewą stronę jeśli cyfra na danej pozycji + przeniesienie > 10.

C/C++
int main()
{
    int n, p = 1;
    int a = 1;
    cout << "Podaj N: ";
    cin >> n;
   
    int tab1[ 301 ];
    int tab2[ 301 ];
   
    tab1[ 300 ] = 1;
    tab2[ 300 ] = 2;
   
    while( p <= n ) //p to obecna silnia przez którą mnożę (np liczba w tab1 *p!)
    {
       
        for( int i = 300; i >= 0; i-- )
        {
            for( int z = 300; z >= 0; z-- )
            {
                if( tab2[ i ] != 0 ) //omijam mnożenie przez 0
                {
                    wynik = tab1[ z ] * tab2[ i ];
                   
                    for( int j = 300; j >= 0; j-- ) //blokada twórcza
                    {
                        zostaje = wynik % 10;
                        przeniesienie =( wynik - zostaje ) / 10;
                        tab1[ j ] = zostaje;
                    }
                }
            }
        }
       
       
    }
    return 0;
}

To jest oczywiście niekompletne rozwiązanie, ale chciałbym zaczerpnąć waszej wiedzy bo czuję się jakbym próbował głową rozbić mur.

Dziękuję za pomoc!
P-175406
» 2019-10-22 11:43:46
Poniżej masz kod zaczerpnięty z internetu (lekko zmodyfikowany), w którym mnożone liczby reprezentowane są przez stringi ( n.p. "78476887634764234554660008988643242342355324394832447" ).
Funkcja mnoży tylko liczby dodatnie - jak chcesz to możesz łatwo przerobić to na liczby ujemne.

C/C++
#include <iostream>
#include <vector>

using namespace std;

string multiply( const string & number1, const string & number2 )
{
    if( number1.size() == 0 || number2.size() == 0 ) return "0";
   
    // will keep the result number in vector
    // in reverse order
    vector < int > result( number1.size() + number2.size(), 0 );
   
    // Below two indexes are used to find positions
    // in result.
    int i_n1 = 0;
    int i_n2 = 0;
   
    // Go from right to left in number1
    for( int i = number1.size() - 1; i >= 0; --i )
    {
        int carry = 0;
        int n1 = number1[ i ] - '0';
       
        // To shift position to left after every
        // multiplication of a digit in num2
        i_n2 = 0;
       
        // Go from right to left in number2
        for( int j = number2.size() - 1; j >= 0; j-- )
        {
            // Take current digit of second number
            int n2 = number2[ j ] - '0';
           
            // Multiply with current digit of first number
            // and add result to previously stored result
            // at current position.
            int sum = n1 * n2 + result[ i_n1 + i_n2 ] + carry;
           
            // Carry for next iteration
            carry = sum / 10;
           
            // Store result
            result[ i_n1 + i_n2 ] = sum % 10;
           
            ++i_n2;
        }
       
        // store carry in next cell
        if( carry > 0 ) result[ i_n1 + i_n2 ] += carry;
       
        // To shift position to left after every
        // multiplication of a digit in number1.
        ++i_n1;
    }
   
    // ignore '0's from the right
    int i = result.size() - 1;
    while( i >= 0 && result[ i ] == 0 ) --i;
   
    // If all were '0's - means either both or
    // one of number1 or number2 were '0'
    if( i == - 1 ) return "0";
   
    // generate the result string
    string s { };
   
    while( i >= 0 ) s += to_string( result[ i-- ] );
   
    return s;
}

int main()
{
    cout << multiply( "278234774683724632452562718636464731461255252312312445555578654622003938366414", "148847262565343249383772625411256334895099263564002923576" );
   
    return 0;
}
.
P-175407
« 1 »
 Strona 1 z 1