Xử lý số lớn - part1
Trong lúc lập trình đã bao giờ bạn bị trường hợp số xử lý quá lớn mà các kiểu dữ liệu double hay long double cũng không lưu trữ được?
Dưới đây mình xin trình bày 1 trong số nhiều cách để giúp bạn xử lý được trường hợp trên (xử lý số lớn)
Nhìn chung thì “xử lý” ở đây mình đưa ra với các phép toán số học thông thường (+,-,*,/), và cũng có thể phát triển theo hướng này các phép toán khác.
Hầu hết các phương pháp xử lý số lớn đều xoay quanh việc “cắt nhỏ” số lớn để xử lý rồi “vá” lại.
Mình xin trình bày 1 cách đơn giản và tỏ ra khá hiệu quả, đó là xử lý kiểu mảng(Ví dụ của mình là cộng hai số lớn). Với mỗi chữ số mình sẽ cắt ra và cho vào 1 phần tử của mảng. Sau đó thực hiện phép cộng các phần tử của mảng tương ứng được mảng mới để hiển thì kết quả ra màn hình.
Cách này tuy là xử lý được nhưng có 1 nhược điểm là cần tốn quá nhiều bộ nhớ vì phải mất 3 mảng (mỗi phần tử của mảng ăn mẹ mất 4byte rồi T_T). Vì thế mình đề xuất cho mọi người 1 cách khác là XỬ LÝ VỚI CHUỖI. mỗi ký tự chỉ mất có 1 byte thôi (Dành cho các bạn nghiên cứu, lúc nào rảnh mình làm rồi làm cái pic khác hen! )
Hình minh họa cho các bạn!
Bạn nào rảnh có thể code thêm 1 đoạn nữa cho 2 số a+b rồi in ra màn hình xem(với a,b lớn như trong hình) ^.^
À còn 1 điều nữa là thuật toán của mình chỉ cho phép đầu vào là số thứ 1 có số chữ số lớn hơn hoặc bằng số thứ 2 thôi nhé ^^. Nếu muốn hoàn thiện hơn thì đó là việc mh để giành cho các bạn đó
Code:
large_number_solution
#include #include #include #include int *number(char str[],int*n, int k){ printf(" Nhap so thu %d:",k); gets(str); *n=strlen(str); int *p; p=(int*) malloc((*n)*4); for(int i=0;i<*n;i++) *(p+i)=str[i]-48;...
p.s: Sư thật thì coppy & paste vào đây nó ra cái khỉ gì ấy nên m.n vào google doc xem nhaz!
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <conio.h>
int *number(char str[],int*n, int k)
{
printf(" Nhap so thu %d:",k);
gets(str);
*n=strlen(str);
int *p;
p=(int*) malloc((*n)*4);
for(int i=0; i<*n; i++) *(p+i)=str[i]-48;
return p;
}
void display(int arr[], int n)
{
for(int i=0; i<n; i++) printf("%d",arr[i]);
}
int *add_num(int *num1, int n1, int *num2, int n2)
{
int r=0,*p;
int n;
n=n1+1;
p=(int*) malloc(n*4);
int i1=n1;
int i2=n2;
while(n>0)
{
i1--;
i2--;
n--;
if(i2>=0) *(p+n)=num1[i1]+num2[i2]+r;
else if(i1>=0) *(p+n)=num1[i1]+r;
else *(p+n)=r;
r=0;
if(*(p+n)>9)
{
r=1;
*(p+n)=*(p+n)-10;
}
}
return p;
}
int main()
{
int *number1,n1,*number2,n2,*result,size;
char str[30];
memset(str,30,' ');
number1=number(str,&n1,1);
memset(str,30,' ');
number2=number(str,&n2,2);
display(number1,n1);
printf(" + ");
display(number2,n2);
printf(" = ");
size=n1+1;
result=add_num(number1,n1,number2,n2);
display(result,size);
free(number1);
free(number2);
getch();
}
Mọi người thẳng thắn góp ý trao đổi nhé! Gạch đá nhận hết
Anh mới sửa bài em để post code lên, anh thấy “cái khỉ gì” trông cũng có vẻ ổn mà :trollface:
Cách post code dùng markdown nè em
P/S: Good, anh đang cần tìm một bạn làm bài xử lý số lớn. Bài này là một trong những bài cơ bản nhất mà sinh viên CNTT phải nắm. Để anh share lên FB
Nhớ năm đầu học cũng làm assignment với thư viện tĩnh để tính các số nguyên lớn(big integer). Hồi đó tìm hiểu cực lắm đâu có sẵn như bây giờ . Đánh giá cao bài viết của bạn
Khi cộng các phần tử tương ứng của hai mảng theo từng cột bằng phương pháp số học thì nhớ 1 đưa qua bên trái.
Kết quả vẫn chưa được như mong đợi.
99 + 9 = 08
999 + 9 = 008
9999 + 9 = 0008
“No Star Where”
á, cũng mới làm bài này xong nhưng = java, :v nhưng chỉ làm được với số dương thôi. chưa làm được với số âm
@yenchuchu95 làm một topic chia sẻ bên Java đi
P/S: Chương trình của Tuấn Nguyễn trên FB
http://codepad.org/XO4iv5Fs
tks anh nhiều! @ltd
Bài post còn nhiều thiếu sót, mình sẽ sửa lại cho hoàn chỉnh hơn. Cảm ơn mọi người góp ý!
Em mới update lại code để tránh lỗi như bạn @phuongle71104 nói, anh sửa lại giúp em phần hiển thị code trên daynhauhoc nhé @ltd
I moved a post to a new topic: Khi nào diễn đàn mở category Java vậy?
Gió nhẹ có thể cho ví dụ code cụ thể hơn không?
góp ý hay lắm gió lạnh ^_^.
mh sẽ code lại bài khác theo thuật toán karatsuba như bạn.
À ngoài ra bạn còn biết thuật toán xử lý số lớn nào nữa không ạ?
I moved a post to a new topic: Xử lý số lớn bằng Java