学步园

/*
求1234567891011121314151617181920*2019181716151413121110987654321的值. 
用数组去做,把第1个大数和第2个大数分别用数组表示. 格式举例如下:
9 8 7 6 5 4 3 2 1 0 <----------代表数组的位
-------------------
        7 8 9 6 5 2
            3 2 1 1 *
-------------------
        7 8 9 6 5 2 <-----------第1趟 
      7 8 9 6 5 2   <-----------第2趟 
     ..........     <-----------第n趟 
-------------------
  ? ? ? ? ? ? ? ? ? <-----------最后的值用另一个数组表示 
*/
 
#include <iostream>
using namespace std;

void print(int a[], int len);
void multiply(int a[], int aLen, int b[], int bLen, int ans[], int ansLen);

int main()
{
    int iArr1[] = {0,2,9,1,8,1,7,1,6,1,5,1,4,1,3,1,2,1,1,1,0,1,9,8,7,6,5,4,3,2,1};
    int iArr2[] = {1,2,3,4,5,6,7,8,9,0,1,1,1,2,1,3,1,4,1,5,1,6,1,7,1,8,1,9,1,0,2};
    int iLen1 = sizeof(iArr1) / sizeof(int);
    int iLen2 = sizeof(iArr2) / sizeof(int);
    int ansLen = iLen1 + iLen2;
    int *ansArr = new int [ansLen];
    int i;
    
    for (i = 0; i < ansLen; i++)
        ansArr[i] = 0;
    
    print(iArr1, iLen1);
    cout << " * ";
    print(iArr2, iLen2);
    cout << " = \n";
    multiply(iArr1, iLen1, iArr2, iLen2, ansArr, ansLen);
    
    print(ansArr, ansLen);    
    delete [] ansArr;
	cout << "\n\n\n";
    system("PAUSE");
    return 0;
}

void print(int a[], int len)
{
    int i;
    i = len - 1;
    while( 0 == a[i])
        --i;
    while( i >= 0 )
        printf("%d", a[i--]);
}

void multiply(int a[], int aLen, int b[], int bLen, int ans[], int ansLen)
{
    int i, j, minLen, tmp, inc;
    int *shortarr, *longarr;
    if (aLen < bLen)
    {
        shortarr = a;
        longarr = b;
        minLen = aLen;
    }
    else
    {
        shortarr = b;
        longarr = a;
        minLen = bLen;
    }
    
    for (i = 0; i < minLen; i++) //共minLen趟
    {
        for (j = 0; j < aLen + bLen - minLen; j++)
        {
            tmp = shortarr[i] * longarr[j];
            ans[i + j] += tmp;
        }
    }
    
    //处理进位
    for (i = 0; i < ansLen; i++)
    {
        tmp = ans[i] / 10;
        ans[i] %= 10;
        ans[i + 1] += tmp;
    }
    
}
/*
输出结果:
1234567891011121314151617181920 * 2019181716151413121110987654321 =
2492816912877266687794240983772975935013386905490061131076320     
*/