題目出處
-------------------------------------------------------------------------------------------題目-------------------------------------------------------------------------------------------
Bull Math
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 10910
Accepted: 5644
Description
Bulls are so much better at math than the cows. They can multiply huge integers together and get perfectly precise answers ... or so they say. Farmer John wonders if their answers are correct. Help him check the bulls' answers. Read in two positive integers (no more than 40 digits each) and compute their product. Output it as a normal number (with no extra leading zeros).
FJ asks that you do this yourself; don't use a special library function for the multiplication.
Input
* Lines 1..2: Each line contains a single decimal number.
Output
* Line 1: The exact product of the two input lines
Sample Input
11111111111111
1111111111
Sample Output
12345679011110987654321
-------------------------------------------------------------------------------------------結束-------------------------------------------------------------------------------------------
解法：簡單模擬
要點：
數據的存儲使用數組
觀察乘法的規律，就可以先相乘再相加進位
注意：存儲空間必須開大一點，不然就像我開始一樣不斷地WA，坑爹啊！
代碼：（先相乘完再進位）
也可以把進位的代碼放進每個數相乘的循環裡
[cpp]
#include <iostream>
using namespace std;
const int MAX=40;
const int result=80;
//空間必須開一些
char a[MAX+10]; //接受鍵盤輸入的數
char b[MAX+10];
int amul[MAX+10];//存儲轉換後的數
int bmul[MAX+10];
int product[result+10];//存儲乘積
void interger(char *source, int *target, int length)
{
int i = length-1;
int index = 0;
for (; index < length; index++, i--)
{
//將數字字符轉換為整數，下標0、1、2分別為個、十、百位
target[index] = source[i] - '0';
}
}
int main()
{
int i, j;
cin >> a >> b;
if (!strcmp(a, "0") || !strcmp(a, "0"))
{
cout << "0" << endl;
return 0;
}
//將char轉換為int
interger(a, amul, strlen(a));
interger(b, bmul, strlen(b));
//相乘不進位
for (i = 0; i < strlen(b); i++)
{
for (j = 0; j < strlen(a); j++)
{
//疊加到原來的位置的數上面
product[i+j] += bmul[i] * amul[j];
}
}
//進位
for (i = 0; i < result; i++)
{
if (product[i] >= 10)
{
product[i + 1] += product[i] / 10;
product[i] = product[i] % 10;;
}
}
//把前導零去掉
int k = result-1;
while (product[k] == 0)
{
k--;
}
//倒序輸出
for (; k >= 0; k--)
{
cout << product[k];
}
cout << endl;
return 0;
}
(後續會嘗試優化或增加不同的解法)
