Tập huấn Sở GD-ĐT 2010

Chuyên đề
Các phép tính với số lớn trong NNLT Pascal.
( VVSửu., GV Trường THPT chuyên HN-AMSTERDAM)

Đặt vấn đề.

Do hạn chế về bộ nhớ, nên các phép toán cộng, trừ, nhân, chia trong NNLT pascal chỉ thực hiện được đối với các số nhỏ. Trong lúc đó nhiều bài toán cần thực hiện phép toán với hàng trăm, thậm chí hàng ngàn chữ số. Chúng ta sẽ sử dụng một vài cấu trúc dữ liệu như xâu, mảng và các thuật toán đã học từ thời THCS để thực hiện yêu cầu tính toán đối với các số lớn.

II. Các bài toán cơ bản

Bài toán 1. Cộng 2 số lớn.


Input: Cho S1, S2 là 2 số nguyên dương, mỗi số có số chữ số <=200 (nhập dưới dạng xâu)
Output: S1+S2.
Thuật toán:
Tạo các thủ tục :
+procedure DOI (S:string, Var a :mang);
{ đổi các kí tự số từ S thành các số tương ứng trong mảng a (với thứ tự ngựợc lại)}
Var n, i, cod: integer;
Begin
n:=length(S);
For i:= n downto 1 do
Begin
val(s[i],a[n-i],cod)
End ;
+Procedure CONG (a,b: mang; var c:mang);
Var nho, tg: integer;
Begin
Nho:=0;
For i:= 0 to 300 do
Begin
Tg:=a[i]+b[i]+ nho;
c[i]:=tg mod 10;
nho:=tg div 10;
End;
End;
+ procedure INKQ (c:mang);
Var sc,i: integer;
Begin
For sc :=300 downto 0 do if c[sc]<>0 then break;
For i:=sc downto 0 do write(c[i]);
End;
Begin {main}
READLN( S1, S2);
DOI(S1,a);
DOI(S2,b);
CONG (a,b,c);
INKQ(c);
End.

Bài toán 2. Hiệu 2 số lớn.

Input : S1, S2 Xâu biểu diễn số (giả thiết s1≥ s2)
Output : S1- S2.
Begin
Readln(S1, S2);
DOI(s1,a); DOI(s2,b);
TRU(a,b,h);
INKQ(h);
End.
Procedure TRU(a,b:mang;var h:mang);
Var
Begin
Muon:=0;
For i:=0 to 300 do
Begin
b[i]:=b[i]+muon;
If a[i]>=b[i] then begin h[i]:=a[i]-b[i]; muon:=0;end
Else
Begin
muon:=1;
h[i]:=10+a[i]-b[i];
End;
End;

Bài 3. So sánh 2 số lớn.

Input: S1, S2 2 số có số chữ số <=200.
Output: sắp xếp lại 2 xâu để S1>=S2.
Prorcedure sosanh(X,Y: string; Var biger, equal, less: Boolean);
Begin
biger:=false; equal:=false; less:=false; nx:=length(X); ny:=length(Y);
If X=Y then equal:=true
Else if nx> ny then biger:=true
Else if ny> nx then less:=true
Else
Begin
i:=0;
While (X[i+1]=Y[i+1]) and (i If i=nx then equal:=true;
Else if X[i]>Y[i] then Biger:=true
Else less:=true;
End;
End;
Begin{ Main}
READLN (S1,S2);
SOSANH(S,S2,big, eq,les);
If les then begin tg:=S1; s1:=s2