BCBIGNUM – Xử lý số nguyên lớn – E16CN PTIT

Posted on by mtoplistChuyên mục:Top List

Link Sub: http://www.spoj.com/PTIT/problems/BCBIGNUM/

Người Gửi:

Dương Lee

  • Problem:

Cho hai số nguyên dương A và B ( A & B có không quá 1000 chữ số )

Yêu cầu:  Tính A + B, A – B, A * B  

Chú ý: Khi kết quả là 0 các bạn phải in ra 0, nếu in -0 là sai  

Các chữ số 0 không có nghĩa ở đầu không được in ra. VD 013 thì phải in ra là 13, chữ số 0 ở đầu không có nghĩa  

Vì cách chấm ở đây là so sánh 2 FILE kết quả

Input

Dòng 1: số nguyên A  

Dòng 2: số nguyên B

Output

Dòng 1: Kết quả A + B  

Dòng 2: Kết quả A – B  

Dòng 3: Kết quả A * B

Example:

Input
10
11
Output:
21
-1
110

  • Solution:



Vì con số lên tới 1000 chữ số (Gần 10^1000) nên không thể lưu trữ dữ liệu và tính toán thông thường được. Ta phải chuyển về xử lý string. (1000 kí tự thì string xử lí thoải mái).
B1: Xử lý chung:
- Ta phải nhập vào A và B dưới dạng string
- Chuyển nó về dạng Mảng các số đơn lẻ cùng độ dài (StrToNumArr)
VD:
A: 115
B: 45
->
Arr: 1 1 5
Brr: 0 4 5

B2: Với A+B.
Ta sẽ cộng như cách cộng ở mẫu giáo: Cộng từng phần tử từ cuối về đầu i:(n-1 -> 0), Nếu phép công >10 thì lấy số cuối và nhớ 1 ở số tiếp theo.

B3: Với A-B.
- Đầu tiên xét xem A > B hay A < B (ss), A==B ->=0.
- Lấy số lớn lớn trừ số bé theo quy tắc trừ ở mẫu giáo: Trừ từng phần tử từ cuối về đầu i:(n-1 -> 0). Nếu phép trừ <0 thì + thêm 10 và nhớ 1 ở số tiếp theo.
- Sau khi tính xong thì lưu ý số in ra không có 0 ở đầu và phụ thuộc vào ss để xét xem có thêm dấu trừ đằng trước hay không.

B4: Với A*B.
- Sẽ cần thêm 2 mảng là Btg và Ctg với chiều dài =2*lenmax(A,B).
- Nhân thông thường như tiểu học. Với mỗi dãy số của phép nhân từng phần tử sẽ được lưu vào Btg và cộng dồn vào Ctg (bằng hàm A+B bên trên).

  • Code:

C:


#include <stdio.h>
#include <string.h>
 
int StrToNumArr (char a[], char b[], int A[], int B[]) {
    int lenA = strlen (a);
    int lenB = strlen (b);
   
    int len;
    if (lenA>lenB) len=lenA;
    else len = lenB;
   
    lenA--;
    lenB--;
    for (int i=len-1; i>=0; i--) {
        if (lenA>=0) {
            A[i] = a[lenA]-'0';
            lenA--;
        } else A[i]=0;
       
        if (lenB>=0) {
            B[i] = b[lenB]-'0';
            lenB--;
        } else B[i]=0;
    }
    return len;
}
 
int SumBig (int A[], int B[], int len, int C[]) {
    for (int i=len-1; i>=0; i--) {
        if (i!=0) {
            int x = A[i]+B[i];
            C[i]=x%10;
            B[i-1]=B[i-1]+(x/10);
        } else C[i]=A[i]+B[i];
    }
    return len;
}
 
int ss (int A[], int B[], int len) {
    for (int i=0; i<len; i++) {
        if (A[i]>B[i]) return 1;
        else if (A[i]<B[i]) return -1;
    }
    return 0;
}
 
int MiBig (int A[], int B[], int len, int C[], int *dau) {
    int hs=ss (A, B, len);
    if (hs==0) return 0;
    *dau=hs;
    for (int i=len-1; i>=0; i--) {
        int x;
        if (hs==1) x=A[i]-B[i];
        else x=B[i]-A[i];
        if (i!=0) {
            if (x>=0) C[i]=x;
            else {
                C[i]=x+10;
                if (hs==1) B[i-1]=B[i-1]+1;
                else A[i-1]=A[i-1]+1;
            }
        } else {
            C[i]=x;
        }
    }
    for (int i=0; i<len; i++) {
        if (C[i]!=0) return (len-i);
    }
}
 
void sc (int A[], int B[], int len) {
    // Cop B -> A;
    for (int i=0; i<len; i++) {
        A[i]=B[i];
    }
}
 
int PrBig (int A[], int B[], int len, int C[]) {
    int Btg[2006];
    int Ctg[2006];
    int lenMax=2*len;
    for (int i=0; i<lenMax; i++) {
        Btg[i]=0;
        Ctg[i]=0;
    }
    for (int i=len-1; i>=0; i--) {
        lenMax--;
        int k=lenMax;
        for (int j=0; j<2*len; j++) {
            Btg[j]=0;
        }
        for (int j=len-1; j>=0; j--) {
            int x=Btg[k]+B[i]*A[j];
            Btg[k]=(x)%10;
            Btg[k-1]=(x)/10;
            k--;
        }
        SumBig (Ctg, Btg, 2*len, C);
        sc (Ctg, C, 2*len);
    }
    for (int i=0; i<2*len; i++) {
        if (C[i]!=0) return (2*len-i);
    }
    return 0;
}
 
int main () {
    char a[1001] = "";
    char b[1001] = "";
    scanf ("%s%s", a, b);
    int len;
   
   
   
    int As[1003];
    int Bs[1003];
    int Sum[1003];
    len = StrToNumArr (a, b, As, Bs);
    int lenSum = SumBig (As, Bs, len, Sum);
    for (int i=0; i<lenSum; i++) {
        printf ("%d", Sum[i]);
    }
    printf ("\n");
   
    int Am[1003];
    int Bm[1003];
    len = StrToNumArr (a, b, Am, Bm);
    int Mi[1003];
    int dau=1;
    int lenMi = MiBig (Am, Bm, len, Mi, &dau);
    if (lenMi==0) printf ("0");
    else {
        if (dau==-1) printf ("-");
        for (int i=len-lenMi; i<len; i++) {
            printf ("%d", Mi[i]);
        }
    }
    printf ("\n");
   
    int Ap[1003];
    int Bp[1003];
    len = StrToNumArr (a, b, Ap, Bp);
    int Pr[2006];
    int lenPr = PrBig (Ap, Bp, len, Pr);
    if (lenPr==0) printf ("0");
    else {
        for (int i=2*len-lenPr; i<2*len; i++) {
            printf ("%d", Pr[i]);
        }
    }
   
    return 0;
}

C++:

JAVA:

Share this

Related Posts

mtoplist