2 条题解

  • 4
    @ 2020-03-10 22:47:13

    此处摘录较好同学答案

    @陈朝

    几乎所有同学没有重定义比较运算符?

    //陈朝 201930390029
    // 头文件 HugeInt.h
    #ifndef HUGEINT_H
    #define HUGEINT_H
    #include<iostream>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    using namespace std;
    class HugeInt
    {
        private:
            int digit[100];
            int len;
        public:
            HugeInt();
            friend HugeInt operator+(const HugeInt&,const HugeInt&);
            friend HugeInt operator-(const HugeInt&,const HugeInt&);
            friend HugeInt operator*(const HugeInt&,const HugeInt&);
            friend istream &operator>>(istream&,HugeInt&);
            friend ostream &operator<<(ostream&,const HugeInt&);
    };
    #endif 
    
    //实现文件 HugeInt.cpp
    /*
    #include<bits/stdc++.h>
    #include"HugeInt.h"
    */
    HugeInt::HugeInt()
    {
        for(int i=0;i<100;++i)digit[i]=0;
        len=0;
    }
    istream &operator>>(istream&input,HugeInt&a)
    {
        char s[100];
        input>>s;
        a.len=strlen(s);
        for(int i=a.len-1;i>=0;--i)
            a.digit[i]=s[a.len-i-1]-'0';
        //digit低位为数量级小 
        return input;
    }
    ostream &operator<<(ostream&op,const HugeInt&a)
    {
        for(int i=a.len-1;i>=0;--i)
            op<<a.digit[i];
        return op;
    }
    HugeInt operator+(const HugeInt&a,const HugeInt&b)
    {
        HugeInt c;
        for(int i=0;i<a.len;++i)
        {
            c.digit[i]+=(a.digit[i]+b.digit[i]);
            if(c.digit[i]>=10) c.digit[i]%=10,c.digit[i+1]++;
        }
        if(c.digit[a.len]>0) 
            c.len=a.len+1;
        else c.len=a.len;
        return c;
    }
    HugeInt operator-(const HugeInt&a,const HugeInt&b)
    {
        HugeInt c;
        int l1=0;
        for(int i=0;i<a.len;++i)
        {
            c.digit[i]+=(a.digit[i]-b.digit[i]);
            if(c.digit[i]<0) c.digit[i]=10+c.digit[i],c.digit[i+1]--;
        }
        for(int i=a.len-1;i>=0;--i) 
        {
            if(c.digit[i]==0) l1++;
            else break;
        }
        c.len=a.len-l1;
        return c;
    }
    HugeInt operator*(const HugeInt&a,const HugeInt&b)
    {
        int l1=a.len;
        HugeInt c;
        for(int i=0;i<a.len;++i)
        {
            for(int j=0;j<b.len;++j)
            {
                c.digit[i+j]+=(a.digit[i]*b.digit[j]);
                if(c.digit[i+j]>=10)
                    c.digit[i+j+1]+=c.digit[i+j]/10, 
                    c.digit[i+j]%=10;
            }
        }
        if(c.digit[a.len+b.len-1]) c.len=a.len+b.len;
        else c.len=a.len+b.len-1;
        return c;
    }
    
    //主程序 main.cpp
    /*
    #include<bits/stdc++.h>
    #include"HugeInt.h"
    */ 
    int main()
    {
        HugeInt a,b;
        cin>>a;
        cin>>b;
        cout<<a+b<<endl
            <<a-b<<endl
            <<a*b;
        return 0;
    }
    
  • 0
    @ 2020-03-10 22:53:52

    我的高精度模版

    想了解的同学可以拿回去研究

    使用vector进行储存以灵活利用空间和避免溢出

    //万进制高精度模版
    //负数支持
    #include<iostream>
    #include<algorithm>
    #include<vector>
    #include<cmath>
    #include<string>
    #include<cstdio>
    #include<cstring>
    #include<iomanip>
    #include<sstream>
    using namespace std;
    const int mod = 10000;
    const int digs = 4;
    typedef int typ;//低精类型
    class bignum
    {
    private:
        vector<int> v;//储存值
        int len;//长度
        int flag;//1表示负数
    public:
        bignum();
        bignum(typ);
        bignum(const char*);
        bignum(string);
    
        bignum operator +(bignum);
        bignum operator -(bignum);
        bignum operator -();
        bignum operator *(bignum);
        bignum operator /(typ);
        bignum operator %(typ);
    
        //比较运算实现>和==
    
        bool operator >(bignum);
        bool operator >=(bignum);
        bool operator <(bignum);
        bool operator <=(bignum);
        bool operator ==(bignum);
        bool operator !=(bignum);
    
        bignum& operator=(bignum);
        bignum& operator +=(bignum);
        bignum& operator -=(bignum);
        bignum& operator *=(bignum);
        bignum& operator /=(typ);
        bignum& operator %=(typ);
    
        bignum getdiv(typ, typ&);
        void print();
        void clean();//去除前导0
        string ToString();
        const char* str();
    
        friend istream& operator>>(istream&, bignum&);
        friend ostream& operator<<(ostream&, bignum);
    };
    
    bignum::bignum()
    {
        v.clear();
        len = 0;
        flag = 0;
    }
    
    bignum::bignum(typ val) :bignum()
    {
        if (val == 0) {
            v.push_back(0);
            len = 1;
        }
        if (val < 0) {
            flag = 1;
            val = -val;
        }
        while (val) {
            v.push_back(val % mod);
            val /= mod;
        }
        len = v.size();
    }
    
    bignum::bignum(const char* s) :bignum()
    {
        if (s[0] == '-') flag = 1;
        else flag = 0;
        v.clear();
        int p = 0;
        int i, j;
        int le = strlen(s);
        for (i = flag; i < le; i++) {
            p = p * 10 + s[i] - '0';
            if ((le - i - 1) % digs == 0) {
                v.push_back(p);
                p = 0;
            }
        }
        len = v.size();
        i = 0; j = len - 1;
        while (i < j) {
            swap(v[i], v[j]);
            i++; j--;
        }
    }
    
    bignum::bignum(string str) :bignum(str.c_str())
    {
        //empty body
    }
    
    bignum bignum::operator+(bignum x)
    {
        if (flag ^ x.flag) {
            x.flag ^= 1;
            return *this - x;
        }
        bignum res;
        int l = min(len, x.len);
        int xx = 0;
        for (int i = 0; i < l; i++)
        {
            xx+=x.v[i] + v[i];
            res.v.push_back(xx % mod);
            xx /= mod;
        }
        bignum& p = len > x.len ? *this : x;
        for (int i = l; i < p.len; i++)
        {
            xx += p.v[i];
            res.v.push_back(xx % mod);
            xx /= mod;
        }
        if (xx) res.v.push_back(xx);
        res.len = res.v.size();
        res.flag = flag;
        return res;
    }
    
    bignum bignum::operator-(bignum x)
    {
        if (flag ^ x.flag) {
            x.flag ^= 1;
            return *this + x;
        }
        bignum res = *this;
        int i;
        for (i = 0; i < x.len; i++)
        {
            if (i < len) res.v[i] -= x.v[i];
            else res.v.push_back(-x.v[i]);
        }
        res.len = res.v.size();
        if (res.v[res.len - 1] < 0) {
            res.flag ^= 1;
            for (i = 0; i < res.len;i++) {
                res.v[i] = -res.v[i];
            }
        }
        for (i = res.len - 1; i > 0; i--) {
            if (res.v[i - 1] < 0) {
                res.v[i]--;
                res.v[i - 1] += mod;
            }
        }
        res.clean();
        return res;
    }
    
    bignum bignum::operator-()
    {
        bignum res = *this;
        res.flag ^= 1;
        return res;
    }
    
    bignum bignum::operator*(bignum x)
    {
        int i, j, xx = 0;
        bignum res;
        res.len = len + x.len;
        for (i = 0; i < res.len; i++) res.v.push_back(0);
        for (i = 0; i < len; i++) for (j = 0; j < x.len; j++) {
            res.v[i + j] += v[i] * x.v[j];
            if (res.v[i + j] > mod) {
                res.v[i + j + 1] += res.v[i + j] / mod;
                res.v[i + j] %= mod;
            }
        }
        for (i = 0; i < res.len - 1; i++) {
            res.v[i + 1] += res.v[i] / mod;
            res.v[i] %= mod;
        }
        res.clean();
        res.flag = flag ^ x.flag;
        return res;
    }
    
    bignum bignum::operator/(typ x)
    {
        typ md;
        return this->getdiv(x, md);
    }
    
    bignum bignum::operator%(typ x)
    {
        typ res;
        getdiv(x, res);
        return bignum(res);
    }
    
    bool bignum::operator>(bignum x)
    {
        if (flag ^ x.flag) return flag ^ 1;
        if (len > x.len) return flag ^ 1;
        if (len < x.len) return flag;
        int i;
        for (i = len - 1; i >= 0; i--) {
            if (v[i] != x.v[i]) return flag ^ (v[i] > x.v[i]);
        }
        return false;
    }
    
    bool bignum::operator==(bignum x)
    {
        if (flag ^ x.flag) return false;
        if (len != x.len) return false;
        int i;
        for (i = 0; i < len; i++) if (v[i] != x.v[i]) return false;
        return true;
    }
    
    bool bignum::operator>=(bignum x)
    {
        return *this > x || *this == x;
    }
    
    bool bignum::operator<(bignum x)
    {
        return x > *this;
    }
    
    bool bignum::operator<=(bignum x)
    {
        return x >= * this;
    }
    
    bool bignum::operator!=(bignum x)
    {
        return !(*this == x);
    }
    
    bignum& bignum::operator=(bignum x)
    {
        len = x.len;
        flag = x.flag;
        v = x.v;
        return *this;
    }
    
    bignum& bignum::operator+=(bignum x)
    {
        *this = *this + x;
        return *this;
    }
    
    bignum& bignum::operator-=(bignum x)
    {
        *this = *this - x;
        return *this;
    }
    
    bignum& bignum::operator*=(bignum x)
    {
        *this = *this * x;
        return *this;
    }
    
    bignum& bignum::operator/=(typ x)
    {
        *this = *this / x;
        return *this;
    }
    
    bignum& bignum::operator%=(typ x)
    {
        *this = *this % x;
        return *this;
    }
    
    bignum bignum::getdiv(typ x, typ& mod_dest)
    {
        int p = 0,i;
        int fl = 0;
        bignum res;
        for (i = len - 1; i >= 0; i--) {
            p = p * mod + v[i];
            if (p > x) {
                if (!fl) {
                    res.len = i + 1;
                    for (int j = 0; j < res.len; j++) res.v.push_back(0);
                    fl = 1;
                }
                res.v[i] = p / x;
                p %= x;
            }
        }
        res.flag = (x < 0 ? 1 : 0) ^ flag;
        mod_dest = p;
        return res;
    }
    
    void bignum::print()
    {
        int i;
        if (flag) cout<<'-';
        cout << v[len - 1];
        for (i = len - 2; i >= 0; i--) cout << setfill('0') << setw(digs) << v[i];
    }
    
    void bignum::clean()
    {
        while (v[len - 1] == 0) len--, v.pop_back();
    }
    
    string bignum::ToString()
    {
        string res;
        stringstream ss;
        if(flag) res.push_back('-');
        for (int i = len - 1; i >= 0; i--)
        {
            ss.str("");
            ss << setw(digs) << setfill('0') << v[i];
            res += ss.str();
            
        }
        return res;
    }
    
    const char* bignum::str()
    {
        string s = ToString();
        return s.c_str();
    }
    
    istream& operator>>(istream& c, bignum& x)
    {
        string s;
        c >> s;
        x = bignum(s);
        return c;
    }
    
    ostream& operator<<(ostream& c, bignum x)
    {
        x.print();
        return c;
    }
    
    int main() {
        bignum a, b;
        cin >> a >> b;
        cout << a + b << endl;
        cout << a - b << endl;
        cout << a * b << endl;
    }
    
  • 1

信息

ID
1002
难度
4
分类
高精度 点击显示
标签
递交数
165
已通过
32
通过率
19%
上传者