一起学习交流~

大整数计算-04-乘法

算法 laomuji 11个月前 (11-06) 525次浏览 已收录 0个评论

一、原理

乘法花费的时间要比其它计算花的多很多,

A数组的每一位都要乘B数组的每一位

需要两层循环嵌套,时间复杂度n^2

写起来不难,理解起来也很容易,我就不多废话了

二、代码

	static string m_multiply(const string& data1, const string& data2)
	{
		const char* cData1 = data1.c_str();
		const char* cData2 = data2.c_str();
		//如果有一个数为0,返回0
		if (cData1[0] == '0')return "0";
		if (cData2[0] == '0')return "0";
		int len1 = data1.size();
		int len2 = data2.size();
		char* num1 = new char[len1];
		char* num2 = new char[len2];
		//把字符转为数字
		for (int i = 0; i < len1; i++)num1[i] = cData1[i] - '0';
		for (int i = 0; i < len2; i++)num2[i] = cData2[i] - '0';
		//999*999=998001,结果长度最大为两个数的长度相加
		int k = len1 + len2 + 1;//多一个结束符
		char* result = new char[k] {0};

		//循环乘
		for (int i = len1 - 1; i >= 0; i--)
		{
			for (int j = len2 - 1; j >= 0; j--)
			{
				char product = (num1[i]) * (num2[j]) + result[i + j + 1];
				if (product > 9)
				{
					result[i + j] += product / 10;
					product %= 10;
				}
				result[i + j + 1] = product;
			}
		}
		//把数字转为字符
		for (int i = 0; i < k - 1; i++)result[i] += '0';

		string data3;
		if (result[0] == '0')data3 = result + 1;
		else data3 = result;
		delete[] result;
		delete[] num1;
		delete[] num2;
		return data3;
	}
喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论