PHẦN I. ĐẶT VẤN ĐỀ
1. Lý do chọn đề tài
Trong quá trình đào tạo bồi dưỡng học sinh giỏi ở trường phổ thông, chúng tôi
nhận thấy khả năng số học đối với số nguyên lớn của ngôn ngữ lập trình Free Pascal
khi biểu diễn các số nguyên có hàng chục nghìn chữ số đến hàng trăm nghìn chữ số
gây rất nhiều khó khăn cho học sinh. Nhằm khắc phục nhược điểm trên và để đáp ứng
được yêu cầu của công tác bồi dưỡng học sinh giỏi của thầy và trò trường trung học
phổ thông Vinh Xuân, chúng tôi mạnh dạn nghiên cứu đề tài “KĨ THUẬT LẬP
TRÌNH ĐỐI VỚI SỐ NGUYÊN LỚN TRONG CÔNG TÁC BỒI DƯỠNG HỌC
SINH GIỎI TẠI TRƯỜNG TRUNG HỌC PHỔ THÔNG VINH XUÂN” nhằm phục
vụ công tác bồi dưỡng học sinh giỏi có hiệu quả hơn.

2. Mục đích nghiên cứu
- Hệ thống hóa cơ sở lý thuyết về lập trình đối với số nguyên lớn.
- Xây dựng bộ công cụ lập trình đối với số nguyên lớn nhằm hỗ trợ cho hoạt động
dạy và học của thầy và trò của nhà trường trong quá trình tiếp xúc và làm việc với số
nguyên lớn.
- Trên cơ sở nghiên cứu, từ đó đưa ra nhận xét, đánh giá và đề xuất giải pháp góp
phần hoàn thiện công tác dạy và học lập trình đối với các bài toán mà dữ liệu vào hay
kết quả ra có giá trị nguyên dương rất lớn.

3. Đối tượng nghiên cứu
Kỹ thuật lập trình đối với số nguyên lớn trong công tác dạy và học bồi dưỡng của
thầy và trò tại trường THPT Vinh Xuân.

4. Phạm vi nghiên cứu
Tập hợp số nguyên dương lớn và hệ thống bài tập có dữ liệu vào hay kết quả ra là
kiểu số nguyên dương có giá trị rất lớn.

5. Phương pháp nghiên cứu
- Phương pháp nghiên cứu cơ sở lý luận

Type Big_Number = Array[0..Hang_so] of Longint;
Var

A: Big_Number;

trong đó:
+ Chữ số hàng đơn vị của số nguyên lớn được biểu diễn bởi phần tử
A[1.000.000]
+ Chữ số hàng chục của số nguyên lớn được biểu diễn bởi phần tử A[999.999]
+ ………..
+ Chữ số hàng cao nhất của số nguyên lớn được biểu diễn bởi phần tử A[i] và
giá trị i được quản lý bởi giá trị của phần tử A[0].
Với số nguyên lớn A = 876328 được biểu diễn trên các phần tử mảng và quản lý
giá trị A[0] như sau:

A

999.995

0

0

0

0

8

7


Với A := 0 được viết:
Fillchar(A, Sizeof(A),0); A[0]:= Hang_So;
Với A := 1 được viết:
Fillchar(A,Sizeof(A),0);
A[0]:= Hang_So; A[Hang_so]:=1;

3


Trên cơ sở biểu diễn số nguyên lớn như vậy, chúng tôi xây dựng các phép toán trên
tập hợp số nguyên dương lớn như phép toán quan hệ, phép toán cộng, phép trừ, phép
nhân, phép chia lấy phần nguyên (Div), phép chia lấy phần dư (Mod) và ứng dụng các
phép toán đó để giải quyết một số bài toán trong công tác bồi dưỡng học sinh giỏi.

1.2. PHÉP TOÁN QUAN HỆ
1.2.1. Phép toán so sánh bằng
* Thuật toán: Hai số nguyên dương lớn A B kiểu Big_number được biểu diễn
bằng mảng một chiều, mỗi phần tử mảng biểu diễn một chữ số của số nguyên lớn. Ta
dựa vào các giá trị A0, B0, Ai với A0 ≤ i ≤ Hang_so và Bk với B0 ≤ k ≤ Hang_so để thực
hiện so sánh và trả về giá trị True hoặc False.
Function Bằng(A,B:Big_number): Boolean
Begin
Nếu A0 B0 thì Bằng:=false
Ngược lại
{ + i:= A0; Trong khi (i ≤ Hang_so) và (Ai = Bi) làm i:= i+1;
+ Bằng:= i > Hang_so;}
End;
* Chương trình
Function Bang(A,B:Big_Number):Boolean;

Function Lon_Hon(A,B:Big_Number):Boolean;
Var

I:Longint;

Begin
If A[0]B[0] Then Lon_Hon:=False
Else Begin
I:=A[0]; While (IHang_So Then Lon_Hon:=False
Else Lon_Hon:=A[I]>B[I];
End;
End;
1.2.3. Phép toán so sánh nhỏ hơn
* Thuật toán: So sánh hai số A, B: Big_Number; nếu A nhỏ hơn B thì trả về kết
quả True nếu không thì trả về giá trị False.
Function Nhỏ_hơn(A,B:Big_number):Boolean
Begin
* Nếu A0 < B0 thì Lớn_hơn:= False
Ngược lại
- Nếu A0 > B0 thì Lớn_hơn:= True
Ngược lại
5


{ + i:= A0;
+ Trong khi (i Hang_so thì Lớn_hơn:= False
ngược lại i:= Ai
6


* Chương trình
Procedure Cong_Min(Var C:Big_Number; A:Big_Number; k:Longint);
Var

I: Longint;

Begin
Fillchar(C,Sizeof(C),0);
For I:=Hang_So Downto A[0] Do
Begin K:=K+A[I]; C[I]:=K Mod 10; K:= K Div 10; End;
While K>0 Do Begin I:=I-1;C[I]:=K Mod 10;K:=K Div 10; End;
C[0]:=I;
End;
1.3.1.2. Cộng hai số nguyên lớn
* Thuật toán: Phép cộng hai số nguyên dương lớn được thực hiện từ phải sang trái
và phần nhớ được mang sang trái một chữ số.
Procedure Cong_Max(Var C:Big_Number;A,B:Big_Number);
Begin
Fillchar(C,sizeof(C),0); Tg:= 0;
Cho i:= Hang_so về Min(A0, B0) làm
{Tg:= Tg + Ai + Bi; Ci:= Tg Mod 10; Tg:= Tg Div 10}
Nếu Tg = 0 thì C0:= i Ngược lại {C0:= i -1; Ci-1:= Tg}
End;
* Chương trình
Procedure Cong_Max(Var C:Big_Number;A,B:Big_Number);
Var


Biểu diễn giá trị k vào mảng C kiểu Big_number;
C[c0]:= - C[c0]
End;
* Chương trình
Procedure Tru_Min(Var C:Big_Number;A:Big_Number;K:Longint);
Var

I,M,Tg,Lt: Longint;

Begin
Fillchar(C,Sizeof(C),0); C[0]:=Hang_So; Tg:=0; I:=Hang_So; M:=K;
While (K>0) And (I>=A[0]) Do
Begin
Tg:=K Mod 10; K:=K Div 10;
If A[I]>=Tg Then C[I]:=A[I]-Tg
Else Begin C[I]:=A[I]+10-Tg; K:=K+1; End;
I:=I-1;
End;
8


If K=0 Then
Begin
While I>=A[0] Do Begin C[I]:=A[I]; I:=I-1; End;
I:=A[0]; While (I

Tg:= 0;
Cho i:= Hang_so về B0 làm
Nếu Bi ≥ Tg + Ai thì {Ci:= Bi – Ai – Tg; Tg:= 0;}
Ngược lại {Ci:= Bi + 10 – Ci – Tg; Tg:= 1;}
Trong khi (i< Hang_so) và (Ci = 0) làm i:= i+1;
C0:= i; Ci:= 1 – Ci}

End;
* Chương trình
Procedure Tru_Max(Var C:Big_Number;A,B:Big_Number);
Var

I,Tg:Longint; Ok:Boolean;

Begin
Fillchar(C,Sizeof(C),0);
If A[0]B[0] Then Ok:=False
Else Begin
I:=A[0];While (IHang_So Then Ok:=False Else Ok:=A[I]>B[I];
End;
If Ok Then
Begin
Tg:=0;
For I:=Hang_So Downto A[0] Do
If A[I]>=B[I]+Tg Then
Begin C[I]:=A[I]-B[I]-Tg; Tg:=0 End
Else Begin C[I]:=A[I]+10 - B[I] - Tg; Tg:=1; End;

Procedure Nhan_Min(Var C:Big_Number;A:Big_Number;K:Longint);
Var

I, Tg,Schia,Min:Longint;

Begin
Fillchar(C,Sizeof(C),0);Tg:=0;
For I:=Hang_So Downto A[0] Do
Begin Tg:=Tg+A[I]*K; C[I]:=Tg Mod 10; Tg:=Tg Div 10; End;
While Tg>0 Do Begin I:=I-1; C[I]:=Tg Mod 10; Tg:=Tg Div 10; End;
C[0]:=I;
End;

11


1.3.3.2. Nhân hai số nguyên lớn
* Thuật toán: Thực hiện nhân từ phải sang trái các chữ số A i với số nguyên lớn B
được tích bằng D; ứng với mỗi giá trị D được cộng dồn vào cho C và kết thúc khi i =
A0; suy ra được kết quả bằng số nguyên lớn C.
Procedure Nhan_Max(Var C:Big_Number;A,B:Big_Number);
Begin
C:=0;
Cho i:= Hang_so về A0 làm {D:= Ai * B* 10Hang_so – i; C:= C + D;}
End;
* Chương trình
Procedure Nhan_Max(Var C:Big_Number;A,B:Big_Number);
Var

I,J,U,Tg: Longint; D: Big_Number;

Procedure Div_Min(Var C:Big_Number;A:Big_Number;K:Longint);
Begin
C:= 0; Tg:= 0;
Cho A0 đến Hang_so làm
{Tg:=10*Tg+Ai; Ci:= Tg Div 10; Tg:= Tg Mod 10}
i:=A0; Trong khi (i
Repeat
Tg:=0;
If A[0]B[0] Then Ok:=True
Else Begin
I:=A[0];Tg:=A[I];
While I
End;
Until Ok;
If A[0]B[0] Then Ok:=False
Else Begin
I:=A[0]; While (IHang_So Then Ok:=True Else Ok:=A[I]>=B[I];
End;
If Ok Then
Begin
Tg:=1;
For I:= Hang_So Downto C[0] Do
Begin Tg:=Tg+C[I]; C[I]:=Tg Mod 10; Tg:=Tg Div 10; End;
If Tg >0 Then Begin C[0]:= C[0]-1; C[C[0]]:=Tg; End;
End;
End;

16


1.3.4.2. Chia lấy phần dư (Mod)
1.3.4.2.1. Số nguyên lớn chia số nguyên nhỏ
* Thuật toán: Thực hiện trừ trái sang phải, lấy các giá trị A i chia cho giá trị k phần
dư nhân 10 cộng với Ai+1 rồi chia k cho đến khi kết thúc ta thu được phần dư cần tìm.
Procedure Mod_Min(Var C:longint;A:Big_Number;K:Longint);
Begin
C:=0; Cho i:= A0 đến Hang_so làm {C:=(10*C+Ai) Mod k;
End;
* Chương trình
Procedure Mod_Min(Var C:longint;A:Big_Number;K:Longint);


While I
While (I
Program GIAI_THUA;
Const

Hang_So = 1000000;
20


Type

Big_Number = Array[0..Hang_So] Of Longint;

Var

A: Big_Number; I, M: Longint; F1, F2: Text;

{========================}
Procedure Nhan_Min(Var C: Big_Number; A: Big_Number; K: Longint);
Var

I, Tg: Longint;

Begin
Tg:= 0;
For I:= Hang_So Downto A[0] Do
Begin Tg:= Tg + A[I] * K; C[I]:= Tg Mod 10000; Tg:= Tg Div 10000;
End;
While Tg>0 Do Begin I:=I-1; C[I]:= Tg Mod 10000; Tg:= Tg Div 10000;
End;
C[0]:= I;
End;


b

2

…

…

z

26

aa

27

ab

28

…

…

snowfall

157.118.051.752

…


51.346.529.199.396.181.750

prestidigitation

28.011.622.636.823.854.456.520

computationally

232.049.592.627.851.629.097

zzzzzzzzzzzzzzzzzzzz
20.725.274.851.017.785.518.433.805.270
2. Cấu trúc dữ liệu và giải thuật
* Cấu trúc dữ liệu:
- Xây dựng mảng một chiều kiểu Big_Number để tổ chức lưu trữ số nguyên lớn
của bài toán và được khai báo như ở phần lý thuyết.
- Xây dựng thủ tục Tru_1(Var A: Big_Number): A:= A - 1 được thực hiện khi A
chia hết cho 26.
- Sử dụng các thủ tục sau:
+ Cong_Max(A,B,C): A:= B + C với A, B, C kiểu Big_Number.
+ Nhan_Min(A,B,k): A:= B * k với A, B kiểu Big_Number và k kiểu Longint.
+ Mod_Min(c,A,k): C:= A Mod k với A kiểu Big_Number và c, k kiểu Longint.
+ Div_Min(A,B,k): A:= B Div k với A, B kiểu Big_Number và k kiểu Longint.
* Giải thuật:
- Xây dựng thủ tục mã hóa để mã hóa một từ thành một số:
Procedure Ma_Hoa(St: một từ để biểu diễn thành số);
Begin
A0:= Hang_So - Length(St) + 1
AHang_So + i - Length(St) := Ord(Sti) - 96; với mọi i =1 .. Length(St)

Ghi file(F2, S:20, St:45);
End;
- Chương trình chính
BEGIN
Trong khi Not Eof(F1) làm:
+ Readln(F1, St);
+ Nếu St1
Begin Tg:= 10 * Tg + A[I]; C[I]:= Tg Div K; Tg:= Tg Mod K; End;
I:= A[0]; While (I