藍橋杯 算法提高 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;
}