dashuxch.cpp

大数相乘算法,使用C++语言在VC下实现.

//实现一个计算大位数（如100位以上）相乘结果的函数string multiply(sting,string)。（请完全用算法实现） 

//我用一个类来实现的，不过基本算法就是操作符*的实现。我用到了string，不知道是否符合。下面给出代码：
// multiplition.cpp : Defines the entry point for the console application.
//

#include <iostream>
#include <string>


using namespace std;

class slong
{
public:
	slong()
	{
		_str = "";
	}

	slong(string str) 
	{
		string::iterator itor = str.begin();
		for(; itor != str.end(); ++itor)
		{
			if(*itor < '0' || *itor > '9')
				throw "the parameter is error.";
		}
		_str = str;
	}

	slong(char* s)
	{
		if(s == NULL)
		{
			_str = "";
			return;
		}

		size_t size = strlen(s);
		for(size_t i = 0; i < size; ++i)
		{
			if(s[i] < '0' || s[i] > '9')
				throw "the parameter is error.";
		}

		_str = s;


	}

	slong(const slong& sl)
	{
		_str = sl._str;
	}

	slong& operator =(const slong& sl)
	{
		if(&sl == this)
			return *this;
		_str = sl._str;
		return *this;
	}

	slong operator *(slong& sl)
	{
		if(sl._str.length() == 0)
			return *this;

		int n = static_cast<int>(sl._str.length());
		int m = static_cast<int>(this->_str.length());

		int t = m + n - 1; // caculate times

		string::reverse_iterator itor1, itor2;
		int j = 0;
		int k = 0;

		int c = 0;
		int r = 0;
		int v = 0;

		char s[2];

		string rproduct;
		for(int i = 0; i < t; ++i)
		{
			v = 0;
			j = 0;
			
			itor1 = _str.rbegin();
			
			for(; itor1 != _str.rend(); ++itor1)
			{
				k = 0;
				itor2 = sl._str.rbegin();
				for(; itor2 != sl._str.rend(); ++itor2)
				{
					if(j + k == i)
					{
						v += ctoi(*itor1) * ctoi(*itor2);
						break;
					}
					k++;
				}
				j++;
				if(j > i)
					break;
			}

			v += c;
			r = v%10;
			c = v/10;
			
			itoa(r, s, 10);
			rproduct += s;
		}

		if(c != 0)
		{
			itoa(c, s, 10);
			rproduct += s;
		}

		string temp;
		temp.resize(rproduct.length());
		string::reverse_iterator ritor = rproduct.rbegin();
		string::iterator itor = temp.begin();
		for(; itor != temp.end(); ++itor)
		{
			*itor = *ritor;
			ritor++;
		}

		slong product(temp);
		return product;
	}

	int ctoi(char c)
	{
		return c - 48;
	}

	string value()
	{
		return _str;
	}

private:
	string _str;
};

int main( )
{
	string s1, s2;
	cout << "please input first operator" << endl;
	cin >> s1;
	cout << "please input second operator" << endl;
	cin >> s2;

	slong sl1(s1);
	slong sl2(s2);

	slong sl3 = sl1 * sl2;
	cout << "the value is :" << endl;
	cout << sl3.value() << endl;

	char word;
	while(cin >> word)
		if(word == 'q')
			break;

	return 0;
}