Cộng 2 số nguyên lớn có nhiều chữ số

Trong các ngôn ngữ lập trình nói chung và trong C++ nói riêng, việc tính toán các phép toán dựa trên dữ liệu kiểu số vô cùng đơn giản.

Tuy nhiên, khi gặp phải các số có nhiều chữ số thì không còn đơn giản nữa. Do các kiểu dữ liệu biểu diễn số học ngôn ngữ hỗ trợ có giới hạn.

Vậy để thực hiện cộng 2 số nguyên lớn chúng ta phải làm sao?

Sau đây là ý tưởng giải quyết cho vấn đề này:

• Sử dụng 2 danh sách liên kết để biểu diễn cho 2 số nguyên.
• Trong đó mỗi một node trong danh sách biểu diễn cho 1 chữ số của số nguyên theo chiều đảo. Ví dụ: Ví dụ số 1234 thì danh sách liên kết sẽ lưu trữ là [(root)-4]->[3]->[2]->[1].
• Tiến hành thực hiện theo phương pháp cộng bằng tay thần thánh mà chúng ta học từ tiểu học. Ví dụ:

  1234
+
     3
------
  1237

Sau đây là phần code C++ thực hiện cộng 2 số theo ý tưởng trên:

/*YÊU CẦU:=======================================================================================================================
**  Để lưu trữ một số nguyên lớn, ta có thể dùng danh sách liên kết chứa các chữ số của nó. 
**	Hãy tìm cách lưu trữ các chữ số của một số nguyên lớn theo ý tưởng trên sao cho việc cộng hai số nguyên lớn là dễ thực hiện.
**	Viết chương trình cộng hai số nguyên lớn
**==============================================================================================================================*/

/*Ý TƯỞNG GIẢI QUYẾT:=============================================================================================================	
**  Sử dụng 2 danh sách liên kết để biểu diễn cho 2 số nguyên. 
**	Trong đó mỗi một node trong danh sách biểu diễn cho 1 chữ số của số nguyên theo chiều đảo. 
**	Ví dụ số 1234 thì danh sách liên kết sẽ lưu trữ là [(root)-4]->[3]->[2]->[1]
**	Tiến hành thực hiện cộng tay rồi in kết quả ra từng ký tự:
**	1234
** +   3
**  ----
*	1237 
**==============================================================================================================================*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <iostream.h>
#include <string.h>

//ĐỊNH NGHĨA CẤU TRÚC NODE
typedef struct Node
{
    int data;
    Node* next;
} NodeType;

//HÀM THÊM 1 GIÁ TRỊ (VALUE) VÀO DANH SÁCH
void Insert( NodeType* &root, int value )
{
    if(root==NULL)
    {
		NodeType* newnode = (NodeType*)malloc( sizeof( NodeType ) );
		newnode->next = NULL;
		newnode->data = value;
		root=newnode;
		//printf("1-%d;    ",value);
    }
    else
    {   NodeType* P=root;
		while(P->next!=NULL)
		{
			P=P->next;
		}
		
		NodeType* newnode = (NodeType*)malloc( sizeof( NodeType ) );
		newnode->next = NULL;
		newnode->data = value;
		P->next=newnode;
		//printf("2-%d;    ",value);
    }
}

void PrintList(NodeType* &root)
{
	NodeType* P=root;
	while(P!=NULL)
	{
		cout<<P->data<<endl;
		P=P->next;
	}
}

void InTong(NodeType* &SoA, NodeType* &SoB,const int maxlen)
{
	int ketqua[100];
	NodeType* P1=SoA;
	NodeType* P2=SoB;
	int sonho=0;
	int continunei=0;
	for(int i=0;i<maxlen;i++)
	{
		int a=0;
		int b=0;
		int tong=0;
		
		if(P1!=NULL)
		{
			a=P1->data;
		}
		if(P2!=NULL)
		{
			b=P2->data;
		}
		
		tong=a+b+sonho;
		if(tong>=10)
		{
			sonho=(int)tong/10;
			tong=tong%10;
		}
		else
		{
			sonho=0;
		}

		//cout<<tong;
		ketqua[i]=tong;
		if(P1!=NULL)
		{
			P1=P1->next;
		}

		if(P2!=NULL)
		{
			P2=P2->next;
		}
		continunei=i;
	}

	if(sonho>0)
	{
		//cout<<sonho;
		continunei=continunei+1;
		ketqua[continunei]=sonho;
	}
	
	//cout<<"continunei="<<continunei<<endl;
	
	for(int y=continunei;y>=0; y--)
	{
		cout<<ketqua[y];
	}
}


int main()
{
	printf("===CHUONG TRINH CONG HAI SO NGUYEN CO NHIEU CHU SO [UNG DUNG DANH SACH LIEN KET]===");
	NodeType* Songuyen1 = NULL; //Khởi tạo cây chứa các chữ số của số nguyên thứ nhất
	NodeType* Songuyen2 = NULL; //Khởi tạo cây chứa các chữ số của số nguyên thứ hai
	clrscr();
	char sothu1[100],sothu2[100];

	printf("Nhap so thu 1: ");
	scanf("%s",&sothu1);
	
	int i=0;
	int len1=strlen(sothu1);
	//printf("\nDo dai so thu 1: %d",len1);
	for(i=len1-1;i>=0;i--)
	{
		int so=(int)sothu1[i]-48;
		Insert(Songuyen1,so);
	}
	//printf("List so thu 1: \n");
	//PrintList(Songuyen1);


	printf("Nhap so thu 2: ");
	scanf("%s",&sothu2);
	
	i=0;
	int len2=strlen(sothu2);
	//printf("\nDo dai so thu 2: %d",len2);
	for(i=len2-1;i>=0;i--)
	{
		int so=(int)sothu2[i]-48;
		Insert(Songuyen2,so);
	}
	//printf("List so thu 2: \n");
	//PrintList(Songuyen2);
	
	int maxlen=0;
	if(len1>len2)
	{
		maxlen=len1;
	}
	else
	{
		maxlen=len2;
	}
	
	cout<<sothu1<<" + "<<sothu2<<" = ";
	InTong(Songuyen1,Songuyen2,maxlen);
	getch();
	
 return 0;
}

Hy vọng hữu ích với bạn!

Nosomovo