Chuyên đề các phép tính với số lớn trong ngôn ngữ lập trình pascal

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<nx) do inc(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; s2:=tg; end;
 INKQ(S1, S2);
End.
Bài 4 Nhân một số lớn với một số nguyên dương ( trong pv máy tính)
Input : S - Xâu biểu diễn số lớn , n –số nguyên dương.
Output: S.n
BEGIN
Nhập S, nhập n
DOI(S,a){ doi xâu số S thành mảng a[0],, a[n])
NHAN(a,n,T) { nhân a với n cho mảng tích T}
GHIKQ(T);
END.
PROCEDURE NHAN(a:mang; n:integer; Var T:mang);
Var
Begin
Fillchar(T,sizeof(T),0);
Nho:=0; Tg:=0;
For i:=0 to 300 do
 Begin
 Tg:=a[i]*n +nho;
 T[i]:= Tg mod 10;
 Nho:=tg div 10
 End;
End;
Bài 5. Nhân 2 số lớn.
Input: 2 số S1, S2.
Output S1.S2.
Thuật toán:
+ Khai báo các mảng các byte: TG, KQ,a,b
+ DOI(S1,a); DOI(S2,b);
+ for i:=0 to 300 do 
 Begin
 Nhan(a, b[i],TG); 
 For j:= 0 to 300 do CONG( TG, KQ, i);
 End;
+ INKQ;
+ cài đặt 
 Procedure CONG(TG: mang; var KQ: mang; i: integer);
 Var nho, t: integer;
 Begin
 Nho:=0; t:=0;
 For j:=0 to 300 do
 Begin
 t:=KQ[j+i]+TG[j]+nho;
 KQ[j+i]:= t mod 10;
 nho:= t div 10;
 End;
 End;
III. Các bài toán ứng dụng.
Bài 1. Giai thừa.
Input : n nguyên dương n<=200.
Output:Tính giai thừa n!.
Thuật toán:
 + Khai báo mảng : GT[0..1000] of byte { chứa kết quả};
 + Khởi tạo a[0]:=1
 + For i:=1 to n do NHAN(i, a); {Chú ý đầu tiên khởi tạo a[0]:=1}
 + GHIKQ
Bài 2. Tổng luỹ thừa.
Tính Pn+Qm. (P,Q ,m , n nguyên dương<=200)
Thuật toán: 
+ Xây dung thủ tục PROCEDURE LT(K, n: integer, var A:mang); {nâng K lên luỹ thừa n, kết quả ghi vào mảng A}
For i:=1 to n do NHAN( K,a) {chú ý đầu tiên khởi tạo a[0]:=1}
+ Gọi thủ tuc LT(P,n,A), LT(Q.m,B)
+Gọi thủ tuc CONG(A, B, C);
+ Ghi C.
Bài 3. Ghép HCN
 Input: a , b, c , d , với a,b,c,d nguyên dương là kích thước 2 hình chữ nhật a x b và c x d . Hỏi từ 2 hcn đó có thể ghép được thành một hcn Output : 2 hcn đó có thể ghép được thành một hcn khác. Nếu ghép được cho biết chu vi lớn nhất có thể. 
Bài 4. BCNN
Cho dãy số nguyên dương a1, a2, a3,, an (n<=10000, 0<ai<109).
Tìm BCNN(a1,a2,,an) (Đề thi HSG Hà nội 2010)
Thuật toán:
+ Xét dãy các số nguyên tố trong khoảng tứ 2 đến n:
 Snt:=0; 
 For p:=2 to n do 
 If OK (P) then {if P nguyên tô}
 Begin
 Inc(snt) 
 NT[snt]:=p;
+ Xét dãy số mũ max của số nguyên tố NT[i] là ước của a1,a2,..
 Khởi tạo Mmax[i]:=0;(i=1..snt)
+ for i:= 1 to n do {xét a1, a2,}
 Begin
 Tg:=a[i];
 For j:= 1 to snt do
 Begin
 mm:=0
 While tg mod nt[j] =0 do
 Begin
 Tg:= tg div nt[j];
 Inc(mm)
 End;
 If mm>mmax[j] then mmax[j]:=mm;
 End;
 End;
 + Gọi mảng bc[0], bc[1],,,bc[300] là BCNN (ghi theo tt ngược)
 +Khởi tao bc[0]:=1
 + 
 For i:=1 to snt do 
 If mmax[i]>0 then
 For j:= 1 to mmax[i] do nhan (bc, nt[i])
 + GHI gọi nbc: chỉ số khác không cuối cùng của bc.
For nbc:=300 downto 0 do if bc[nbc]0 then break;
For i:= nbc downto 0 do write(BC[I]);
End.