Link Sub: http://www.spoj.com/PTIT/problems/BCBIGNUM/
Người Gửi: Dương Lee
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
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).
C:
https://pastebin.com/r0QmcUx6
#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:
