蓝桥杯 算法提高 ADV-197 P1001 大数乘法

算法提高 P1001

时间限制：1.0s 内存限制：256.0MB

　　当两个比较大的整数相乘时，可能会出现数据溢出的情形。为避免溢出，可以采用字符串的方法来实现两个大数之间的乘法。具体来说，首先以字符串的形式输入两个整数，每个整数的长度不会超过8位，然后把它们相乘的结果存储在另一个字符串当中（长度不会超过16位），最后把这个字符串打印出来。例如，假设用户输入为：62773417和12345678，则输出结果为：774980393241726.

输入：

　　62773417 12345678

输出：

　　774980393241726

分析：对于用字符串存大整数，并且进行乘法操作问题，主要考虑的就是进位的问题。而乘法不同于加减，加减只需要按位一位一位的去操作，我们小学就学过乘法计算的步骤，是被乘数依次去乘以乘数的每一位，然后进行相加，所以就不能直接一个循环去解决，而需要一个二重循环，具体思路见下图：

　　然后还有一点就是：两个数相乘的积的最大位数是两个数位数之和，比如一个2位数乘以一个3位数，最多只有5位数，所以我创建的存结果的字符串长度就是len1+len2；初始化为‘0’方便加法运算，就是我们乘完的结果是要有进位的，存进去的方式是加上该位计算后的值。

　　代码如下：

#include <iostream>
#include <cstring>
using namespace std;

void fun(string s1, string s2)
{
	int len1 = s1.length(), len2 = s2.length();
	int len = len1 + len2;
	int wei, num;												//wei为当前运算位，num是当前位的值 
	string s(len, '0');
	
	for(int i = 0; i < len1; i++)
	{
		for(int j = 0; j < len2; j++)
		{
			wei = len - 2 - (i + j);								//初始化当前位
			num = (s[wei]-'0') + (s1[i]-'0') * (s2[j]-'0');		//计算当前位的值 
			while(1)
			{	/*循环判断是否进位*/
				if(num > 9)
				{	/*如果需要进位，进位并循环判断下一位是否进位*/
					s[wei] = num % 10 + '0';					//当前位结果
					num = (s[++wei]-'0') + (num / 10);			//进位结果 
				}
				else
				{	/*如果不需进位，直接赋值并跳出循环*/
					s[wei] = num + '0';
					break;
				}
			}
		}
	}
	
	string::iterator it = s.end();
	it--;
	while(*it == '0') it--;	//去掉前导0 
	
	if(it >= s.begin())		//如果还有值，则输出，无值说明结果为0，被上面操作跳过了 
	{
		while(it >= s.begin())
		{
			cout << *it;
			it--;
		}
		cout << *it << endl;
	}
	else cout << 0 << endl;
}

int main()
{
	string s1, s2;
	
	cin >> s1 >> s2;
	fun(s1, s2);
	
	return 0;
}