Bài toán xử lý số siêu lớn
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (69.88 KB, 3 trang )
Một ý tưởng cho bài toán xử lý số siêu lớn
Hải Minh- Trịnh Hải
Khi viết chương trình bằng một ngôn ngữ lập trình, ta thường phải sử dụng bộ dữ liệu
chuẩn của ngôn ngữ đó mà đã được định nghĩa trước. Với bộ dữ liệu chuẩn dành cho dữ
liệu kiểu số thì có đặc điểm là sẽ bị giới hạn về phạm vị biểu diễn. Một trong những cách
để ta khắc phục tình trạng này là ta sẽ chuyển số sang dạng xâu và thực hiện các phép toán
trên từng số hạng xâu đó. Nhưng làm theo cách này thì ta cũng mới chỉ biểu diễn được số
có tối đa là 255 chữ số muốn tăng khả năng biểu diễn lên ta cần phải khai báo nhiều biến
kiểu xâu.
Trong bài viết này, chúng tôi xin giới thiệu một cách xử lý số lớn nhưng dữ liệu được tổ
chức theo kiểu mảng mỗi phần tử của mảng có kiểu dữ liệu là kiểu Byte mà 1 Byte sẽ mô
tả được hai chữ số của số lớn. Cụ thể: giả sử ta có số 15 và 50 thì ta sẽ được mô tả 4 bit
cao lưu trữ hàng chục, 4 bít thấp lưu hàng đơn vị:
Khi đó thì để tách chữ số phần được lưu ở phần bit thấp ta sẽ thực hiện phép toán logic và
(And) với $0F, để tách chữ số lưu phần bít cao ta thực hiện phép dịch sang phải 4 bit (Shr).
Bằng cách này chúng tôi xây dựng chương trình nhập và tính tổng hai số siêu lớn bằng
ngôn ngữ Pascal.
Uses Crt;
Const
NumMax=512;
Type
Numbers=Array[0..NumMax] Of Byte;
Var
So1,So2,Tong:Numbers;
Procedure Input(Var A:Numbers);
Var
i,j,Code:Integer;
Num: Char;
NTmp:Array[0..NumMax*2] Of Byte;
Begin
Writeln('Nhap vao so that lon');
i:=0;
FillChar(A,SizeOf(a),0);
Repeat
Num:=Readkey;
If Num in ['0'..'9'] Then
Begin
Write(Num);
Val(Num,NTmp[i],Code);
I:=i+1;
End;
Until Ord(Num)=13;
i:=i-1;j:=NumMax;
While i>=0 do
Begin
A[j]:=NTmp[i]+(NTmp[i-1] shl 4);
i:=i-2;
j:=j-1;
End;
Writeln;
End;
Procedure WriteNumber(A:Numbers);
Var
i,j:Integer;
HN,LN:Byte;
Begin
i:=0;
While (i<=NumMax) And (A[i]=0) do i:=i+1;
If i<=NumMax Then
Begin
For j:=i to NumMax do
Begin
LN:=A[j] And $0F;
HN:=A[j] shr 4;
Write(HN,LN);
End;
End
Else Write(0);
Writeln;
End;
Procedure AđAB(A,B:NumBers;Var C:Numbers);
Var
i:integer;
LN,HN,TL,TH:Byte;
Begin
FillChar(C,SizeOf(C),0);
For i:=NumMax Downto 1 do
Begin
LN:=(A[i] and $0F) + (B[i] and $0F) +TH;
Tl:=LN div 10;
LN:=LN Mod 10;
HN:=(A[i] Shr 4) + (B[i] Shr 4) +TL;
TH:=HN div 10;
HN:=HN Mod 10;
HN:=HN shl 4;
C[i]:=(LN+HN);
End;
End;
Begin
input(So1);
input(So2);
AđAB(So1,So2,Tong);
Writeln('Tong ');
WriteNumber(Tong);
Readln;
End.
