2014-06-01 18:03:30

题意 & 思路:大数乘,这里采用的小白书里的bign结构体

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 1000;

struct bign{
    int len,s[maxn + 5];

    bign(){
        memset(s,0,sizeof(s));
        len = 1;//因为0的存在
    }

    bign operator = (const char *num){
        len = strlen(num);
        for(int i = 0; i < len; ++i)
            s[i] = num[len - i - 1] - \'0\';//倒序转化成数字
        return *this;
    }

    bign operator = (int num){
        char ts[maxn + 5];
        sprintf(ts,"%d",num);
        *this = ts;
        return *this;
    }

    bign(int num){
        *this = num;
    }

    bign(const char *num){
        *this = num;
    }
    //bign的str型转化
    string str() const{
        string res = "";
        for(int i = len - 1; i >= 0; --i)
            res +=  (char)(s[i] + \'0\');
        if(res == "")
            res = "0";
        return res;
    }
    //高精度加
    bign operator + (const bign & b) const{
        bign sum;//保存结果的bign
        sum.len = 0;
        for(int i = 0, g = 0; g || i < max(len,b.len); ++i){
            int x = g;//x:暂存和,g:进位
            if(i < len) x += s[i];
            if(i < b.len) x += b.s[i];
            sum.s[sum.len++] = x % 10;
            g = x / 10;
        }
        return sum;
    }
    //高精度乘,实际上加和乘对进位的处理有所不同,比较喜欢乘的
    bign operator * (const bign &b) const{
        bign pro;
        pro.len = 0;
        for(int i = 0; i < len; ++i){
            for(int j = 0; j < b.len; ++j){
                pro.s[i + j] += (s[i] * b.s[j]);
                pro.s[i + j + 1] += pro.s[i + j] / 10;
                pro.s[i + j] %= 10;
            }
        }
        pro.len = len + b.len + 1;//这里注意pro.len初始值可能是题目数字范围两倍
        while(pro.s[pro.len - 1] == 0 && pro.len > 1)
            --pro.len;//最后一位不管是不是0都不能让len - 1
        if(pro.s[pro.len])
            ++pro.len;//这句有待商讨
        return pro;
    }
    //额外加的+=重载
    bign operator += (const bign & b){
        *this = *this + b;
        return *this;
    }

    //额外的比较运算符重载
    bool operator < (const bign & b) const{
        if(len != b.len) return len < b.len;
        for(int i = len - 1; i >= 0; --i)//从高位开始比较
            if(s[i] != b.s[i])
                return s[i] < b.s[i];
        //如果 本身 == b
        return false;
    }

    bool operator > (const bign &b) const{
        return b < *this;//代表 本身 > b
    }

    bool operator <= (const bign &b) const{
        return !(b < *this);//带表 !(本身 > b)
    }

    bool operator >= (const bign &b) const{
        return !(*this < b);
    }

    bool operator != (const bign &b) const{
        return *this < b || b < *this;
    }

    bool operator == (const bign &b) const{
        return !(*this < b) && !(b < *this);
    }
    friend istream & operator >> (istream & in,bign & x);
    friend ostream & operator << (ostream & out,const bign & x);
};

istream & operator >> (istream & in,bign & x){
    string ts;
    in >> ts;
    x = ts.c_str();
    return in;
}

ostream & operator << (ostream & out,const bign & x){
    out << x.str();
    return out;
}
int main(){
    char st1[maxn + 5],st2[maxn + 5];
    bign n1,n2;
    while(scanf("%s%s",st1,st2) == 2){
        n1 = st1;
        n2 = st2;
        cout << n1 * n2 << endl;
    }
    return 0;
}

 

版权声明:本文为naturepengchen原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/naturepengchen/articles/3763583.html