Mnożenie pisemne dużych liczb
Ostatnio zmodyfikowano 2019-10-22 11:43
kwdrt3000 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. 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 ) { for( int i = 300; i >= 0; i-- ) { for( int z = 300; z >= 0; z-- ) { if( tab2[ i ] != 0 ) { wynik = tab1[ z ] * tab2[ i ]; for( int j = 300; j >= 0; j-- ) { 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! |
|
TemplateEntity |
» 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. #include <iostream> #include <vector>
using namespace std;
string multiply( const string & number1, const string & number2 ) { if( number1.size() == 0 || number2.size() == 0 ) return "0"; vector < int > result( number1.size() + number2.size(), 0 ); int i_n1 = 0; int i_n2 = 0; for( int i = number1.size() - 1; i >= 0; --i ) { int carry = 0; int n1 = number1[ i ] - '0'; i_n2 = 0; for( int j = number2.size() - 1; j >= 0; j-- ) { int n2 = number2[ 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; ++i_n1; } int i = result.size() - 1; while( i >= 0 && result[ i ] == 0 ) --i; if( i == - 1 ) return "0"; string s { }; while( i >= 0 ) s += to_string( result[ i-- ] ); return s; }
int main() { cout << multiply( "278234774683724632452562718636464731461255252312312445555578654622003938366414", "148847262565343249383772625411256334895099263564002923576" ); return 0; }
. |
|
« 1 » |