Thứ Hai, 5 tháng 3, 2012

Các phép tính với số nguyên lớn & mã nguồn C++


Cộng, trừ, nhân, chia số nguyên lớn, mã nguồn C++
#include <iostream>
#include <string.h>
using namespace std;
#define MAXLEN 1000

struct SNL
{
    char sign;//dấu, nếu số âm thì sign=-1
    char len;//chiều dài
    char num[MAXLEN];//lưu các chữ số
};

void initSNL(SNL &n);//Khởi tạo số nguyên lớn
void str2snl(char *str, SNL &n);//Chuyển một chuỗi kí tự thành số nguyên lớn
void scanSNL(SNL &n);//Đọc số nguyên lớn từ bàn phím
void printSNL(SNL &n);//In số nguyên lớn ra màn hình
int cmpu(SNL &a, SNL &b);//So sánh 2 số nguyên lớn không xét dấu
int cmp(SNL &a, SNL &b);//So sánh 2 số nguyên lớn, nếu a>b trả về 1, a=b trả về 0, a<b trả về -1
void addu(SNL &s, SNL &a, SNL &b);//Cộng không xét dấu
void add(SNL &s, SNL &a, SNL &b);//Cộng có xét dấu
void subu(SNL &s, SNL &a, SNL &b);//Trừ không xét dấu
void sub(SNL &s, SNL &a, SNL &b);//Trừ có xét dấu
void mul(SNL &r, SNL &a, SNL &b);//Nhân hai số nguyên lớn
void div(SNL &r, SNL a, SNL b);//Phép chia số nguyên lớn

void InitSNL(SNL &n)
{
    for (int i=0; i<MAXLEN; i++) n.num[i]=0;
    n.len=0;
    n.sign=1;
}
void str2snl(char *str, SNL &n)
{
    int i;
    if (str[0]=='-')
    {
        n.sign=-1;
        str++; //bỏ qua kí tự đầu tiên
    }
    else
        n.sign=1;

    while (str[0] == '0') ++str; //bỏ qua các chữ số 0 ở đầu

    n.len=strlen(str);//Chiều dài (số chữ số) của số nguyên lớn

    for (i=0; i<n.len; i++)
        n.num[i]=str[n.len-i-1]-'0';//Chuyển từng kí tự thành số
}

int cmpu(SNL &a, SNL &b)
{

    if (a.len>b.len)//Số nào dài hơn thì số đó lớn hơn
        return 1;
    else if (a.len<b.len)
        return -1;
    else//Trường hợp chiều dài 2 số bằng nhau
    {
        int len=a.len-1;
        while (len>=0)
        {
            //So sánh từ chữ số
            if (a.num[len]>b.num[len])
                return 1;
            else if (a.num[len]<b.num[len])
                return -1;
            else
                len--;
        }
    }
    return 0;
}

int cmp(SNL &a, SNL &b)
{
    if (a.sign * b.sign<0) return a.sign;
    return a.sign * cmpu(a,b);
}

void scanSNL(SNL &n)//Đọc SNL từ bàn phím
{
    char *t=new char[MAXLEN];
    cin>>t;
    str2snl(t,n);
    delete []t;
}

void printSNL(SNL &n)
{
    if (n.len > 0)
    {
        if (n.sign<0) cout<<"-";
        for (int i=n.len-1; i>=0; i--) cout<<(int)n.num[i];
    }
    else
        cout << 0;
}

void addu(SNL &s, SNL &a, SNL &b)
{
    InitSNL(s);
    s.len=a.len>b.len?a.len:b.len;
    char m=0;//biến nhớ
    for (int i=0; i<s.len; i++)
    {
        s.num[i]=a.num[i]+b.num[i]+m;
        if (s.num[i]>9)
        {
            s.num[i] -= 10;
            m=1;
        }
        else
            m=0;
    }
    if (m)
    {
        s.num[s.len]=1;
        s.len++;
    }
}

void add(SNL &s, SNL &a, SNL &b)
{
    if (a.sign*b.sign>0)//Nếu a và b cùng dấu
    {
        addu(s,a,b);
        s.sign=a.sign;//Dấu của s cũng là dấu của a hoặc b
    }
    else
    {
        int t=cmpu(a,b);
        if (t==1)
        {
            subu(s,a,b);
            s.sign=a.sign;
        }
        else if (t==-1)
        {
            subu(s,b,a);
            s.sign=b.sign;
        }
        else
            InitSNL(s);

    }
}

void subu(SNL &r, SNL &a, SNL &b)
{
    InitSNL(r);
    r.len=a.len>b.len?a.len:b.len;
    int m=0;
    for (int i=0; i<r.len; i++)
    {
        if (a.num[i]<b.num[i]+m)
        {
            r.num[i]=10+a.num[i]-b.num[i]-m;
            m=1;
        }
        else
        {
            r.num[i]=a.num[i]-b.num[i]-m;
            m=0;
        }
    }
    while (r.num[r.len-1]==0) r.len--;
}

void sub(SNL &r, SNL &a, SNL &b)
{
    b.sign=-b.sign;
    add(r,a,b);
    b.sign=-b.sign;
}

void mul(SNL &r, SNL &a, SNL &b)
{
    InitSNL(r);
    for (int i=0; i<b.len; i++)
        for (int j=0; j<b.num[i]; j++)
            for (int k=0; k<a.len; k++)
            {
                r.num[k+i] += a.num[k];
                if (r.num[k+i]>9)
                {
                    r.num[k+i] -= 10;
                    r.num[k+i+1]++;
                }
            }
            r.len=a.len+b.len;
            while (r.num[r.len-1]==0) r.len--;
            r.sign=a.sign*b.sign;
}

void div(SNL &r, SNL a, SNL b)
{
    InitSNL(r);
    r.len=a.len-b.len+1;
    if (a.len>=b.len)
    {
        int blen=b.len;
        int i;
        if (a.len>b.len)
        {
            i=a.len-1;
            int x=a.len-b.len;
            while (i>=0)
            {
                if (i>=x)
                    b.num[i]=b.num[i-x];
                else
                    b.num[i]=0;
                i--;
            }
        }
        b.len=a.len;
        SNL d;
        i=1;
        while (b.len>=blen)
        {
            while (cmpu(a,b)>-1)
            {
                subu(d,a,b);
                r.num[r.len-i]++;
                a=d;
            }
            b.len--;
            i++;
            for (int k=0; k<b.len; k++) b.num[k]=b.num[k+1];
            b.num[b.len]=0;
        }
        while (r.num[r.len-1]==0) r.len--;
    }
    r.sign=a.sign*b.sign;
}

int main()
{
    SNL a,b,c;
    InitSNL(a);
    InitSNL(b);
    InitSNL(c);

    cout<<"Nhap so nguyen a: "; scanSNL(a);
    cout<<"Nhap so nguyen b: "; scanSNL(b);

    add(c,a,b);
    cout<<endl<<"a + b = "; printSNL(c);
    sub(c,a,b);
    cout<<endl<<"a - b = "; printSNL(c);

    mul(c,a,b);
    cout<<endl<<"a * b = "; printSNL(c);

    div(c,a,b);
    cout<<endl<<"a / b = "; printSNL(c);

    cout<<endl;
    system("pause");
    return 0;
}

Mã nguồn hướng đối tượng trên ngôn ngữ C++ – tải về (VC++ project)
Lớp Số nguyên lớn – class BigInt
  • 3 phương thức khởi tạo: không tham số, tham số nguyên, tham số mảng kí tự.
  • 3 định nghĩa toán tử gán =, hỗ trợ chuyển đổi từ kiểu số nguyên, mảng kí tự.
  • 5 toán tử 2 ngôi: + – * / %
  • 4 toán tử 1 ngôi: ++ trước/sau, — trước/sau;
  • 6 toán tử so sánh: ==, !=, <, >, <=, >=
  • 2 toán tử nhập xuất với iostream: <<, >>
Tập tin BigInt.h
//(c) http://kithuatlaptrinh.tk

#ifndef _BIG_INT_H
#define _BIG_INT_H

#include <iostream>
#include <string.h>
using namespace std;
#define MAXLEN 100

class BigInt
{
    char sign;
    char len;
    char num[MAXLEN];

    friend istream& operator >> (istream&, BigInt&);
    friend ostream& operator << (ostream&, BigInt&);

    void init();
    int cmpu(const BigInt&) const;
    int cmp(const BigInt&) const;
    BigInt& addu(const BigInt&, BigInt&) const;
    BigInt& subu(const BigInt&, BigInt&) const;

public:

    istream& read(istream&);
    ostream& write(ostream&);

    void getSz(const char*);
    void getInt(int);

    BigInt();
    BigInt(int);
    BigInt(const char*);

    BigInt& operator = (const BigInt&);
    BigInt& operator = (const char*);
    BigInt& operator = (int);

    bool operator == (const BigInt&) const;
    bool operator != (const BigInt&) const;
    bool operator < (const BigInt&) const;
    bool operator >= (const BigInt&) const;
    bool operator > (const BigInt&) const;
    bool operator <= (const BigInt&) const;

    BigInt operator + (const BigInt&) const;
    BigInt operator - (const BigInt&) const;
    BigInt operator * (const BigInt&) const;
    BigInt operator / (const BigInt&) const;
    BigInt operator % (const BigInt&) const;

    BigInt operator - () const;
    BigInt& operator ++ ();
    BigInt operator ++ (int);
    BigInt& operator -- ();
    BigInt operator -- (int);

    ~BigInt();
};

#endif
Tập tin BigInt.cpp
//(c) http://kithuatlaptrinh.tk

#include "BigInt.h"

istream& operator >> (istream& inDev, BigInt& n)
{
    return n.read(inDev);
}

ostream& operator << (ostream& outDev, BigInt& n)
{
    return n.write(outDev);
}

istream& BigInt::read(istream& inDev)
{
    char *strTemp = new char[MAXLEN];
    inDev >> strTemp;
    getSz(strTemp);
    delete []strTemp;
    return inDev;
}

void BigInt::getInt(int n)
{
    char strTemp[10];
    _itoa_s(n, strTemp, 10);
    getSz(strTemp);
}

void BigInt::getSz(const char* str)
{
    init();
    if (str[0] == '-')
    {
        sign = -1;
        ++str;
    }
    else
        sign = 1;

    while (str[0] == '0') ++str;

    len = strlen(str);

    for (int i = 0; i < len; ++i)
        num[i] = str[len - i - 1] - '0';
}

ostream& BigInt::write(ostream& outDev)
{
    if (len > 0)
    {
        if (sign < 0) outDev << "-";
        for (int i = len - 1; i >= 0; --i) outDev << (int)num[i];
    }
    else
        outDev << 0;

    return outDev;
}

void BigInt::init()
{
    sign = 1;
    len = 0;
    for (int i = 0; i < MAXLEN; ++i) num[i] = 0;
}

BigInt::BigInt()
{
    init();
}

BigInt::BigInt(int n)
{
    getInt(n);
}

BigInt::BigInt(const char* str)
{
    getSz(str);
}

BigInt& BigInt::operator = (const BigInt& n)
{
    len = n.len;
    sign = n.sign;
    for (int i = len - 1; i >=0; --i) num[i] = n.num[i];
    return *this;
}

BigInt& BigInt::operator = (const char* str)
{
    getSz(str);
    return *this;
}

BigInt& BigInt::operator = (int n)
{
    getInt(n);
    return *this;
}

int BigInt::cmpu(const BigInt &n) const
{
    if (len > n.len)
        return 1;
    else if (len < n.len)
        return -1;
    else
    {
        int t = len - 1;
        while (t >= 0)
        {
            if (num[t] > n.num[t])
                return 1;
            else if (num[t] < n.num[t])
                return -1;
            else
                --t;
        }
    }
    return 0;
}

int BigInt::cmp(const BigInt &n) const
{
    if (sign * n.sign < 0) return sign;
    return sign * cmpu(n);
}

bool BigInt::operator == (const BigInt& n) const
{
    return cmp(n) == 0;
}

bool BigInt::operator != (const BigInt& n) const
{
    return cmp(n) != 0;
}

bool BigInt::operator < (const BigInt& n) const
{
    return cmp(n) < 0;
}

bool BigInt::operator >= (const BigInt& n) const
{
    return cmp(n) >= 0;
}

bool BigInt::operator > (const BigInt& n) const
{
    return cmp(n) > 0;
}

bool BigInt::operator <= (const BigInt& n) const
{
    return cmp(n) <= 0;
}

BigInt& BigInt::addu(const BigInt& n, BigInt& r) const
{
    r.len = len > n.len ? len : n.len;
    char m = 0;
    for (int i = 0; i < r.len; ++i)
    {
        r.num[i] = num[i] + n.num[i] + m;
        if (r.num[i] > 9)
        {
            r.num[i] -= 10;
            m = 1;
        }
        else
            m = 0;
    }
    if (m)
    {
        r.num[r.len] = 1;
        r.len++;
    }
    return r;
}

BigInt& BigInt::subu(const BigInt& n, BigInt& r) const
{
    r.len = len > n.len ? len : n.len;
    int m = 0;
    for (int i = 0; i < r.len; ++i)
    {
        if (num[i] < n.num[i] + m)
        {
            r.num[i] = 10 + num[i] - n.num[i] - m;
            m = 1;
        }
        else
        {
            r.num[i] = num[i] - n.num[i] - m;
            m = 0;
        }
    }
    while (r.num[r.len - 1] == 0) --r.len;

    return r;
}

BigInt BigInt::operator + (const BigInt& n) const
{
    BigInt r;
    if (sign * n.sign > 0)
    {
        addu(n, r);
        r.sign = sign;
    }
    else
    {
        int cr = cmpu(n);
        if (cr == 1)
        {
            subu(n, r);
            r.sign=sign;
        }
        else if (cr == -1)
        {
            n.subu(*this, r);
            r.sign = n.sign;
        }
    }
    return r;
}

BigInt BigInt::operator - (const BigInt& n) const
{
    BigInt r, _n = -n;
    r = *this + _n;
    return r;
}

BigInt BigInt::operator * (const BigInt& n) const
{
    BigInt r;

    for (int i = 0; i < n.len; ++i)
        for (int j = 0; j < n.num[i]; ++j)
            for (int k = 0; k < len; ++k)
            {
                r.num[k + i] += num[k];
                if (r.num[k + i] > 9)
                {
                    r.num[k + i] -= 10;
                    ++r.num[k + i + 1];
                }
            };
    r.len = len + n.len;
    while (r.num[r.len-1] == 0) --r.len;
    r.sign = sign * n.sign;

    return r;
}

BigInt BigInt::operator / (const BigInt& n) const
{
    BigInt r, b = n;
    r.len = len - n.len + 1;
    if (len >= b.len)
    {
        int bLen = b.len;
        int i;

        if (len > bLen) //Them so 0 vao cuoi so b de chieu dai so b bang chieu dai so bi chia
        {
            i = len - 1;
            int x = len - bLen;
            while (i >= 0)
            {
                if (i >= x)
                    b.num[i] = b.num[i - x];
                else
                    b.num[i] = 0;
                --i;
            }
        }

        b.len = len;

        BigInt c, a = *this;
        i = 1;
        while (b.len >= bLen)
        {
            while (a.cmpu(b) > -1) //while so bi chia > so chia
            {
                a = a.subu(b, c);
                ++r.num[r.len-i];
            }
            --b.len;
            ++i;
            for (int k = 0; k < b.len; ++k) b.num[k] = b.num[k + 1];
            b.num[b.len] = 0;
        }

        while (r.num[r.len - 1] == 0) --r.len;
    }
    r.sign = sign * n.sign;

    return r;
}

BigInt BigInt::operator % (const BigInt& n) const
{
    return *this - (*this / n) * n;
}

BigInt BigInt::operator - () const
{
    BigInt r = *this;
    r.sign = -r.sign;
    return r;
}

BigInt& BigInt::operator ++ ()
{
    *this = *this + 1;
    return *this;
}

BigInt BigInt::operator ++ (int)
{
    BigInt t = *this;
    ++*this;
    return t;
}

BigInt& BigInt::operator -- ()
{
    *this = *this - 1;
    return *this;
}

BigInt BigInt::operator -- (int)
{
    BigInt t = *this;
    --*this;
    return t;
}

BigInt::~BigInt()
{

}
Demo: tập tin main.cpp
#include <iostream>
#include "BigInt.h"
using namespace std;

int main()
{
    BigInt a = "123456789123456789", b = 123456;

    cout << "a = " << a << endl;
    cout << "b = " << b << endl;

    cout << "Nhap a: "; cin >> a;
    cout << "Nhap b: "; cin >> b;

    cout << "a + b = " << a + b << endl;
    cout << "a - b = " << a - b << endl;
    cout << "a * b = " << a * b << endl;
    cout << "a / b = " << a / b << endl;
    cout << "a % b = " << a % b << endl;

    cout << a++ << endl;
    cout << a-- << endl;
    cout << ++a << endl;
    cout << --a << endl;

    return 0;
}

Bài viết liên quan:
Người đăng: 0 nhận xét
Nhãn:
Share this post
  • Share to Facebook
  • Share to Twitter
  • Share to Google+
  • Share to Stumble Upon
  • Share to Evernote
  • Share to Blogger
  • Share to Email
  • Share to Yahoo Messenger
  • More...

0 nhận xét

:) :-) :)) =)) :( :-( :(( :d :-d @-) :p :o :>) (o) [-( :-? (p) :-s (m) 8-) :-t :-b b-( :-# =p~ :-$ (b) (f) x-) (k) (h) (c) cheer

 
© Download do an khoa luan tai lieu
Designed by BlogThietKe Cooperated with Duy Pham
Released under Creative Commons 3.0 CC BY-NC 3.0
Posts RSS ∙ Comments RSS
Back to top