Thao tác số nguyên lớn - Trình bày thuật toán

  • In C#
  • Tuesday, August 09, 2016
  • 1221 Views

Dùng xâu ký tự để diễn số nguyên lớn với cấu trúc như sau: Các chữ số được viết theo chiều ngược lại. Nếu số nguyên có n chữ số thì xâu tương ứng có n+2 byte (phía cuối thêm 2 byte, byte thứ nhất chứa dấu '-' nếu đó là số âm, hoặc null nếu số dương, byte cuối cùng là null)

Dùng xâu ký tự để diễn số nguyên lớn với cấu trúc như sau:

Các chữ số được viết theo chiều ngược lại. Nếu số nguyên có n chữ số thì xâu tương ứng có n+2 byte (phía cuối thêm 2 byte, byte thứ nhất chứa dấu '-' nếu đó là số âm, hoặc null nếu số dương, byte cuối cùng là null). Ví dụ, số a = 12345678901234567890 được biểu diễn bởi xâu xa = "09876543210987654321", còn b = -12345678901234567890 được biểu diễn bởi xâu b = "09876543210987654321-"nul. Để xác định số -a ta chỉ việc thay null đầu tiên bởi '-' , và –b nhận được bằng cách thay '-' bởi null.

Việc biểu diễn ngược đó thuận tiện trong các thao tác về cộng, trù, nhân chia mà không phải chèn thêm '0' (leading zero). Sau đây là một số giải thuật về cộng, trù, nhân chia các số không âm (Các số âm sẽ được nói sau). Trước hết, ta cần định nghĩa:

C Code:

    #define zero '0'

    typedef char* pchar;

Một số hàm liên quan đến cộng, trừ, nhân hai ký tự biểu thị số:

C Code:
int val(char chr) {return chr-zero;} // Giá trị tương ứng với ký tự chr biểu thị số
char chr(int num) {return num + zero;} // Ký tự tương ứng với giá trị num
int strlen(const pchar a)        // Độ dài của xâu
{ pchar p = a;     while (*p) p++; return p-a;}

Giải thuật cộng: Thông thường, khi cộng hai số có nhiều chữ số, chúng ta thực hiện từ phải qua trái. Với mỗi lần cộng, kết quả của nó còn được cộng với giá trị nhớ của lần trước đó và đồng thời cũng xác định giá trị nhớ mới. Ở đây, vì các số được lưu theo chiều ngược lại nên chúng ta thực hiện từ trái qua phải, tức là từ đầu đến cuối xâu. Do đó code có thể là: 

C Code:
char chradd(char a, char b, int &carry)  // Cộng hai chữ số
{
    int temp = val(a) + val(b) + carry;
    carry = temp/10;
    return chr(temp %10);
}

pchar stradd (const pchar a, const pchar b, const pchar c) // Cộng hai số có nhiều chữ số
{
    int i = 0, carry = 0;    //Ban đầu, nhớ bằng 0
    while(a[i] && b[i]) c[i++] = chradd(a[i],b[i],carry); // Cộng lần lượt từ đầu đến cuối
    if(a[i])                             // Nếu xâu a dài hơn xâu b
        while (a[i]) c[i++] = chradd(a[i],zero,carry); // Cộng tiếp a[i] với 0
    else                            // Nếu xâu b dài hơn
        while (b[i]) c[i++] = chradd(b[i],zero,carry); // Cộng tiếp b[i] với 0
    if (carry) c[i++] = chr(carry);            //Nếu cuối cùng mà nhớ khác 0
    c[i] = 0;                    // Đặt null vào cuối
    return c;
}

Giải thuật trừ: Giống như cộng, chúng ta cũng thực hiện từ phải qua trái. Với mỗi lần trừ, đề phòng chữ số của số bị trừ nhỏ hơn nên ta cứ vay tạm một chục. Nếu lần trước đã vay rồi thì lần này phải trừ đi. Nhưng chỉ đáng vay nếu kết quả sau khi trừ là bé hơn 10, còn lớn hơn 10 là không phải vay. Dưới đây ta xem rằng a >= b: 

C Code:
char chrsub(char a, char b, int &carry)
{
    int temp = 10 + val(a) - val(b) - carry; // Cứ vay 10 rồi trừ đi (kể cả cho nhớ cũ)
    carry = 1 - temp/10;            // Nếu sau trừ mà >= 10 thì không phải vay
    return chr(temp %10);
}
pchar strsub (const pchar a, const pchar b, const pchar c) // Trừ số có nhiều chữ số
{
    int i = 0, carry = 0;    
    while (a[i] && b[i]) c[i++] = chrsub(a[i],b[i],carry);
    while (a[i]) c[i++] = chrsub(a[i],zero,carry);
    while (i > 0 && c[--i] == zero);    
    c[++i]=0;
    return c;
}

Như chúng ta vẫn làm, kết quả của a – b với a < b chính là –(b – a), vì vậy cần viết hàm so sánh. Số nào có nhiều chữ số thì số đó lớn hơn. Khi hai số có số các chữ số khác nhau thì sự so sánh này được thực hiện từ phải qua trái do chúng ta lưu ngược lại. 

C Code:
int strrcmp(const pchar a, const pchar b)
{

    int aj = strlen(a), bj = strlen(b);

    while (aj && a[--aj]== zero);     //Bỏ qua các '0' ở cuối của a

    while (bj && b[--bj]== zero);     //Bỏ qua các '0' ở cuối của b

    if (aj > bj) return 1;            //Nếu xâu a dài hơn thì a > b

    if (aj < bj) return -1;            //Nếu xâu a ngắn hơn thì a < b

    while (aj && a[aj]==b[aj])aj--;    // Nếu độ dài như nhau thì tìm đến chữ số khác nhau đầu tiên

    return a[aj] - b[aj]; // So sánh hai chữ số đó, cùng lắm thì so các chữ số đầu tiên.

}

Một số hàm bổ trợ khác:

C Code:
pchar strcpy (const pchar dest, const pchar src) // Sao chép src vào dest
{

    int k = 0;

    while (src[k]) dest[k] = src[k++];

    dest[k] = 0;

    return dest;

}

pchar strrev( const pchar src, const pchar dest) //Hàm trỏ tới xâu dest, là đảo ngược của xâu src
{

    strcpy(dest,src);    // Khi dest trùng với src vẫn dùng được

    int len = strlen(src);

    for (int k = 0; k < len/2; k++)

        {

            char temp = dest[k];

            dest[k] = dest[len-k-1];

            dest[len-k-1] = temp;

        }

    return dest;

}

Giải thuật nhân: Thông thường, khi nhân a với b, chúng ta thực hiện từ phải qua trái. Mỗi lần sẽ nhân một chữ số của b với số a và đặt kết quả dịch sang trái 1 chữ số. Nhưng trong mỗi lần đó chúng ta lại lần lượt nhân từng chữ số của a với chữ số nói trên của b. Cũng như phép cộng, kết quả cũng phụ thuộc việc nhớ của lần nhân trước và xác định giá trị nhớ mới. Việc nhận này được thực hiện từ trái qua phải đó.

C Code:
  1. char chrmul(char a, char b, int &carry) // Nhân hai chữ số

{

    int temp = val(a) * val(b) + carry;

    carry = temp/10;

    return chr(temp %10);

}

pchar strmul(const pchar a, const pchar b, const pchar c)     // Nhân hai số có nhiều chữ số, c=a*b

{

    int jb = 0;

    pchar temp = new char[strlen(a)+2];     // Vùng nhớ lưu kết quả trung gian khi nhân a với

    do                    // từng chữ số của b.

    {

        int ja = 0, carry = 0;

        do                    //Lần lượt với từng chữ số của a

        {

            temp[ja++] = chrmul(a[ja],b[jb],carry);  // Có tăng ja đấy nhé

        }    while (a[ja]);

 

        if (carry) temp[ja++] = chr(carry); // Cuối mỗi lượt nhân a với 1 chữ số của b

        temp[ja]=0;                // Đặt null vào temp

 

        if (jb==0) strcpy(c,temp);        // Với lượt nhân đầu tiên

        else stradd(c+jb,temp,c+jb);        // Đây chính là đặt kết quả dịch 1 chữ số đó

        jb++;                    // Chuyển sang chữ số kế tiếp của b

 

    } while (b[jb]);                // Khi xâu b vẫn còn

    delete temp;                // Giải phóng vùng nhớ lưu kết quả trung gian

    return c;                // Cho hàm trỏ tới c

}

Giải thuật chia: Thông thường, khi chia a với b, chúng ta thực hiện từ trái qua phải. Lần đầu tiên lấy nhóm có số chữ số bằng số chữ số của b, các lần sau đó chỉ lần lượt hạ một số xuống phần dư. Thay vì nhẩm xem được mấy lần, ở đây chỉ việc thử lần lượt từ 0 đến có thể. Vì chúng ta lưu ngược nên ta thực hiện từ phải qua trái. Hàm sau thực hiện chia a cho b, đặt kết quả vào c và phần dư vào r.

C Code:
  1. pchar strdiv(const pchar a, const pchar b, const pchar c, const pchar r)

{

    int len = strlen(a), k = 0;

    pchar temp = new char[len+1];     // Vùng nhớ lưu các kết quả trung gian

    strcpy(temp,a);              // Ban đầu là bản sao của a

    pchar p = temp + len - strlen(b);    // Cho p trỏ tới nhóm trong a có số chữ số bằng b

    do                    // Lặp cho tới khi hạ hết các chữ số của a

    {

        c[k] = zero;            // Ban đầu đặt bằng '0' (tức = 0 lần)

        while (strrcmp(p,b)>= 0)    // Nếu còn được lần nữa

        {

            c[k]++;        // Thì cộng thêm 1

            strsub(p,b,r);        // Trừ bớt p đi 1 lần b

            strcpy(p,r);        // Cập nhật lại hiệu

        }

        p--;                 // Chuẩn bị hạ 1 chữ số của a

        k++;                 // Đã chia xong một nhóm

        c[k]=0;                // Đặt null vào cuối

    } while (p >= temp );            // Khi chưa hết các chữ số của a

 

    strrev(c,c);                // Vì thương được ghi thuận nên phải dảo lại

    k = strlen(c)-1;            

    while (c[k]== zero) k--;        // Loại bỏ '0' sinh ra vì nhóm đầu tiên có thể < b

    c[++k]=0;                // Đặt null vào cuối xâu kết quả

    delete temp;                // Xoá vùng nhớ

    return c;                // Cho hàm trỏ tới thương

}


Sau đây là một số lời gọi kiểm chứng. Do các hàm của ta thao tác với xâu ghi ngược nên chúng ta phải đảo ngược chúng trước. Tất nhiên việc này chỉ sử dụng khi ta thử thôi, còn sau này khi đã viết thành class hoàn chỉnh (dùng cho các số âm) thì các hàm input(), output() sẽ làm việc đó. 

C Code:
Select All | Show/Hide
  1. void main()

{

    char a[] = "7650035435430002526471232732", b[] = "19153500423021";

    char c[100], r[100], da[100],db[100], dc[100];

 

    strrev(a,da); strrev(b,db);             // da và db là đảo ngược của a và b

    stradd(da,db,c);                // c = da + db

    printf("\n%s + %s = %s\n",a, b, strrev(c,c));    // Vì c là đảo ngược

 

    strsub(da,db,c);                // c = da – db, đừng lấy db – da nhé

    printf("\n%s - %s = %s\n",a, b, strrev(c,c));

 

    strmul(da,db,c);                // c = da*db

    printf("\n%s * %s = %s\n",a, b, strrev(c,c));

 

    strrev(c,dc);                    // Do c bị đảo ở lệnh printf(), nên đảo lại

    stradd(dc,"123",dc);                // Cộng thêm "321 vào dc

    strdiv(dc,db,da,r);                // da = dc/db <=> da = c/b đó

    strrev(da,da);        

    strrev(r,r);

    strrev(dc,dc);

    printf("\n%s / %s = %s du %s\n,dc, b, da, r); // Chắc chắn dư là 321

}

Kết quả:

Output Code:
7650035435430002526471232732 + 19153500423021 = 7650035435430021679971655753

 

7650035435430002526471232732 - 19153500423021 = 7650035435429983372970809711

 

7650035435430002526471232732 * 19153500423021 = 146524956948634193321801854882749341523372

 

14652531001826721947557587760652816748690988242741523693 / 19153546575700423021 = 765003543543000252657567909471232732 du 321

 

 

 

Với vấn đề lưu số nguyên lớn dưới dạng mảng các số, mình xin đóng góp như sau:
Các chữ số được lưu theo chiều ngược lại và có -1 ở cuối để đánh dấu sự kết thúc. Ngoài ra còn thêm 0 hoặc -1 vào cuối để phân biệt không âm và âm. Hơn nữa, đề phòng rác trong bộ nhớ nên còn thêm 1 giá trị 0 nữa vào cuối mảng. Ví dụ, 12345 được lưu là 54321-100, còn -12345 được lưu là 54321-1-10. Số 0 được lưu là 0-100, số -1 là 1-1-10. Giải thuật cộng, trừ, nhân, chia (với các số dương) được mô phỏng theo các giải thuật xử lý xâu mà mình đã trình bày ở bài trước. So với lưu trữ dạng xâu ký tự, mình nhận thấy có hai nhược điểm. Thứ nhất là các thao tác phức tạp hơn, thứ hai là tốn bộ nhớ hơn. Khi code hàm nhập số nguyên lớn, mình xử lý theo kiểu char nên tránh được việc hỏi số chữ số cần nhập và không có khoảng cách giữa các chữ số, nhờ đó việc nhập được tự nhiên như hàm scanf(). Mặc dù có hai nhược điểm nói trên, nhưng mình cũng post lên đây nhằm tranh thủ sự góp ý của các bạn.

C Code:
Select All | Show/Hide
#include <stdio.h>
  1. #include <conio.h>

#define max 200

 

typedef int songuyen[max];

 

void daonguoc(songuyen &a) // Đảo ngược

{

    int n = 0;

    while (a[n]>=0) n++;

    for (int k=0; k < n/2; k++)

    {

        int t = a[k];

        a[k] = a[n-1-k];

        a[n-1-k] = t;

    }

}

 

void xoakhongcuoi(songuyen &a) //Xoá các chữ số 0 ở cuối sau khi đã đảo ngược

{

    int n = 0;

    while (a[n]>= 0) n++;

    if (a[n-1]> 0 || n==1) return;

    int p = n;

    while (p && a[p-1]==0) p--;

    if (p==0) p++;

    a[p]= -1;

    a[p+1]= a[n+1];

    a[p+2]= a[n+2];

}

 

void hienthi(songuyen a, char *s = "\n") //Hiển thị số

{

    int n = 0;

    while (a[n]>=0) n++;

    if (a[n+1] == -1) printf("%c",'-');

    while (n) {printf("%c",a[n-1]+'0'); n--;}

    printf("%s",s);

   

}

 

void nhapsn(songuyen &a, char ten) // Nhập số nguyên lớn

{

    printf("\nMoi ban nhap so nguyen %c: ", ten);

    int n = 0, sign = 0; char ch;

    do

        {

            ch = getch();

            if (ch == '-' && n == 0 && !sign)

                {

                    sign = 1;

                    printf("%c",ch);

                }

            else

                if ('0' <= ch && ch <= '9')

                {

                    a[n++] = ch - '0';

                    printf("%c",ch);

                }

                else

                    if (ch == '\b' && n>=0)

                        {

                            printf("%c%c%c",ch,32,ch);

                            if (n) n--;

                            if (n==0) sign = 0;

                        }

        } while (ch != '\r' || n == 0);

        printf("\n");

 

        a[n++] = -1;

        if (sign) a[n++]=-1;

        a[n++] = 0;

        daonguoc(a);

        xoakhongcuoi(a);

}

 

int sosanh(const songuyen a, const songuyen b, int p = 0) //So sánh

{

    int aj = 0, bj = 0;

    while (a[aj++] != -1);  

    while (b[bj++] != -1);

    if (aj - p > bj) return 1;

    if (aj - p < bj) return -1;

    while (bj && a[p+bj]==b[bj])bj--;

    return a[p+bj] - b[bj];

}

 

int congchuso(int a, int b, int &carry)  // Cộng hai chữ số

{

    int temp = a + b + carry;

    carry = temp/10;

    return temp %10;

}

 

void cong (const songuyen a, const songuyen b, songuyen &c, int p = 0) // Cộng số lớn

{

    int i, carry = 0;  

    for (i = 0; i < p; i++) c[i] = a[i];

    i = 0;

    while(a[i+p]!=-1 && b[i]!=-1) c[p+i++] = congchuso(a[p+i],b[i],carry);

    if(a[i+p]!=-1)                            

        while (a[i+p]!=-1) c[p+i++] = congchuso(a[p+i],0,carry);

    else                            

        while (b[i]!=-1) c[p+i++] = congchuso(b[i],0,carry);

    if (carry) c[p+i++] = carry;

    c[p+i] = -1;

    c[p+i+1] = 0;                  

}

 

int truchuso(int a, int b, int &carry)// Trừ hai chữ số

{

    int temp = 10 + a - b - carry;

    carry = 1 - temp/10;          

    return temp %10;

}

 

void tru (const songuyen a, const songuyen b, songuyen &c, int p=0)//Trừ số lớn

{

    int i, carry = 0;  

    for (i = 0; i < p; i++) c[i] = a[i];

    i = 0;

    while (a[p+i]!=-1 && b[i]!=-1) c[p+i++] = truchuso(a[p+i],b[i],carry);

    while (a[p+i]!=-1) c[p+i++] = truchuso(a[p+i],0,carry);

    c[p+i++]=-1;c[p+i++] = 0;

    xoakhongcuoi(c);

}

 

int nhanchuso(int a, int b, int &carry) //Nhân 2 chữ số

{

    int temp = a*b + carry;

    carry = temp/10;

    return temp %10;

}

 

void saochep(songuyen &b, const songuyen a)//Sao chép

{

    int n=0;

    while (a[n] != -1) b[n] = a[n++];

    while (a[n] == -1) b[n] = a[n++];

    b[n] = 0;

}

 

void nhan(const songuyen a, const songuyen b, songuyen &c)  //Nhân hai số lớn

{

    int jb = 0;

    songuyen temp;

    do                  

    {

        int ja = 0, carry = 0;

        do                  

        {

            temp[ja++] = nhanchuso(a[ja],b[jb],carry);  

        }   while (a[ja]!=-1);

 

        if (carry) temp[ja++] = carry;

        temp[ja]= -1; temp[ja+1]= 0;            

        if (jb==0) saochep(c,temp);

        else cong(c,temp,c,jb);

        jb++;                  

 

    } while (b[jb]!=-1);                

}

 

void chia(const songuyen a, const songuyen b, songuyen &c, songuyen &r)//Chia hai số lớn

{

    int ja=0, jb=0,k = 0;

    while (a[ja] != -1) ja++;

    while (b[jb] != -1) jb++;

    songuyen temp;  

    saochep(temp,a);

    int jt = ja - jb;

    do                

    {

        c[k] = 0;            

        while (sosanh(temp,b,jt)>= 0)    

        {

            c[k]++;

            tru(temp,b,r,jt);      

            saochep(temp,r);

        }

        jt--;              

        k++;                

    } while (jt >= 0 );          

    c[k]=-1; c[k+1]=0;

    daonguoc(c);

    xoakhongcuoi(c);

}

 

void main()

{

    songuyen a, b, c,r;

    nhapsn(a,'a'); nhapsn(b,'b');

    cong(a,b,c); hienthi(a," + "); hienthi(b," = "); hienthi(c);

    tru(a,b,c); hienthi(a," - "); hienthi(b," = "); hienthi(c);

    nhan(a,b,c); hienthi(a," * "); hienthi(b," = "); hienthi(c);

    chia(a,b,c,r); hienthi(a," / "); hienthi(b," = "); hienthi(c," du "); hienthi(r);

}

Dưới đây là kết quả minh họa:

Output Code:
Select All | Show/Hide
Moi ban nhap so nguyen a: 001234567891234567890123 

Moi ban nhap so nguyen b: 0012345678

1234567891234567890123 + 12345678 = 1234567891234580235801

1234567891234567890123 - 12345678 = 1234567891234555544445

1234567891234567890123 * 12345678 = 15241577654320997640597938394

1234567891234567890123 / 12345678 = 100000007390000 du 7470123

 

http://diendan.congdongcviet.com/threads/t31199::thao-tac-so-nguyen-lon-trinh-bay-thuat-toan-cach-thuc-hien.cpp