Tạo bài viết
Đăng ký
30/09/2018, 16:09

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) ^.^

large_number_solution.png1366x768 205 KB

À 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:

docs.google.com

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

Nguyễn Minh Dũng viết 18:14 ngày 30/09/2018

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!

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

Làm sao để có thể hiển thị syntax highlighting bằng markdown? Các bạn phải đánh dấu ``` như ví dụ dưới đây Chú ý, dấu ``` được tạo ra bởi nút nằm bên trái số 1 trên bàn phím, nút này sẽ là ~ khi bấm giữ Shift Ví dụ cho C Nội dung: ``` void main() { } ``` Và đừng quên ``` ở cuối Kết quả void main() { } Ví dụ cho Pascal Nội dung: ``` Program HelloWorld; Begin WriteLn('Hello world!') {no ";" is required after the last statement of a block - adding one adds a "null stateme…

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

viết 18:22 ngày 30/09/2018

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

Phương Lê viết 18:16 ngày 30/09/2018

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

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”

Thúy Hiền viết 18:24 ngày 30/09/2018

á, 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

Nguyễn Minh Dũng viết 18:26 ngày 30/09/2018

@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 

#include <iostream>
#include <string.h>
#include <conio.h>
using namespace std;

 struct NODE
{
	int data;
	NODE *pNext,*pPred;
};typedef struct NODE NODE;
typedef struct
{
	NODE *pHead,*pTail;
}LIST;

void Init(LIST &L)
{
	L.pHead=L.pTail=NULL;
}
NODE *CreateNode(int &x)
{
	NODE *newnode=new NODE;
	if(newnode==NULL) //Khong du bo nho cap phat
		return NULL;
	newnode->data=x;
	newnode->pNext=NULL;
	newnode->pPred=NULL;
	return newnode;
}
void AddHead(LIST &L,NODE *p)
{
	if(L.pHead==NULL)
	{
		L.pHead=L.pTail=p;
	}
	else
	{
		p->pNext=L.pHead;
		L.pHead->pPred=p;
		L.pHead=p;
	}
}
void AddTail(LIST &L,NODE *p)
{
	if(L.pHead==NULL)
	{
		L.pHead=L.pTail=p;
	}
	else
	{
		L.pTail->pNext=p;
		p->pPred=L.pTail;
		L.pTail=p;
	}
}
void DisplayHead(LIST L)
{
	if(L.pHead==NULL)
		return;
	for(NODE *p=L.pHead;p!=NULL;p=p->pNext)
		cout<<p->data;
}
void DeleteHead(LIST &L)
{
	if(L.pHead==NULL)
		return;
	else if(L.pHead==L.pTail)
	{
		delete L.pHead;
          Init(L);
	}
	else
	{
		NODE *p=L.pHead;
		L.pHead=L.pHead->pNext;
		delete p;
	}
}
int Count(LIST L)
{
	int count=0;
	if(L.pHead==NULL)
		return count;
	for(NODE *p=L.pHead;p!=NULL;p=p->pNext)
		count++;
	return count;
}

void Nhap2Chuoi(LIST &L,LIST &L2,char s[100],char s2[100])
{
	cout<<"\nNhap So Thu Nhat:";
	fflush(stdin);
	gets(s);
	cout<<"\nNhap So Thu Hai:";
	fflush(stdin);
	gets(s2);

	for(int i=0;i<strlen(s);i++)
	{
		int temp=s[i]-48;
		NODE *p=CreateNode(temp);
		AddTail(L,p);
	}
	for(int i=0;i<strlen(s2);i++)
	{
		int temp2=s2[i]-48;
		NODE *q=CreateNode(temp2);
		AddTail(L2,q);
	}
}
void Nhap1Chuoi(LIST &L,char s[100])
{
	cout<<"\nNhap So:";
	fflush(stdin);
	gets(s);
	for(int i=0;i<strlen(s);i++)
	{
		int temp=s[i]-48;
		NODE *p=CreateNode(temp);
		AddTail(L,p);
	}
}
void CanBangChuSo(LIST &L,LIST &L2)
{
	int k=0,x=0;
	int CountL=Count(L),CountL2=Count(L2);
	if(CountL > CountL2)
{
		k=CountL-CountL2;
	for(int i=0;i<k;i++)
	{
		NODE *p=CreateNode(x);
		AddHead(L2,p);
	}
}
	 if(CountL2 > CountL)
 {		k=CountL2-CountL;
	for(int i=0;i<k;i++)
	{
		NODE *q=CreateNode(x);
		AddHead(L,q);
	}	
 }
}
void XoaSo0Du(LIST &L)
{
	int dem=0;
	if(L.pHead->data!=0)
		return;
	for(NODE *p=L.pHead;p->pNext!=NULL;p=p->pNext)
	{
		if(p->data==0 && p->pNext->data==0)
		   dem++;
	   else
			break;
	}
	  for(int i=0;i<dem;i++)
		DeleteHead(L);
	  DeleteHead(L);
}
LIST TinhTong(LIST L,LIST L2)
{
	LIST Tong;
	Init(Tong);
	int nho=0,x;
	NODE *z;
	CanBangChuSo(L,L2);
	for(NODE *p=L.pTail,*q=L2.pTail;;p=p->pPred,q=q->pPred)
	{
		int temp=(p->data)+(q->data)+nho;
		nho=temp/10;
		x=temp%10;
		z=CreateNode(x);
		AddHead(Tong,z);
		if(q==L2.pHead)
			break;
	}
	if(nho!=0)
	{
		z=CreateNode(nho);
		AddHead(Tong,z);
	}
	return Tong;
}
LIST operator+(LIST L,LIST L2)
{
	LIST kq;
	Init(kq);
	kq=TinhTong(L,L2);
	return kq;
}
int SoSanh2So(LIST L,LIST L2)
{
	 CanBangChuSo(L,L2);
	 for(NODE *p=L.pHead,*q=L2.pHead;p!=NULL;p=p->pNext,q=q->pNext)
	 {
		 if(p->data > q->data)  // Ket luan So Thu 1 > So Thu 2
			 return 1; 
		 else if(p->data < q->data) //Ket luan So Thu 2 > So Thu 1
			 return 2;
	 }
	 return 0;  // 2 so bang nhau
}
LIST TinhHieu(LIST L,LIST L2)
{
	LIST Hieu;
	Init(Hieu);
	int nho=0,x;
	NODE *z;
	for(NODE *p=L.pTail,*q=L2.pTail;;p=p->pPred,q=q->pPred)
	{
		int temp=(p->data)-(q->data)-nho;
		if(temp<0)
			{
				temp+=10;
				nho=1;}
		else
		{
			nho=temp/10;}
		x=temp%10;
		z=CreateNode(x);
		AddHead(Hieu,z);
		if(q==L2.pHead)
			break;
	}
	XoaSo0Du(Hieu);
	return Hieu;
}
LIST operator-(LIST L,LIST L2)
{
	LIST kq;
	Init(kq);
	kq=TinhHieu(L,L2);
	return kq;
}
void RemoveList(LIST &L)
{
	if(L.pHead==NULL)
		return;
	while(L.pHead!=NULL)
	{
		NODE *p=L.pHead;
		L.pHead=L.pHead->pNext;
		delete p;
	}
	Init(L);
}
LIST TinhTich(LIST L,LIST L2)
{
	int x,khong=0,k,k2=0;
	NODE *z;
	LIST Tich;
	Init(Tich);
	LIST Sum,Sum2;
	Init(Sum);
	Init(Sum2);
	z=CreateNode(khong);
	AddHead(Sum,z);
	AddHead(Sum2,z);
	Sum=Sum+Sum2;
	if(Count(L)>Count(L2))
		k=Count(L);
	else
		k=Count(L2);
		for(NODE *q=L2.pTail;;q=q->pPred)
	{
		int nho=0;
		for(NODE*p=L.pTail;;p=p->pPred)
		{
			int temp=(p->data)*(q->data)+nho;
			nho=temp/10;
			x=temp%10;
			z=CreateNode(x);
			AddHead(Tich,z);
			if(p==L.pHead)
				break;
		}
		if(nho!=0)
		{
			z=CreateNode(nho);
			AddHead(Tich,z);
		}
		for(int i=1;i<=k;i++)
		{
			z=CreateNode(khong);
			AddHead(Tich,z);
		}
		for(int j=0;j<k2;j++)
		{
			z=CreateNode(khong);
			AddTail(Tich,z);
		}
		k--;
		k2++;
		Sum=Sum+Tich;
		RemoveList(Tich);
		if(q==L2.pHead)
			break;
	}
		XoaSo0Du(Sum);
		return Sum;
}
LIST operator*(LIST L,LIST L2)
{
	LIST kq;
	Init(kq);
	kq=TinhTich(L,L2);
	return kq;
}
LIST Thuong(LIST L,LIST L2)
{
	int x=1;
	NODE *z;
	LIST Temp,thuong;
	Init(Temp);
	Init(thuong);
	for(NODE *p=L.pHead;p!=NULL;p=p->pNext)
	{
		int x=p->data;
		int count=0;
		z=CreateNode(x);
		AddTail(Temp,z);
		while(SoSanh2So(Temp,L2)!=2)
		{
			Temp=Temp-L2;
			count++;
		}
		z=CreateNode(count);
		AddTail(thuong,z);
	}
	XoaSo0Du(thuong);
	return thuong;
}
LIST operator/(LIST L1,LIST L2)
{
	return Thuong(L1,L2);
}
LIST LuyThua(LIST L,int somu)
{
	LIST sum1,sum2,luythua;
	int khong=0,mot=1;
	Init(sum1);
	Init(sum2);
	NODE *z;
	z=CreateNode(khong);
	AddHead(sum1,z);
	z=CreateNode(mot);
	AddHead(sum2,z);
	luythua=sum1+sum2;
	for(int i=0;i<somu;i++)
	{
		luythua=luythua*L;
	}
	return luythua;
}
LIST GiaiThua(LIST L)
{
	int mot=1;
	LIST gt,k;
	Init(gt);
	Init(k);
	NODE*z;
	z=CreateNode(mot);
	z=CreateNode(mot);
	AddHead(gt,z);
	AddHead(k,z);
	while(SoSanh2So(L,k)!=2)
	{
		gt=gt*L;
		CanBangChuSo(L,k);
		L=L-k;
	}
	return gt;
}
int main()
{
	system("color 0a");
	int somu,chon;
	LIST L,L2;
	char s[100],s2[100];
	Init(L);
	Init(L2);
	LIST *T=new LIST;
	LIST *Tich=new LIST;
	LIST *H=new LIST;
	LIST *Thuong2=new LIST;
	LIST *luythuaL=new LIST;
	LIST *gt=new LIST;
	do{
		system("cls");
		cout<<"\t\t|______________COPYRIGHT TUAN NGUYEN______________|\n";
		cout<<"\t1.Tinh Tong 2 Chuoi So Nguyen Duong \n\n";
		cout<<"\t2.Tinh Hieu 2 Chuoi So Nguyen Duong\n\n";
		cout<<"\t3.Tinh Tich 2 Chuoi So Nguyen Duong\n\n";
		cout<<"\t4.Tinh Thuong 2 Chuoi So Nguyen Duong\n\n";
		cout<<"\t5.Tinh Luy Thua Chuoi So Nguyen Duong\n\n";
		cout<<"\t6.Tinh Giai Thua Chuoi So Nguyen Duong\n\n";
		cout<<"\t7.Ket thuc\n";
		cout<<"Moi Ban Chon:\n";
		cin>>chon;
		switch(chon)
	{
		case 1:system("cls");Nhap2Chuoi(L,L2,s,s2);CanBangChuSo(L,L2);*T=L+L2;
			cout<<"\nTong = ";DisplayHead(*T); RemoveList(L);RemoveList(L2);getch();break;
		
		case 2:system("cls");Nhap2Chuoi(L,L2,s,s2);CanBangChuSo(L,L2);
			if(SoSanh2So(L,L2)==1 || SoSanh2So(L,L2)==0)
			{*H=L-L2;if(Count(*H)==0) cout<<"Hieu = 0";else cout<<"\nHieu = ";}
			else if(SoSanh2So(L,L2)==2)
			{*H=L2-L; if(Count(*H)==0) cout<<"Hieu = 0";else cout<<"\nHieu = - ";}
			DisplayHead(*H);RemoveList(L);RemoveList(L2);getch();break;
		case 3:system("cls");Nhap2Chuoi(L,L2,s,s2);CanBangChuSo(L,L2);*Tich=L*L2;
			cout<<"\nTich = ";
	       if(Count(*Tich)==0)
		       cout<<"0";
	      else
	         DisplayHead(*Tich);RemoveList(L);RemoveList(L2);getch();break;
		case 4:system("cls");Nhap2Chuoi(L,L2,s,s2);CanBangChuSo(L,L2);*Thuong2=L/L2;
           cout<<"\nThuong = ";
	          DisplayHead(*Thuong2);getch();RemoveList(L);RemoveList(L2);break;
		case 5:system("cls");Nhap1Chuoi(L,s);do{
			cout<<"\nNhap Vao So Mu De Tinh Luy Thua:";
	          cin>>somu;
	           if(somu<0)
		       cout<<"Nhap So Mu >=0!\n";
	             }while(somu<0);*luythuaL=LuyThua(L,somu);cout<<"\n So Thu Nhat ^ "<<somu<<" = ";
	DisplayHead(*luythuaL);getch();RemoveList(L);break;
		case 6:system("cls");cout<<"Nhap n:\n";Nhap1Chuoi(L,s);*gt=GiaiThua(L);
	cout<<"n! = ";DisplayHead(*gt);getch();RemoveList(L);break;

	 }
	}while(chon!=7);
	delete T;
	delete H;
	delete Tich;
	delete Thuong2;
	delete luythuaL;
	delete gt;
	return 0;
}

http://codepad.org/XO4iv5Fs

Lãnh Huyết viết 18:22 ngày 30/09/2018

tks anh nhiều! @ltd

Lãnh Huyết viết 18:25 ngày 30/09/2018

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 ý!

Lãnh Huyết viết 18:23 ngày 30/09/2018

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

Nguyễn Minh Dũng viết 18:11 ngày 30/09/2018

I moved a post to a new topic: Khi nào diễn đàn mở category Java vậy?

Nguyễn Minh Dũng viết 18:21 ngày 30/09/2018

Gió nhẹ có thể cho ví dụ code cụ thể hơn không?

Lãnh Huyết viết 18:23 ngày 30/09/2018

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 ạ?

Nguyễn Minh Dũng viết 18:23 ngày 30/09/2018

I moved a post to a new topic: Xử lý số lớn bằng Java

Bài liên quan

Lãnh Huyết

0 chủ đề

0 bài viết

Tác giả nổi bật
Từ khóa nổi bật
AngularJS Blog Bootstrap C / C++ Cấu trúc dữ liệu & Giải thuật Cơ sở dữ liệu Codeigniter Công cụ lập trình CSS CSS cơ bản CSS3 Học Excel HTML HTML cơ bản HTML5 Java Javascript jQuery Json Lập trình mobile Laravel Linux MongoDB MySQL NodeJS Oracle Pascal PHP PHP cơ bản PHP nâng cao Python React Native ReactJS Ruby SEO SQL Server Swift Visual Basic VueJS WordPress XML
Chủ đề nổi bật
0
Các chủ đề đang được quan tâm
phần mềm lập trình php | lập trình web php + mysql | khóa học lập trình php | tự học lập trình php | học php cơ bản thachpham | Giảm giá khuyến mãi thùng rác giá rẻ, thùng rác 120l 240l 660l màu xanh lh 0911.082.000 | Chi phí vận chuyển (Giao hàng đến các địa điểm theo yêu cầu của Công ty). | Xe nâng tay giá rẻ, xe nâng 3 tấn và tải trọng thông dụng nhất hiện nay-lh 0911.082.000 | Code24h | Cho thuê phòng trọ hà nội | Cho thuê phòng trọ bình thạnh | Cho thuê phòng trọ | Cho thuê nhà trọ
Đăng ký

Đăng ký nhận thông báo

Các bài học thú vị sẽ được gửi đến inbox của bạn

HỖ TRỢ HỌC VIÊN
VỀ CODE24H
HỢP TÁC VÀ LIÊN KẾT
KẾT NỐI VỚI CHÚNG TÔI
TẢI ỨNG DỤNG TRÊN ĐIỆN THOẠI

CCode 24h, code mọi lúc, mọi nơi

© Copy right 2018 - 2024