[心得] 大數演算法 c++
前幾天腦袋在很渾沌的情況下，問了大數演算的問題，
經由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
→
01/09 22:49, , 1F
01/09 22:49, 1F
推
02/17 12:21, , 2F
02/17 12:21, 2F