加载中...

POJ 2389 - Bull Math

算法

原创

发布日期: 2011-06-20

更新日期: 2024-11-17

文章字数: 380

阅读时长: 2 分

阅读次数:

POJ 2389 - Bull Math
Time: 1000MS
Memory: 10000K
难度: 初级
分类: 高精度算法

问题描述

无。

解题思路

大数相乘，水题一道，直接模拟笔算竖式即可，没技巧没算法。

AC 源码

//Memory Time
//216K  16MS 

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

const int size=1000;  //大数位数

void mult(char* A,char* B,char* ans)
{
    int a[size+1]={0};
    int b[size+1]={0};
    int pa=0,pb=0;
    int c[2*size+1]={0};

    int lena=strlen(A);
    int lenb=strlen(B);

    for(int i=lena-1;i>=0;i--)
        a[pa++]=A[i]-'0';
    for(int j=lenb-1;j>=0;j--)
        b[pb++]=B[j]-'0';

    for(pb=0;pb<lenb;pb++)
    {
        int w=0;  //低位到高位的进位
        for(pa=0;pa<=lena;pa++)
        {
            int temp=a[pa]*b[pb]+w;
            w=temp/10;
            temp=(c[pa+pb]+=temp%10);
            c[pa+pb]=temp%10;
            w+=temp/10;
        }
    }
    bool flag=false;
    bool sign=false;  //标记ans是否为全0
    for(pa=0,pb=lena+lenb-1;pb>=0;pb--)
    {
        if(!flag && c[pb]==0)  //删除ans开头的0
            continue;
        else
            flag=true;

        sign=true;
        ans[pa++]=c[pb]+'0';
    }
    if(sign)
        ans[pa]='\0';
    else
    {
        ans[0]='0';
        ans[1]='\0';
    }

    return;
}

int main(void)
{
    char a[size+1];
    char b[size+1];
    char ans[2*size+1];
    while(cin>>a>>b)
    {
        mult(a,b,ans);
        cout<<ans<<endl;
    }
    return 0;
}