Xử lý số lớn - part1

[lanhhuyet510 (Lãnh Huyết)]

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:
https://docs.google.com/document/d/1HLj__PFd7WbrK637G0HJnNHGJR2SkzUkCXSWaNwa-zc/edit?usp=sharing
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,'\0');
    number1=number(str,&n1,1);
    memset(str,30,'\0');
    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

[ltd (Lê Trần Đạt)]

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

Cách post Code dùng Markdown trong Category Programming

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

[dailammoc]

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

[phuongle71104 (Phương 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

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”

[yenchuchu95 (Thúy Hiền)]

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

[ltd (Lê Trần Đạt)]

@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

[lanhhuyet510 (Lãnh Huyết)]

tks anh nhiều! @ltd

[lanhhuyet510 (Lãnh Huyết)]

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

[lanhhuyet510 (Lãnh Huyết)]

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

[ltd (Lê Trần Đạt)]

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

[lanhhuyet510 (Lãnh Huyết)]

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