Xử lý dữ liệu lớn trong một số bài toán tin
MỤC LỤC
Tên đề mục Trang
Phần I: Phần mở đầu 1
Danh mục viết tắt 2
1. Lí do chọn đề tài 3
2. Mục đích của đề tài 4
3. Nhiệm vụ nghiên cứu 4
4. Đối tượng nghiên cứu 4
5. Phương pháp nghiên cứu 4
6. Không gian của đối tượng nghiên cứu 4
7. Phạm vi và kế hoạch nghiên cứu 4
Phần II: Nội dung 5
1. Cơ sở lí luận của đề tài 5
2. Cơ sở thực tiễn 8
3. Giải pháp mới, sáng tạo 8
4. Kết quả nghiên cứu 23
5. Ứng dụng vào thực tiễn công tác giảng dạy 23
5.1. Quá trình áp dụng của bản thân 23
5.2. Bài học kinh nghiệm 23
Phần III: Kết luận và kiến nghị 24
1. Kết luận 24
2. Kiến nghị 24
Người thực hiện: Nguyễn Khải Hoàn
1
Xử lý dữ liệu lớn trong một số bài toán tin
DANH MỤC CÁC TỪ VIẾT TẮT
Stt Tên diễn giải Viết tắt
1 Trường THCS THCS
2 Trường THPT THPT
3 Turbo Pascal TP

4 Free Pascal FC
Người thực hiện: Nguyễn Khải Hoàn
2
Xử lý dữ liệu lớn trong một số bài toán tin
Phần I: ĐẶT VẤN ĐỀ
1. Lý do chọn đề tài
Trong những năm gần đây ngành giáo dục và đào tạo là tiêu điểm của
sự quan tâm, chú ý của xã hội. Việc nâng cao chất lượng giáo dục là vấn đề
không chỉ của ngành giáo dục mà còn được toàn xã hội quan tâm đặc biệt
qua các kỳ đại hội Đảng, các kì họp Quốc hội. " Đổi mới căn bản và toàn
diện ngành giáo dục" là vấn đề cấp thiết của ngành giáo dục để từng bước
nâng cao chất lượng giáo dục. Chính vì lẽ đó mà nó là một phần quan trọng
trong chủ đề của nhiều năm học. Để nâng cao chất lượng giáo dục cần đầu
tư nâng cao chất lượng đại trà bằng nhiều phương pháp, song đầu tư cho
chất lượng mũi nhọn để phát hiện, chọn lựa và bồi dưỡng học sinh giỏi
cũng là một vấn đề hết sức quan trọng.
Bồi dưỡng học sinh giỏi là nhiệm vụ khó không chỉ từ việc lựa chọn học
sinh, lựa chọn phương pháp mà vì nó đòi hỏi nhiều kiến thức, kĩ năng vận dụng
cao, đề thi tập trung khai thác sâu kiến thức không chỉ ở cấp học THCS mà còn
cả ở cấp THPT, thậm chí cả đề thi Đại học, đề thi học sinh giỏi cấp THPT, cấp
Quốc gia. Riêng môn tin học là một bộ môn rất mới được đưa vào trường THCS
và đa số trang thiết bị tin học tại các nhà trường còn hạn chế cho nên việc tiếp
cận, giảng dạy, học tập bộ môn này của giáo viên và học sinh còn rất nhiều khó
khăn. Với việc giáo dục đại trà bộ môn Tin học còn vất vả và khó khăn thì công
tác phát hiện, bồi dưỡng đối tượng học sinh giỏi ở bộ môn này còn gặp nhiều
khó khăn hơn nữa. Trên tài nguyên mạng hay tài liệu đã có nhiều phương pháp
sử lý, giải bài toán tin được giáo viên và học sinh sử dụng khi bồi dưỡng học
sinh giỏi như: Các phương pháp giải bài toán tin, các phương pháp sử lý dữ liệu
kiểu số, kiểu xâu; Các chuyên đề duyệt, sử lý thuật toán…
Qua việc tham khảo những đề thi học sinh giỏi gần đây đặc biệt là các

cuộc thi học sinh giỏi lớp 9 cấp tỉnh thì xu hướng sử dụng các đề thi sử lý, tính
toán với dữ liệu lớn vượt qua giới hạn các kiểu số Real, Longint của Pascal hay
Int32, Int64 của Free Pascal với các số có hàng chục, hàng trăm con số ngày
càng áp dụng rộng rãi. Với ưu điểm dùng được cho các bài toán phức tạp xảy ra
qua nhiều quá trình tính toán, phát huy tối đa khả năng tư duy, vận dụng kiến
thức toán học phải tốt mới có thể sử lý quét hết các trường hợp của bài toán.
Điều đặc biệt lý thú của những dạng bài toán này là có những bài toán không
cần phải có cấu trúc lập trình phức tạp, hay ghe ghớm gì lắm, code của chương
trình ngắn thậm chí chỉ cần vài dòng code là có thể sử lý bài toán một cách hiệu
quả… nên được đưa vào trong nhiều đề thi chọn học sinh giỏi các cấp, các khối
học không chỉ đối với học sinh giỏi Tin học lớp 9.
Chính vì vậy tôi mạnh dạn nghiên cứu và đưa vào chương trình bồi dưỡng
học sinh giỏi bộ môn Tin học cấp THCS chuyên đề: “Xử lý dữ liệu lớn trong
một số bài toán tin”
Người thực hiện: Nguyễn Khải Hoàn
3
Xử lý dữ liệu lớn trong một số bài toán tin
2. Mục đích của đề tài
Phân dạng các bài toán tin học có liên quan đến việc sử lý dữ liệu lớn, rất
lớn nhằm nâng cao chất lượng học sinh giỏi
3. Nhiệm vụ nghiên cứu.
- Nêu lên được cơ sở lý luận của chuyên đề.
- Tiến hành điều tra tình hình nắm vững kiến thức cơ bản của học sinh
giỏi.
- Hệ thống bài toán Tin học theo từng dạng.
- Qua bài tập giúp các em tích cực, chủ động chiếm lĩnh tri thức rèn luyện kĩ
năng.
4. Đối tượng nghiên cứu:
Học sinh giỏi lớp 9
5. Phương pháp nghiên cứu.

Trong đề tài này tôi đã vận dụng các phương pháp nghiên cứu khoa học
như: Phân tích lý thuyết, tổng kết kinh nghiệm sư phạm. Tham khảo các tài liệu
lấy từ nhiều nguồn nhất là các học liệu mở trên mạng thông tin Internet và phân
tích một cách có hệ thống các dạng bài toán theo nội dung đã đề ra.
Trên cơ sở đó tôi đã trình bày các dạng bài toán tin học đã sưu tầm và
nghiên cứu để nâng cao khả năng, trí tuệ của học sinh.
6. Giới hạn về không gian của đối tượng: Trường THCS Thái Hòa
7. Phạm vi và kế hoạch nghiên cứu
- Đối tượng: học sinh lớp 9
- Dự kiến số tiết bồi dưỡng: 9 tiết
Người thực hiện: Nguyễn Khải Hoàn
4
Xử lý dữ liệu lớn trong một số bài toán tin
Phần II: NỘI DUNG
1. Cơ sở lý luận của đề tài:
1.1. Dữ liệu kiểu số và độ lớn của dữ liệu kiểu số:
- Dữ liệu kiểu số là một dạng dữ liệu sử dụng để tính toán trong lập trình
đối với mỗi ngôn ngữ lập trình thì kiểu số được định nghĩa, giới hạn của nó có
sự khác nhau. Trong phạm vi chuyên đề này tôi xin đưa ra dữ liệu kiểu số của
ngôn ngữ lập trình Pascal và Free Pascal, đối với Free Pascal thì độ lớn dữ liệu
kiểu số lớn hơn Pascal có thể đảm bảo yêu cầu của một số bài toán.
- Với Pascal ta có 2 kiểu số là số thực và số nguyên thường được sử dụng
như bảng sau:
Stt Tên
Loại giá
trị
Phạm vi
Độ lớn
Byte
1 Real Số thực 2,9.10

-39
1,7.10
38
6
2 Single Số thực 1,5.10
-45
3,4.10
38
4
3 Double Số thực 5,0.10
-324
1,7.10
308
8
4 Extended Số thực 3,4.10
-4932
1,1.10
4932
10
5 Comp Số thực 9,2.10
-18
9,2.10
18
8
6 Currency Số thực -2.10
64+1
2.10
63-1
8
7 Shortint Nguyên -128 127 1

8 Integer Nguyên -32768 32767 2
9 Longint Nguyên -2147483648 2147483647 4
10 Byte Nguyên 0 255 1
11 Word Nguyên 0 65535 2
- Với Free Pascal ngoài kiểu dữ liệu có độ lớn như bảng trên ta còn có
thêm hai kiểu dữ liệu như sau:
Stt Tên Loại giá trị Phạm vi Độ lớn
Byte
1 Int64 Nguyên -2.10
63
2.10
63-1
6
2 Qword Nguyên 0 2.10
64-1
6
1.2. Các phép toán với kiểu dữ liệu này
Sử dụng các phép toán số học thuần thúy:
Stt Tên phép toán Ký hiệu
1 Cộng +
2 Trừ -
Người thực hiện: Nguyễn Khải Hoàn
5
Xử lý dữ liệu lớn trong một số bài toán tin
3 Nhân *
4 Chia /
5 Chia lấy nguyên Div
6 Chia lấy dư Mod
Với dữ liệu không lớn thì sử lý bình thường là có thể vét hết các Test của
bài toán, nhưng khi dữ liệu lớn thì kết quả của các phép tình trên sẽ cho ra một

số liệu tương đối lớn đa số vượt quá giới hạn cho phép của ngôn ngữ lập trình ở
đây tôi nói đến Free Pascal là độ lớn dữ liệu là lớn nhất.
Vấn đề đặt ra ở đây là làm thế nào để sử lý những bài toán đó, ta có thể sử
dụng một trong các phương pháp sau:
* Tối ưu quá trình tính toán: Áp dụng kiến thức toán học thông thường
để giải quyết bài toán
* Sử dụng dữ liệu kiểu xâu: Để biểu diễn số và lưu kết quả tính toán,
trong Free Pascal thì dữ liệu kiểu xâu ký tự không hạn chế độ dài nên ta có thể
sử lý những con số rất lớn đến hàng trăm, hàng nghìn chữ số.
1.3.Áp dụng các phương pháp này:
1.3.1: Tối ưu hóa quá trình tính toán.
- Phương pháp này ta vận dụng hết khả năng toán học vào để từ bài toán
sử lý số rất lớn sang sử lý nhiều bài toán có độ lớn dữ liệu nhỏ hơn, đảm bảo
không bị tràn dữ liệu, vét hết các khả năng của bài toán.
- Ví dụ: Đề thi HSG Tin học lớp 9 năm học 2013-2014 của tỉnh Vĩnh
Phúc bài số 2 đếm số hình vuông
Ở bài này sau khi phân tích ta rút ra được công thức tổng quát để tính số
hình vuông là:
( 1)(2 1)
6
n n n
S
+ +
=
sau đó lấy tổng này chia cho 2013 để lấy số dư.
Nếu thuần thúy thì cứ công thức ta thực hiện được phép toán, nhưng vấn đề ở
đây là
18
10n ≤
cho nên tích trên đã vượt khỏi độ lớn dữ liệu và bị tràn bộ nhớ.

Với toán học ta sử lý tích trên rất đơn giản theo hai vấn đề sau:
- Vấn đề 1: Sử lý nội hàm tích S=n(n+1)(2n+1), tích này luôn luôn chia
hết cho 6 bằng cách ta xét tính chia hết của từng phần tử trong tích cho 2 và 3,
nếu một phần tử nào chia hết cho 2 hoặc 3 thì một trong các phần tử còn lại sẽ
chia hết cho 3 hoặc 2.
- Vấn đề 2: Thực hiện phép chia lấy dư với 2013, áp dụng lý thuyết đồng
dư ta lấy tổng dư của từng phần tử của S cho 2013 chia cho 2013 lấy dư ta sẽ thu
được kết quả mà dữ liệu không bị tràn.
)
(
mod 2013 ( 1)mod 2013 (2 1)mod 2013 mod 2013SoHV n n n= + + + +
1.3.2: Sử dụng dữ liệu kiểu xâu để biểu diễn và tính toán.
Người thực hiện: Nguyễn Khải Hoàn
6
Xử lý dữ liệu lớn trong một số bài toán tin
- Với khả năng không hạn chế độ dài xâu ký tự trong Free Pascal thì mọi
số ta có thể biểu diễn được dưới dạng xâu và sử lý nó với các phép toán số học.
Ví dụ: Ta có hai số A(a
1
a
2
a
3
a
n
) và số B(b
1
b
2
b

3
b
n
) mỗi số lần lượt có độ
dài là N và M, giả sử (N>M)
Ý tưởng: Ta cần có ba xâu A,B,S để biểu diễn cho các số A,B và kết quả
của các phép tính.
* Đối với phép tính cộng:
- Để sử lý vấn đề này ta tiến hành theo hai bước:
+ Bước 1: Điền đầy |N-M| giá trị 0 vào trước số có độ dài nhỏ hơn để
được hai số có độ dài bằng nhau bằng N
+ Bước 2: Thực hiện duyệt ngược 2 xâu đó mỗi bước duyệt lấy ở mỗi xâu
một ký tự để thực hiện tính cộng và lưu ý sử dụng biến nhớ để công thêm vào
kết quả cho những giá trị lớn hơn 10 có nhớ và phép cộng trở nên rất đơn giản
với các số trong phạm vi 10.
* Đối với phép tính trừ:
Với phép trừ ta luôn luôn lấy số có độ dài lớn hơn trừ đi số có độ dài nhỏ
hơn để phép trừ trở nên đơn giản, ta thực hiện duyệt ngược hai xâu sau đó thực
hiện phép trừ:
S
i
=a
i
+Cso-b
i
-du
- Trong đó: - a
i
,b
i

là chữ số thứ i
- du: Là số dư của phép trừ trước a
i-1
-b
i-1
- Cso=10 để a
i
-b
i
>0
* Đối với phép tính nhân:
- Nếu ta thực hiện nhân hai xâu với nhau thì độ phức tạp thuật toán rất lớn
và thời gian chạy sẽ rất lâu nếu các số đem nhân là tương đối lớn.
Ý tưởng thuật toán:
- Cắt B thành M số
- Tiến hành nhân từng số cắt được của B với xâu A.
- Tiến hành cộng các xâu lại sau khi nhân ta thu được kết quả của phép
nhân.
* Đối với phép tính chia:
- Trong các phép toán thì phép chia phức tạp và khó cài đặt mã nguồn hơn,
nhưng thực chất vẫn là áp dụng phép trừ để tính toán.
- Ý tưởng cắt lần lượt từng "đoạn" của số bị chia tính từ bên trái (có cộng
thêm phần dư của các bước trung gian).
- Đem chia các đoạn đó cho số chia bằng phép toán trừ.
- Thương tìm được chính là dãy các số là kết quả của phép chia các "đoạn"
cho số chia (được phát triển dần về phía bên phải).
Người thực hiện: Nguyễn Khải Hoàn
7
Xử lý dữ liệu lớn trong một số bài toán tin
- Phần dư của phép chia chính là "đoạn" còn lại không thể chia được nữa

Người thực hiện: Nguyễn Khải Hoàn
8
Xử lý dữ liệu lớn trong một số bài toán tin
1.4. Chú ý
- Chủ yếu áp dụng cho các bài toán cần phải sử lý dữ liệu lớn.
- Cần xác định rõ giới hạn dữ liệu của từng bài toán để lựa chọn phương
pháp phù hợp tránh tình trạng lãng phí bộ nhớ trong tính toán dẫn đến vi phạm
thời gian chạy test.
- Với ngôn ngữ lập trình Pascal thì số lớn nhất có thể biểu diễn ở dạng
String có độ dài 255 ký tự cho nên số lớn nhất trong tính toán nhỏ hơn 255 chữ
số.
- Còn đối với Free Pascal thì số chữ số của một số là không có giới hạn với
kiểu Ansistring ;
- Cho nên tùy từng bài toán ta có thể lựa chọn Pascal hay Free Pascal.
2. Cơ sở thực tiễn:
Qua nhiều năm giảng dạy, gắn với công tác phát hiện và bồi dưỡng HSG
tôi nhận thấy các em học sinh giỏi rất lúng túng khi va phải những bài toán với
sự giới hạn dữ liệu như vậy và đa số các em không chú ý, xử lý tốt được yêu cầu
của bài toán dẫn tới mất khoảng 2/3 số test lớn. Hơn nữa với việc kết hợp nhuần
nhuyễn giữa các kiểu dữ liệu làm học sinh rất sợ cảm thấy khó.
Đa số những năm gần đây mục tiêu của các bài toán hầu hết yêu cầu học
sinh phải sử lý tốt được dữ liệu lớn, bằng cách nào, bằng phương pháp nào để
đạt được mục đích, đây chính là cơ sở cho việc tổ chức dữ liệu mà sau này các
em sẽ gặp nhiều trong các bài toán tin hay trong lập trình phần mềm ứng dụng.
3. Giải pháp mới sáng tạo:
Việc chọn lọc và phân loại một số các bài tập theo các dạng cơ bản áp dụng
các thủ thuật xử lý dữ liệu lớn, tìm cách giải cho từng dạng này góp phần nâng
cao hứng thú của các em đối với môn học.
Với việc phân tích bài toán theo chiều toán học thuần thúy giúp các em tư
duy toán học tốt, đôi khi có những bài toán tưởng chừng như phức tạp nhưng với

tư duy toán học tốt thì việc giải quyết bài toán lại càng chở nên đơn giản.
3.1. Các dạng bài tập thường gặp:
* Tất cả các bài toán tìm số
* Một số bài toán tối ưu
* Một số bài toán chia để trị
Nói chung bất kỳ bài toán nào liên quan tới quá trình tính toán thì đều
áp dụng phương pháp này để cho lời giải tốt nhất.
3.2. Các ví dụ minh hoạ :
Ví dụ 1: Đề thi HSG Tin học lớp 9 năm 2013-2014 SGD Vĩnh Phúc.
Cho một bảng hình vuông kích thước NxN (N< 10
18
) được chia lưới vuông
đơn vị, các vị trí đỉnh của các hình vuông đơn vị được coi là các mắt lưới. Người
ta muốn đếm số hình vuông thỏa mãn hai điều kiện sau:
Người thực hiện: Nguyễn Khải Hoàn
9
Xử lý dữ liệu lớn trong một số bài toán tin
+ Mỗi cạnh của hình vuông phải song song với một trong hai cạnh bảng
+ Tất cả 4 đỉnh của hình vuông phải nằm tại vị trí của các mắt lưới.
Vì số lượng hình vuông là rất lớn cho nên ta chỉ phải ghi kết quả là số dư
của phép chia số lượng hình vuông đếm được cho 2013.
GIẢI
- Phân tích bài toán ta rút ra:
Với hình vuông n*n sẽ có các loại ô vuông có đơn vị từ 1 đến n và:
- Hình vuông 1 đơn vị có: n
2
- Hình vuông 2 đơn vị có: (n-1)
2
- Hình vuông 3 đơn vị có: (n-2)
2

………………….
- Hình vuông n đơn vị có: (n-(n-1))
2
= 1.
Vậy số ô vuông của hình vuông n*n là:
( 1)(2 1)
6
n n n
S
+ +
=
Và kết quả yêu cầu của bài toán là:
( 1)(2 1)
6
n n n
S
+ +
=
Mod 2013.
Nếu thuần thúy thì cứ công thức ta thực hiện được phép toán, nhưng vấn
đề ở đây là
18
10n ≤
cho nên tích trên đã vượt khỏi độ lớn dữ liệu và bị tràn bộ
nhớ. Với toán học ta sử lý tích trên rất đơn giản theo hai vấn đề sau:
- Vấn đề 1: Sử lý nội hàm tích S=n(n+1)(2n+1), tích này luôn luôn chia
hết cho 6 bằng cách ta xét tính chia hết của từng phần tử trong tích cho 2 và 3,
nếu một phần tử nào chia hết cho 2 hoặc 3 thì một trong các phần tử còn lại sẽ
chia hết cho 3 hoặc 2.
- Vấn đề 2: Thực hiện phép chia lấy dư với 2013, áp dụng lý thuyết đồng

dư ta lấy tổng dư của từng phần tử của S cho 2013 chia cho 2013 lấy dư ta sẽ thu
được kết quả mà dữ liệu không bị tràn.
)
(
mod 2013 ( 1)mod 2013 (2 1)mod 2013 mod 2013SoHV n n n= + + + +
- Mã nguồn của chương trình trên Free Pascal như sau :
Program DemHV;
const
InputFile = 'Count.INP';
OutputFile = 'Count.OUT';
M = 2013;
Var
fi, fo: Text;
n: Int64;
x: array[1 3] of Int64;
i: Integer;
Kq: Int64;
Begin
Người thực hiện: Nguyễn Khải Hoàn
10
Xử lý dữ liệu lớn trong một số bài toán tin
Assign(fi, InputFile); Reset(fi);
Assign(fo, OutputFile); Rewrite(fo);
While not SeekEof(fi) do
Begin
ReadLn(fi, n);
x[1] := n; x[2] := n + 1; x[3] := 2 * n + 1;
For i := 1 to 3 do
If x[i] mod 2 = 0 then
Begin

x[i] := x[i] div 2;
Break;
End;
For i := 1 to 3 do
If x[i] mod 3 = 0 then
Begin
x[i] := x[i] div 3;
Break;
End;
Kq := (x[1] mod m) * (x[2] mod m) * (x[3] mod m) mod m;
WriteLn(fo, Kq);
End;
Close(fi); Close(fo);
End.
- Như vậy với bài toán này ta sử dụng tối ưu công thức tính toán sẽ không
phải sử lý số lớn trên xâu nên bài toán trở nên đơn giản hơn nhiều. Từ thuật toán
tối ưu thay vì thực hiện phép chia một số lớn ta thực hiện chia trên nhiều số nhỏ
hơn đảm bảo không bị tràn dữ liệu và thời gian chạy test.
Ví dụ 2: Cho hai số nguyên có dạng A(a
1
a
2
a
3
a
n
) và số B(b
1
b
2

b
3
b
n
) mỗi
số lần lượt có độ dài là N và M, giả sử (N>M). Lập trình tính tổng hai số đã cho,
dữ liệu được cho từ file Cong.inp có dạng:
Cong.inp
6565463123598775811235125321212351523959235151516
9798665983898098005152351235123521359123052
Người thực hiện: Nguyễn Khải Hoàn
11
Xử lý dữ liệu lớn trong một số bài toán tin
Kết quả được xuất trong File Cong.Out gồm 1 dòng là kết quả của phép
cộng.
Cong.out
6565472922264759709333130473563586647480594274568
GIẢI
- Ta tiến hành phân tích bài toán: Với dữ liệu mẫu như trong file Cong.inp
ta nhận thấy N,M không có giới hạn tức độ lớn dữ liệu vượt qua giới hạn của các
kiểu số trong Pascal và Free Pascal cho nên nếu ta thực hiện cộng một cách bình
thường thì dẫn đến không thể biểu diễn dữ liệu được và sẽ gặp lỗi tràn bộ nhớ.
- Ta gọi N, M là số chữ số của hai số, thực hiện như sau:
+ Bước 1: Điền đầy |N-M| giá trị 0 vào trước số có độ dài nhỏ hơn để
được hai số có độ dài bằng nhau bằng N
+ Bước 2: Thực hiện duyệt ngược 2 xâu đó mỗi bước duyệt lấy ở mỗi xâu
một ký tự để thực hiện tính cộng và lưu ý sử dụng biến nhớ để công thêm vào
kết quả cho những giá trị lớn hơn 10 có nhớ và phép cộng trở nên rất đơn giản
với các số trong phạm vi 10.
- Ta có mã nguồn của bài toán trên Free Pascal như sau:

Program TongSoLon;
uses crt;
Var X,Y:Ansistring;
F,G:Text;
Function tong(a,b:Ansistring):Ansistring;
Var i,x,y,t,z,nho:longint;
c:Ansistring;
Begin
While length(a)<length(b) Do a:='0'+a;
While length(b)<length(a) do b:='0'+b;
C:='';
Nho:=0;
For i:= length(a) downto 1 do
Begin
x:=ord(a[i])-48;
y:=ord(b[i])-48;
t:=x+y+nho;
z:=t mod 10;
Người thực hiện: Nguyễn Khải Hoàn
12
Xử lý dữ liệu lớn trong một số bài toán tin
nho:=t div 10;
c:=char(z+48)+c;
End;
If nho>0 then c:='1'+C;
tong:=c;
End;
Procedure Suly;
Begin
Assign(F,'cong.inp');Reset(F);

Assign(G,'cong.out');Rewrite(G);
Readln(F,x);Read(F,y);
Writeln(G,tong(x,y));
Close(F);Close(G);
End;
BEGIN
Suly;
END.
* Nhận xét: Trong mã nguồn trên ta thấy sử dụng Ord(A[i])-48 mà không
sử dụng Val(); Vì xét thời gian truy xuất để lấy ra giá trị số của ký tự A[i]
trong bảng mã ASCII sẽ nhanh hơn sử dụng hàm Val() để đổi một ký tự
sang số.
Ví dụ 3: Cho hai số nguyên có dạng A(a
1
a
2
a
3
a
n
) và số B(b
1
b
2
b
3
b
n
) mỗi
số lần lượt có độ dài là N và M, giả sử (N>M). Lập trình tính hiệu hai số đã cho,

dữ liệu được cho từ file Cong.inp có dạng:
Hieu.inp
6565463123598775811235125321212351523959235151516
9798665983898098005152351235123521359123052
Kết quả được xuất trong File Cong.Out gồm 1 dòng là kết quả của phép trừ
Hieu.out
6565453324932791913137110168861116390437875028464
Giải
* Phân tích bài toán: Với N,M không giới hạn như bài toán này thì việc
tính toán ta cũng không thể sử dụng các kiểu dữ liệu số trong TP hay FC để làm
được, cho nên xử dụng xâu để biểu diễn tính toán số là hợp lý nhất, với việc sử
Người thực hiện: Nguyễn Khải Hoàn
13
Xử lý dữ liệu lớn trong một số bài toán tin
dụng xâu thì ta đã đưa bài toán tính số vô cùng lớn thực chất về bài toán trừ hai
số trong phạm vi 10.
* Ý tưởng: Xử lý theo các bước sau:
- Bước 1: Lấp đầy các ký tự ’0’ vào trước xâu B để Length(B)=Length(A).
- Bước 2: Duyệt ngược xâu A và B với mỗi bước lặp ta làm:
+ t=a[i]+Cso-b[i]-nho
+ Tính lại biến Nho, lúc này biến Nho={0,1}
+ Trong đó: t là kết quả
a[i],b[i]: Là ký tự thứ i của 2 số
Cso=10 luôn đảm bảo a[i]-b[i]>0;
Nho={0,1}
* Ta có mã nguồn như sau:
Program HieuNL;
Uses Crt;
Const Cso=10;
Var F,G:Text;

X,Y:Ansistring;
Procedure Input;
Begin
Assign(F,'Hieu.inp');Reset(F);
Assign(G,'Hieu.out');Rewrite(G);
Readln(F,x);
Read(F,y);
Close(F);
End;
Function Hieu(a,b:Ansistring):Ansistring;
Var x,y,t,z,nho:Byte;
i:Longint;
c:Ansistring;
Begin
While Length(b)<Length(a) Do b:='0'+b;
Nho:=0;
For i:=Length(a) downto 1 do
Begin
x:=ord(a[i])-48 ;
y:=ord(b[i])-48;
Người thực hiện: Nguyễn Khải Hoàn
14
Xử lý dữ liệu lớn trong một số bài toán tin
t:=x+Cso-y-nho;
z:=t mod 10;
If t>10 then nho:=0
Else nho:=1;
c:=Char(z+48)+c;
End;
Hieu:=c;

End;
Procedure Suly;
Begin
Write(G,Hieu(x,y));
End;
BEGIN
Input;
Suly;
Close(G);
END.
* Nhận xét:
Với bài tính hiệu hai số lớn như thế này thuật toán tựa như cộng hai số lớn
nhưng ta khéo léo đưa thêm Const CSO=10 vào để luôn đảm bảo a[i]-b[i] luôn
lớn hơn không và ở đây không cần cấu trúc rẽ nhánh bài toán.
Ví dụ 4: Cho hai số nguyên có dạng A(a
1
a
2
a
3
a
n
) và số B(b
1
b
2
b
3
b
n

) mỗi
số lần lượt có độ dài là N và M, giả sử (N>M). Lập trình tính tích hai số đã cho,
dữ liệu được cho từ file Tich.inp có dạng:
Tich.inp
6565463123598775811235125321212351523959235151516
9798665983898098005152351235123521359123052
Kết quả được xuất trong File Cong.Out gồm 1 dòng là kết quả của phép
nhân
Tich.out
6433278017774467841619823709225614590179236138817581903
2395279719419862788502059034108346832
Giải
* Phân tích bài toán: Cũng với N,M không giới hạn như bài toán này thì
việc tính toán ta cũng không thể sử dụng các kiểu dữ liệu số trong TP hay FC để
Người thực hiện: Nguyễn Khải Hoàn
15
Xử lý dữ liệu lớn trong một số bài toán tin
làm được, cho nên lựa chọn sử dụng xâu để xử lý bài toán để đưa phép nhân số
lớn thành nhân các số trong phạm vi 10;
* Ý tưởng: Xử lý theo các bước sau:
- Bước 1: Xây dựng hàm nhân 1 số với 1 xâu
- Bước 2: Xây dựng hàm cộng xâu
- Bước 3: Xây dựng hàm nhân 2 xâu bằng cách cộng các kết quả
* Mã nguồn trên Free Pascal
PROGRAM NHAN2XAU;
USES CRT;
VAR S1,S2:Ansistring;
F,G:Text;
PROCEDURE NhapDL;
BEGIN

Assign(F,'Nhan.inp');Reset(F);
Readln(F,S1);
Read(F,S2);
Close(F);
END;
{Nhan 1 so voi 1 xau}
FUNCTION int(a:INT64;b:ANSISTRING):ANSISTRING;
VAR res,k,m:INT64;
ii:LONGINT;
l:ANSISTRING;
er:INTEGER;
BEGIN
IF (a=0) OR (b='0') THEN int:='0'
ELSE BEGIN
int:='';
res:=0;
FOR ii:=length(b) DOWNTO 1 DO
BEGIN
val(b[ii],k,er);
res:=res+k*a;
IF res>=10 THEN
BEGIN
m:=res MOD 10;
Người thực hiện: Nguyễn Khải Hoàn
16
Xử lý dữ liệu lớn trong một số bài toán tin
res:=res DIV 10;
str(m,l);
int:=l+int;
END

ELSE IF res<10 THEN
BEGIN
str(res,l);
int:=l+int;
res:=0;
END;
END;
IF res>0 THEN
BEGIN
str(res,l);
int:=l+int;
END;
END;
END;
{Cong 2 xau}
FUNCTION cx(x:ansistring;y:ansistring):ansistring;
VAR m,k,k1,i,r:LONGINT;
s:STRING;
er:INTEGER;
BEGIN
IF length(x)>length(y) THEN
BEGIN
m:=length(x)-length(y);
FOR i:=1 TO m DO y:='0'+y;
END
ELSE IF length(y)>length(x)THEN
BEGIN
m:=length(y)-length(x);
FOR i:=1 TO m DO x:='0'+x;
END;

r:=0;
i:=length(x);
Người thực hiện: Nguyễn Khải Hoàn
17
Xử lý dữ liệu lớn trong một số bài toán tin
cx:='';
WHILE i>0 DO
BEGIN
val(x[i],k,er);
val(y[i],k1,er);
m:=k+k1+r;
IF m>=10 THEN
BEGIN
r:=1;
m:=m-10;
str(m,s);
cx:=s+cx;
END
ELSE IF m<10 THEN
BEGIN
r:=0;
str(m,s);
cx:=s+cx;
END;
dec(i);
END;
if r=1 then cx:='1'+cx;
END;
{Nhan 2 so lon bang cach tach cau tao so}
FUNCTION x2(a1:ansistring;b1:ansistring):ansistring;

VAR o,i2,j2,kk:LONGINT;
er:INTEGER;
xau,xau2:ansistring;
BEGIN
val(b1[length(b1)],kk,er);
x2:=int(kk,a1);
FOR i2:=length(b1)-1 DOWNTO 1 DO
BEGIN
val(b1[i2],kk,er);
xau:=int(kk,a1);
j2:=length(b1)-i2;
Người thực hiện: Nguyễn Khải Hoàn
18
Xử lý dữ liệu lớn trong một số bài toán tin
FOR o:=1 TO j2 DO xau:=xau+'0';
xau2:=cx(x2,xau);
x2:=xau2;
END;
END;
PROCEDURE Suly;
BEGIN
Assign(G,'Nhan.out');Rewrite(G);
Write(G,X2(S1,S2));
Close(G);
END;
BEGIN
NhapDL;
Suly;
END.
Ví dụ 5: Cho hai số nguyên có dạng A(a

1
a
2
a
3
a
n
) và số B(b
1
b
2
b
3
b
n
) mỗi
số lần lượt có độ dài là N và M, giả sử (N>M). Lập trình tính thương hai số đã
cho, dữ liệu được cho từ file thương.inp có dạng:
Thương.inp
6433278017774467841619823709225614590179236138817581903
2395279719419862788502059034108346832
6565463123598775811235125321212351523959235151516
Kết quả được xuất trong File Cong.Out gồm 1 dòng là kết quả của phép
chia
thương.out
9798665983898098005152351235123521359123052
Giải
* Phân tích ý tưởng bài toán:
- Cắt lần lượt từng "đoạn" của số bị chia tính từ bên trái (có cộng thêm
phần dư của các bước trung gian).

- Đem chia các đoạn đó cho số chia bằng phép toán trừ.
- Thương tìm được chính là dãy các số là kết quả của phép chia các "đoạn"
cho số chia (được phát triển dần về phía bên phải).
- Phần dư của phép chia chính là "đoạn" còn lại không thể chia được nữa
Người thực hiện: Nguyễn Khải Hoàn
19
Xử lý dữ liệu lớn trong một số bài toán tin
* Mã nguồn trên Free Pascal
Program Phep_Chia_Hai_So_Lon;
Var a,b,c:array[0 25000] of shortint;
l,la,lb,lc:integer;
Function ss(d,k:integer):boolean;
{so sanh hai day so: a[d] a[k]va b[1] b[lb]}
Var ok,kt:boolean; i,j: integer;
Begin
If k-d+1>lb then ok:=true
else if (k-d+1<lb )or (k>la) then ok:=false
else
begin
ok:=true;kt:=true;i:=d;j:=1;
while kt and(i<=k) do
if a[i] >b[j] then kt:=false
else if a[i] <b[j] then
Begin kt:=false;
ok:=false
End
else
Begin i:=i+1;j:=j+1;end;
end;
ss:=ok

end;
Procedure tru(d,k:integer);
Var tg,phu:byte;j,i:integer;
Begin
phu:=0;j:=lb;
for i:=k downto d do
begin
if a[i]-b[j]- phu<0 then
begin
a[i]:=a[i]+10-b[j]-phu;
phu:=1;
end
Người thực hiện: Nguyễn Khải Hoàn
20
Xử lý dữ liệu lớn trong một số bài toán tin
else
begin
a[i]:=a[i]-b[j]-phu;
phu:=0;
end;
j:=j-1;
end;
end;
Procedure xu_ly;
Var t:byte;k,i:integer;
Begin
lc:=0;l:=1;k:=lb;
if not ss(l,k)and(k>=la) then exit;
if not ss(l,k) then k:=k+1;
k:=k-1;

repeat
k:=k+1;
while (a[l]=0) and(l<k) do l:=l+1;
t:=0;
while ss(l,k) do
begin
tru(l,k);t:=t+1;
if (a[l]=0) and(l<=la) then l:=l+1;
end;
lc:=lc+1;c[lc]:=t;
until not ss(l,la)or(k>la);
while (k<la) do
begin
lc:=lc+1;c[lc]:=0;k:=k+1;
end;
while (l<la)and(a[l]=0) do l:=l+1;
end;
Procedure init;
Var f:text;s:string;x,i,code:integer;
Begin
Người thực hiện: Nguyễn Khải Hoàn
21
Xử lý dữ liệu lớn trong một số bài toán tin
assign(f,'chia.inp');
reset(f);la:=0;lb:=0;
repeat
readln(f,s);
for i:=1 to length(s) do
begin
val(s[i],x,code);

la:=la+1;a[la]:=x;
end;
until s='';
repeat
readln(f,s);
for i:=1 to length(s) do
begin
val(s[i],x,code);
lb:=lb+1;b[lb]:=x;
end;
until s='';
close(f);b[0]:=0;
end;
Procedure test;
Var f:text;i:integer;
Begin
init; xu_ly;
assign(f,'chia.out');
rewrite(f);
if lc=0 then writeln(f,0)
else
begin
for i:=1 to lc do
begin
write(f,c[i]);
if i mod 60=0 then writeln(f);
end;
if i mod 60<>0 then writeln(f);
end;
Người thực hiện: Nguyễn Khải Hoàn

22
Xử lý dữ liệu lớn trong một số bài toán tin
writeln(f);
if l>la then writeln(f,0)
else
for i:=l to la do
begin
write(f,A[i]);
if i mod 60=0 then writeln(f);
end;
close(f);
end;
Begin
Test;
End.
Ví dụ 6. Với phép toán Div và Mod thực chất khi ta thực hiện được phép
chia thì từ đó ta lấy được kết quả của phép toán Div và Mod. Để xây dựng
thuật toán mô phỏng hai phép tính này là nội dung bài tập cho học sinh.
Bài tập vận dụng:
Bài 1: Tìm chữ số 0 tận cùng của n! với n<10
9
Bài 2: Tìm ra N chữ số hoàn hảo với N<10
2
Bài 3: In ra N số nguyên tố đầu tiên với N<=10
18
Bài 4: Tìm UCNN của hai số M và N với M,N<10
18
Bài 5: In ra số chính phương thứ N với N<10
9
Người thực hiện: Nguyễn Khải Hoàn

23
Xử lý dữ liệu lớn trong một số bài toán tin
4. Kết quả nghiên cứu:
Sau quá trình áp dụng đề tài nghiên cứu trong việc bồi dưỡng học sinh
giỏi môn tin hộc lớp 9 ở trường THCS Thái Hòa tôi đã thu được kết quả đáng
khả quan. Học sinh vận dụng tự tin và linh hoạt các phương pháp sử lý dữ liệu
lớn trong làm các bài tập và bài thi.
- Nhận thức và tư duy toán học của học sinh tăng lên, đứng trước mỗi bài
tập học sinh thường tư duy sử dụng toán học để vét hết các khả năng có thể từ
đó mới cài đặt mã nguồn.
- Từ đó hàng năm số lượng và chất lượng học sinh giỏi Tin học cấp huyện
và cấp tỉnh tăng lên rõ rệt:
Năm học
Cấp-Giải
Huyện Tỉnh
Nhất Nhì Ba KK Nhất Nhì Ba KK
2011-2012 1 1 1
2012-2013 1 1 1
2013-2014 1 1 1
- Đây là một tín hiệu khả quan đối với chất lượng HSG bộ môn.
5. Ứng dụng vào thực tiễn công tác giảng dạy:
5.1. Quá trình áp dụng của bản thân:
Tôi đã áp dụng cách thức bồi dưỡng này qua ba khoá học. Tuy nhiên, mỗi
khoá học sinh mỗi khác, tuỳ thuộc vào khả năng và trình độ của từng học sinh
để sửa đổi, bổ sung cho hợp lí. Áp dụng cách thức làm này qua các khoá học tôi
thấy đã có hiệu quả trong việc học tập của các em học sinh.
- Đã khơi dậy được niềm đam mê nghiên cứu khoa học ở học sinh, đồng
thời cũng là động lực thúc đẩy quá trình học hỏi, tìm tòi của bản thân.
5.2. Bài học kinh nghiệm:
Qua việc bồi dưỡng tôi nhận thấy mình có thêm được những kinh nghiệm

qúi báu về chuyên môn. Bên cạnh đó không nên thoả mãn mà vẫn tiếp tục phải
học hỏi, phấn đấu không ngừng vì nhu cầu học tập là suốt đời. Tôi vẫn phải tiếp
tục học tập đồng nghiệp ở trường, ở các trường bạn và các huyện bạn để nâng
cao vị thế, chất lượng môn Tin học ở nhà trường, khu vực và trong huyện.
Người thực hiện: Nguyễn Khải Hoàn
24
Xử lý dữ liệu lớn trong một số bài toán tin
Phần III: KẾT LUẬN VÀ KIẾN NGHỊ
Xử lý dữ liệu lớn nói riêng, áp dụng chúng vào giải các bài tập tin học nói
chung đóng vai trò hết sức quan trọng trong việc lập trình giải các bài toán tin,
nó giúp học sinh phát triển tư duy sáng tạo, đồng thời nó góp phần quan trọng
trong việc ôn luyện kiến thức cũ, bổ sung thêm những phần thiếu sót về lý
thuyết và thực hành tin học, đồng thời xây dựng những khái niệm cơ bản cho
các em biết cấu trúc, tổ chức, sắp xếp dữ ở các ngôn ngữ lập trình sau này.
Là giáo viên giảng dạy môn Tóa học chúng tôi nhận thấy trong quá trình
giảng dạy bồi dưỡng học sinh giỏi sẽ gặp không ít khó khăn trong việc giúp các
em học sinh làm các dạng bài tập. Song với một số kinh nghiệm ít ỏi của bản
thân và sự giúp đỡ của các bạn đồng nghiệp, cùng với sự phát triển CNTT, việc
chia sẻ những hiểu biết, kiến thức trên Internet giúp tôi mạnh dạn kết hợp giữa
hai mặt lí thuyết và thực tiễn để viết chuyên đề này nhằm phân loại, định hướng
phương pháp giải cho các bài tập bồi dưỡng học sinh giỏi.
Để xây dựng mũi nhọn HSG trong trường THCS cần tranh thủ khai thác
tốt vai trò của tổ chuyên môn những đồng chí, đồng nghiệp có kiến thức, tư duy
toán học tốt để bù đắp những lỗ hổng về kiến thức ở một số phần. Học sinh giỏi
tin học không phải chỉ có sự cần cù, chịu khó mà cần có tư suy toán học tốt, bởi
“ Toán học là cơ sở của Tin học”, phát triển toán tốt thì xây dựng trên Tin học
cũng tốt, chúng bổ trợ nhau.
Sau mỗi chương, phần cần khái quát lại nội dungm kiến thức từng phần,
đồng thời xác định được rõ đối tượng bài toán nào thì ta sử dụng phương pháp
nào, cách thức nào.

Vì thời gian, khả năng hạn chế nên chuyên đề của tôi không tránh khỏi
thiếu sót, rất mong các đồng chí đóng góp xây dựng để chuyên đề hoàn thiện
hơn.
Tôi xin chân thành cảm ơn !
Thái Hòa, ngày tháng năm 2014
Người viết chuyên đề:
Nguyễn Khải Hoàn
Người thực hiện: Nguyễn Khải Hoàn
25