polynomial.cpp

我写的多项式操作代码

#include "polynomial.h"

int Polynomial :: _accuracy = 16;

Polynomial :: Polynomial( double i )
{
	if( i == 0 )
	{
		_degree = -1;
		_a = NULL;
	}
	else
	{
		_degree = 0;
		_a = new double [ 1 ];
		_a[ 0 ] = i;
	}
	
	( *this ).condense();
}

Polynomial :: Polynomial( int i , double *source )
{
	int j;

	_degree = i;
	_a = new double [ i + 1 ];
	
	for( j = 0; j <= i; j++ )
		_a[ j ] = source[ j ];

	( *this ).condense();
		//In case the highest coefficient is equal to zero.
}

Polynomial :: Polynomial( Polynomial &source ){
	_degree = source._degree;
		
	if( _degree != -1 )
	{
		_a = new double [ source._degree + 1 ];
		for( int i = 0; i <= _degree; i++ )
			_a[ i ] = source._a[ i ];
	}
	else
		_a = NULL;
}

Polynomial :: ~Polynomial()
{
	delete [] _a;
}

void Polynomial :: condense()
{
	int i = 0, temp = _degree;
	double accNo = 1;
	
	for( i = 1; i <= _accuracy; i++ )
	{
		accNo *= 10;
	}
	
	for( i = 0; i <= _degree; i++ )
	{
		_a[ i ] = floor( _a[ i ] * accNo ) / accNo;
	}

	i = 0;
	while( i <= temp && _a[ i ] == 0 )
	{
		_degree--;
		i++;
	}
	
	if( _degree < temp )
	{
		if ( _degree == -1 )
		{
			delete [] _a;
			_a = NULL;
		}
		else
		{
			double *temp_stat = _a;
			_a = new double [ _degree + 1 ];
			
			for( int j = 0; j <= _degree; j++ )
				_a[ j ] = temp_stat[ j + i ];
			
			delete [] temp_stat;
		}
	}
}

Polynomial &Polynomial :: operator=( const Polynomial& source )
{
	if( this != &source )
	{
		_degree = source._degree;
		
		if( _degree != 0 )
		{
			delete [] _a;
			_a = new double [ source._degree + 1 ];
			for( int i = 0; i <= _degree; i++ )
				_a[ i ] = source._a[ i ];
		}
		else
			_a = NULL;
	}
	return *this;
}

void Polynomial :: display( char * signal ) const
{
	if( _degree != -1 )
	{
		for( int i = 0; i <= _degree; i++ )
		{
			if( _a[ i ] != 0 )
			{
				if( i != 0 && _a[ i ] > 0 )
					cout << " + ";

				if( _a[ i ] < 0 )
					cout << " - ";

				if( i != _degree )
				{
					if( _a[ i ] != 1 && _a[ i ] > 0 )
						cout << _a[ i ] ;
				
					if( _a[ i ] != -1 && _a[ i ] < 0 )
						cout << - _a[ i ];
				}
				else
				{
					if( _a[ i ] > 0 )
						cout << _a[ i ] ;
				
					if( _a[ i ] < 0 )
						cout << - _a[ i ];
				}

				
				if( i == _degree )
					;
				else
				{
					cout << signal;
					if( i == _degree - 1 )
						;
					else
						cout << '^' << _degree - i;
				}
			}
		}
	}
	else
		cout << 0;

}

Polynomial Polynomial :: operator +( const Polynomial &second ) const
{
	Polynomial *larger,*smaller;
	
	if( _degree > second._degree )
	{
		larger = ( Polynomial * )this;
		smaller = ( Polynomial * )&second;
	}
	else
	{
		larger = ( Polynomial * )&second;
		smaller = ( Polynomial * )this;
	}

	Polynomial result = *larger;
	
	for( int i = 0; i <= smaller->_degree; i++ )
	{
		result._a[ larger->_degree - smaller->_degree + i ] += smaller->_a[ i ];
	}

	result.condense();

	return result;
}

Polynomial Polynomial :: operator *( double factor ) const
{
	Polynomial result = *( Polynomial * )this;

	if( factor == 0.0 )
		return Polynomial();

	for( int i = 0; i <= _degree; i++ )
	{
		result._a[ i ] = _a[ i ] * factor;
	}

	return result;
}

Polynomial Polynomial :: operator -( const Polynomial & source ) const
{
	return *this + source * ( -1.0 );
}

bool Polynomial :: operator ==( const Polynomial &second ) const
{
	if( _degree != second._degree )
		return false;
	
	for( int i = 0; i <= _degree; i++ )
		if( _a[ i ] != second._a[ i ] )
			return false;
	
	return true;
}

Polynomial Polynomial :: operator *( const Polynomial & second ) const
{
	if( _degree == -1 || second._degree == -1 )
		return Polynomial();

	int i;
	double *a;
	a = new double [ _degree + second._degree + 1 ];
	
	for( i = 0; i <= second._degree; i++ )
		a[ i ] = 0;

	for( i = 0; i <= second._degree; i++ )
	{
		for( int j = 0; j <= _degree; j++ )
		{
			a[ i + j ] += _a[ j ] * second._a[ i ];
		}
	}

	Polynomial result( _degree + second._degree, a );
	delete [] a;
	
	return result;

}

ostream &operator <<( ostream &in, const Polynomial &source )
{
	source.display();

	return in;
}

Polynomial Polynomial :: divide( const Polynomial &item, Polynomial &compliment ) const
{
	if( item == Polynomial( 0 ) )
	{
		cout << endl << " * * * Error! Can't divided by 0! Programme terminated. * * * " << endl;
		cin.get();
		exit( 0 );
	}

	if( _degree == -1 )
	{
		compliment = 0;
		return Polynomial( 0 );
	}

	if( _degree < item._degree )
	{
		compliment = *this;
		return Polynomial( 0 );
	}

	double *quotient = new double [ _degree - item._degree + 1 ];
	double *comp = new double[ _degree + 1 ];
	int i, j;

	for( i = 0; i <= _degree; i++ )
		comp[ i ] = _a[ i ];
	
	for( i = 0; i <= _degree - item._degree; i++ )
	{
		quotient[ i ] = comp[ i ] / item._a[ 0 ];
		for( j = i; j <= i + item._degree; j++ )
			comp[ j ] -= item._a[ j - i ] * quotient[ i ];
	}

	compliment = Polynomial( item._degree, comp + _degree - item._degree );
	compliment.condense();

	Polynomial answer( _degree - item._degree, quotient );
	answer.condense();
	
	delete [] quotient;
	delete [] comp;

	return answer;
}

Polynomial Polynomial :: diff() const
{
	if( _degree <= 0 )
		return Polynomial( 0 );

	double *a = new double[ _degree ];

	for( int i = 0; i <= _degree - 1; i++ )
	{
		a[ i ] = _a[ i ] * ( _degree - i );
	}

	Polynomial result( _degree - 1, a );
	
	delete [] a;

	return result;
}

Polynomial Polynomial :: integrate() const
{
	if( _degree == -1 )
		return Polynomial( 0 );

	double * a = new double [ _degree + 2 ];

	for( int i = 0; i <= _degree; i++ )
	{
		a[ i ] = _a[ i ] / ( _degree + 1 - i );
	}

	a[ _degree +1 ] = 0;

	Polynomial result( _degree + 1, a );
	delete [] a;

	return result;
}

Polynomial operator +( double i, const Polynomial &a )
{
	return a + i;
}

double Polynomial :: function( double variable )
{
	double result, base = 1;
	
	if( _degree == -1 )
		return 0;

	result = _a[ _degree ];

	for( int i = 1; i <= _degree; i++ )
	{
		base *= variable;
		result += base * _a[ _degree - i ];
	}

	return result;
}

int Polynomial :: root( double *rootNo )
{
	if( _degree == -1 )
		return -1;
	if( _degree == 0 )
		return 0;

	double step = 1;
	int i, number = 0, temp = 0;
	double accNo = pow( 10, _accuracy );

	for( i = 0; i <= _degree; i++ )
	{
		step *= _a[ i ];
		temp += ( i + 1 );
	}

	step = pow( step, ( double )( 1 / temp ) );
	
	for( i = 0; i <= _degree * 4; i++ )
	{
		double root = step * ( i - _degree * 2 ), preRoot, k, b;
		int flag = 0, j, times = 0;
		do{
			times++;
			k = diff().function( root );
			preRoot = root;
			root = preRoot - function( preRoot ) / k;
		}while( fabs( preRoot - root ) > 1 / accNo && times <= 100 );

		if( times == 100 )
			continue;
		else
		{
			for( j = 0; j < number; j++ )
			{
				if( fabs( rootNo[ j ] - root ) <= accNo )
				{
					flag = 1;
				}
				
			}
			if( flag == 1 )
				continue;
			else
			{
					rootNo[ number ] = floor( root * accNo ) / accNo;
					number++;
			}
		}
	}
	
	return number;
	
}