PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[心得] 大數演算法 c++

看板Prob_Solve (計算數學 Problem Solving)作者Raisto (劉大俠)時間14年前 (2011/01/09 21:01)推噓1(1推 0噓 1→)

留言2則, 2人參與討論串1/1

前幾天腦袋在很渾沌的情況下，問了大數演算的問題，經由S大跟T大的點醒，使得這個程式碼才可以順利產出。要不然那天腦袋有點頓頓的，有些細節之處一時之間沒轉過來以下為程式碼程式碼 #include <iostream> #include <vector> #include <fstream> #include <string> using namespace std ; #define SIZE 512 int ctoi( char c ) { if( c == '0' ) return 0 ; if( c == '1' ) return 1 ; if( c == '2' ) return 2 ; if( c == '3' ) return 3 ; if( c == '4' ) return 4 ; if( c == '5' ) return 5 ; if( c == '6' ) return 6 ; if( c == '7' ) return 7 ; if( c == '8' ) return 8 ; if( c == '9' ) return 9 ; } class myBigInt { private: public: int Num[SIZE] ; myBigInt(); int getlenBigInt() ; myBigInt & operator = ( string s1 ) ; myBigInt & operator = ( const int & ) ; }; myBigInt::myBigInt() { for( int i = 0 ; i < SIZE ; i++ ) Num[i] = 0 ; } int myBigInt::getlenBigInt() { for( int i = SIZE - 1 ; i >= 0 ; i-- ) { if( Num[i] != 0 ) return i + 1 ; } } myBigInt & myBigInt::operator = ( const string s1 ) { int count = 0 ; for( int i = ( s1.size()- 1 ) ; i >= 0 ; i-- ) { Num[count] = ctoi( s1[i] ) ; count++ ; } return *this ; } myBigInt & myBigInt::operator = ( const int &a ) { Num[0] = a ; for( int i = 0 ; i < SIZE ; i++ ) { Num[i+1] += Num[i] / 10; // 進位 Num[i] %= 10 ; } return *this ; } /********************運算子重載***********************************/ ostream& operator << ( ostream &out , myBigInt &a ) { int i = SIZE - 1; while (i >= 0 && a.Num[i] == 0) i--; if (i < 0) out << '0'; else while (i >= 0) out << a.Num[i--]; //out << a.pringBigInt() ; return out ; } myBigInt operator * ( const myBigInt &a , const myBigInt &b ) { myBigInt c ; for( int i = 0 ; i < SIZE ; i++ ) for( int j = 0 ; j < SIZE ; j++ ) if( ( i + j ) < SIZE ) c.Num[i+j] += a.Num[i] * b.Num[j] ; for( int i = 0 ; i < SIZE ; i++ ) { c.Num[i+1] += c.Num[i] / 10; // 進位 c.Num[i] %= 10 ; } return c ; } myBigInt operator * ( const myBigInt &a , const int b ) { myBigInt c ; for( int i = 0 ; i < SIZE ; i++ ) c.Num[i] = a.Num[i] * b ; for( int i = 0 ; i < SIZE ; i++ ) { c.Num[i+1] += c.Num[i] / 10; // 進位 c.Num[i] %= 10 ; } return c ; } myBigInt operator + ( const myBigInt &a , const myBigInt &b ) { myBigInt c ; for( int i = 0 ; i < SIZE ; i++ ) c.Num[i] = a.Num[i] + b.Num[i] ; for( int i = 0 ; i < SIZE ; i++ ) { c.Num[i+1] += c.Num[i] / 10; // 進位 c.Num[i] %= 10 ; } return c ; } inline bool operator == ( const myBigInt &a , const myBigInt &b ) { for( int i = SIZE - 1 ; i >= 0 ; i++ ) if( a.Num[i] != b.Num[i] ) return false ; return true ; } inline bool operator == ( const myBigInt &a , const int &b ) { myBigInt c ; c = b ; if( a == c ) return true ; else return false ; } /****************************函式************************************/ myBigInt readData() { char name[100] ; cin >> name ; ifstream fin( name , ios::in ) ; if( !fin ) { //如果沒讀到資料，顯示讀取失敗 cerr << "File could not be open or not exist !" << endl ; //並結束程式 system("pause") ; exit( 1 ) ; } string s1 ; while( !fin.eof() ) fin >> s1 ; myBigInt b1 ; b1 = s1 ; return b1 ; } myBigInt tenPow ( int pow ) { myBigInt a ; a = "1" ; for( int i = 0 ; i < pow ; i++ ) a = a * 10 ; return a ; } myBigInt prod( myBigInt u , myBigInt v ) { myBigInt x , y , w , z , zero; int n , m ; zero = 0 ; n = u.getlenBigInt() ; //cout << "n " << n << endl ; //cout << "u " << u << endl ; //cout << "v " << v << endl ; if( u == 0 || v == 0 ) return zero ; else if ( n <= 4 ) return u * v ; else { //cout << "---------------------------------------------------------------" << endl ; m = n / 2 ; int count = m - 1 ; //cout << "m " << m << endl ; //cout << "count " << count << endl ; for( int i = n - 1 ; i >= m ; i-- ) { x.Num[count] = u.Num[i] ; w.Num[count] = v.Num[i] ; count--; } //cout << "x " << x << endl ; //cout << "w " << w << endl ; for( int i = m - 1 ; i >= 0 ; i-- ) { y.Num[i] = u.Num[i] ; z.Num[i] = v.Num[i] ; } //cout << "y " << y << endl ; //cout << "z " << z << endl ; myBigInt p , q , r ; p = prod( x , w ) * tenPow( 2 * m ) ; q = ( prod( w , y ) + prod( x , z ) ) * tenPow( m ) ; r = prod( y , z ) ; //cout << "p " << p << endl ; //cout << "q " << q << endl ; //cout << "r " << r << endl ; return p + q + r ; } } void outData( myBigInt a ) { //string s ; //s = bigIntegerToString(a) ; ofstream outfile( "c.txt" , ios::out ) ; outfile << a ; } /******************************************************************/ int main() { myBigInt a , b , c , d ; cout << "1st file:" ; a = readData() ; cout << "The value of content in 1st.txt: " << endl << a << endl ; cout << endl ; cout << "2nd file:" ; b = readData() ; cout << "The value of content in 2nd.txt: " << endl << b << endl ; cout << endl ; c = a * b ; cout << "a * b = " << endl << c << endl ; //d = prod( a , b ) ; //cout << "Mul = " << d << endl ; outData(d); system("pause") ; return 0 ; } -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.169.77.33