SKKN Mở rộng phạm vi tính toán trong ngôn ngữ lập trình Free Pascal với số nguyên không âm có nhiều chữ số

MỤC LỤC
Tài liệu tham khảo
1. MỞ ĐẦU
1.1 Lý do chọn đề tài.
Lập trình Tin học là vấn đề khoa học có tính thực tiễn cao, luôn đòi hỏi người lập trình lĩnh hội kiến thức đã học và vận dụng các kiến thức đó vào giải quyết những bài toán thực tế.
“Các Kiểu dữ liệu của ngôn ngữ lập trình nói chung và ngôn ngữ lập trình Pascal hoặc free pascal nói riêng đều giới hạn trong phạm vi nhất định”[1]. Khi Test chương trình học sinh thường test trên các bộ test bé nên có cảm giác bài làm đúng với mọi bộ input nhưng khi test bằng máy với bộ test lớn thì chương trình đưa ra kết quả không đúng. Chính vì vậy, tôi mạnh dạn viết sáng kiến “Mở rộng phạm vi tính toán trong ngôn ngữ lập trình Free Pascal với số nguyên không âm có nhiều chữ số”. Hy vọng rằng những kinh nghiệm này của tôi có thể góp phần giúp đồng nghiệp và các em học sinh khá giỏi có một số thuật giải về cộng trừ nhân chia với số nguyên có nhiều chữ số. 
1.2 Mục đích nghiên cứu.
	Trong sáng kiến kinh nghiệm này tôi muốn truyền tải đến các thầy cô ôn thi đội tuyển học sinh giỏi các cấp và các em học sinh tham gia câu lạc bộ lập trình Tin học có thêm một số kiến thức và kỹ năng để vận dụng mở rộng khả năng tính toán cho ngôn ngữ lập trình Free Pascal trên tập số nguyên không âm có nhiều chữ số và có thể ứng dụng vào thực tế và giải các bài toán khác.
1.3 Đối tượng nghiên cứu.
	Đối tượng nghiên cứu của tôi là chương trình Tin học 11 (trong chương trình giáo dục quốc gia) bằng cách sử dụng ngôn ngữ lập trình Pascal để vận dụng vào tính toán các số nguyên không âm lớn. 
1.4. Phương pháp nghiên cứu.
Trong phạm vi sáng kiến kinh nghiệm này. Tôi có sử dụng 2 phương pháp chính sau:
	- Sử dụng phương pháp nghiên cứu xây dựng cơ sở lý thuyết
	- Sử dụng phương pháp xử lý dữ liệu.
1.5. Những điểm mới của SKKN.
Tôi có tham khảo một số sách và một số trang web trên Internet. Tôi thấy rằng người ta cũng đã tìm hiểu mở rộng phạm vi tính toán với số nguyên nhưng chỉ đưa ra bàn luận và code chương trình chủ yếu trên ngôn ngữ lập trình C, C++. 
Trong sáng kiến kinh nghiệm này tôi vận dụng trực tiếp vào ngôn ngữ lập trình Free Pascal để học sinh có cách nhìn tổng quan và dễ hiểu hơn phù hợp với ngôn ngữ lập trình mà các em biết.
 2. NỘI DUNG SÁNG KIẾN KINH NGHIỆM
2.1. Cơ sở lý luận của sáng kiến kinh nghiệm.
	Đối với lập trình ngoài việc tìm ra thuật toán cần phải viết chương trình đó là điều rất khó đối với học sinh trong trường THPT. Khi gặp các bài toán phải tính toán với các số có nhiều chữ số nhiều em lúng lúng vì các số này vượt ra khỏi phạm vi các kiểu dữ liệu mà ngôn ngữ lập trình cung cấp. Chính vì vậy, việc giải các bài toán với các số lớn thực sự cần thiết cho các em học sinh khá giỏi khi giải các bài toán liên quan đến các số có nhiều chữ số nói riêng và việc giải quyết các bài toán thực tế nói chung. 
	Nhiều ngôn ngữ lập trình cung cấp kiểu dữ liệu số nguyên khá lớn, chẳng hạn ngôn ngữ lập trình FreePascal có kiểu số 64 bit (khoảng 19 chữ số). Tuy nhiên để thực hiện các phép toán với các số ngoài phạm vi biểu diễn được cung cấp (có hàng trăm thậm chí hàng tỷ chữ số chẳng hạn), chúng ta cần tự thiết kế cách biểu diễn và các hàm để thực hiện các phép toán cơ bản với số nguyên có nhiều chữ số.[1]
2.2. Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm.
	Trong quá trình dạy, tôi giao bài tập: 
“Hãy sử dụng ngôn ngữ lập trình Pascal hoặc FreePascal để tính tổng, hiệu, tích, thương của hai số nguyên a và b”[3]
	Học sinh sẽ lập trình tính như sau:
Khi chạy chương trình ta nhập:
máy sẽ báo lỗi!
	Vì sao lại vậy, ta biết “kiểu số nguyên lớn (longint) có phạm vi biểu diễn từ -2147483648..2147483647 (khoảng 10 chữ số)”[2]. Nên khi nhập số nguyên b=54564654565456456456 (có 20 chữ số) đã vượt ngoài phạm vi của longint. Nhiều em học sinh lúng túng cho rằng, ngôn ngữ lập trình Pascal chỉ có thể giải được các bài toán có phép tính trong khoảng số nguyên mà các em được biết. 
2.3. Các giải pháp đã sử dụng để giải quyết vấn đề.
- Tổ chức lưu trữ các số dưới dạng xâu. “Độ dài xâu tối đa là 255 kí tự”[2]. Vì vậy, xâu có thể lưu trữ được số có tối đa là 255 chữ số. Đồng nghĩa với việc ta có thể tính toán với những số có độ dài tối đa 255 chữ số. Ngoài ra, “ngôn ngữ lập trình FreePascal còn cung cấp thêm một kiểu dữ liệu dạng chuỗi (ANSISTRING) có thể tổ chức lưu trữ các số lớn hơn gấp nhiều lần so với kiểu string (bộ nhớ càng lớn thì chuỗi càng dài)[4].
 	- Sử dụng các phép tính toán trên xâu để tính kết quả. Trong khi tính toán cần sử dụng hiệu quả các thủ tục chuyển đổi kí tự kiểu xâu thành số (hàm val) và ngược lại từ số thành xâu (hàm str)[5]
 	- Hiện thị kết quả dạng xâu (hoặc mảng).
Sau đây là một số giải thuật về cộng, trừ, nhân chia các số không âm (các trường hợp còn lại tôi sẽ nói sau):
a) Giải thuật cộng: 
Khi cộng hai số có nhiều chữ số, chúng ta thực hiện từ phải qua trái. Với mỗi lần cộng, kết quả của nó còn được cộng với giá trị nhớ của lần trước đó và đồng thời cũng xác định giá trị nhớ mới...[6] 
Cụ thể ta tiến hành các bước như sau:
-Bước 1: Hai số được nhập từ bàn phím và lưu vào hai biến kiểu xâu st1 và st2.
-Bước 2: So sánh hai xâu st1 và st2. Thêm kí tự ‘0’ vào xâu ngắn hơn để hai xâu có độ dài bằng nhau.
-Bước 3: Thực hiện phép cộng hai xâu có có độ dài bằng nhau, cộng từ cuối lên đầu (tương tự như cộng ở số được thực hiện từ hàng đơn vị). Các kí tự trong xâu lần lượt chuyển thành số (sử dụng thủ tục chuyển đổi) rồi thực hiện phép cộng. Kết quả cộng các số được chuyển ngược lại thành xâu (h1).
-Bước 4: Sử dụng xâu kết quả (h) lưu trữ kết quả phép cộng (lưu ý phần nhớ)
Trong phần thân chương trình ta chỉ cần gọi:
Nhận xét:
- Chương trình trên thực hiện việc cộng hai số được nhập từ bàn phím.
- Trong chương trình có sử dụng hàm là chương trình con FUNCTION CONG(S1,S2:STRING): STRING; để tính kết quả phép cộng hai xâu s1, s2.
- Kết quả phép cộng được hiện lên trên màn hình.
- Ta có thể thay đổi chương trình bằng cách sử dụng tệp để đọc dữ liệu vào và ghi kết quả ra.
- Ta có thể mở rộng phạm vi tính toán tới các số nguyên dương không âm có số lượng các chữ số vượt qua 255 chữ số bằng cách khai báo các biến kiểu xâu là ANSISTRING.
b) Giải thuật trừ: 
Giống như cộng, chúng ta cũng thực hiện từ phải qua trái. Với mỗi lần trừ, đề phòng chữ số của số bị trừ nhỏ hơn nên ta cứ vay tạm một chục. Nếu lần trước đã vay rồi thì lần này phải trừ đi. Nhưng chỉ đáng vay nếu kết quả sau khi trừ là bé hơn 10, còn lớn hơn 10 là không phải vay...[6] 
Các bước tiến hành như sau:
-Bước 1: Nhập hai số từ bàn phím lưu vào hai biến xâu st1, st2.	
-Bước 2: So sánh hai xâu st1 và st2. Thêm kí tự ‘0’ vào xâu ngắn hơn để hai xâu có độ dài bằng nhau.
-Bước 3: So sánh hai xâu st1, st2 độ dài bằng nhau. 
+ Nếu xâu lưu số bị trừ lớn hơn xâu lưu số trừ. Thực hiện phép trừ hai xâu từ cuối lên đầu (tương tự như phép trừ trong toán học). Sử dụng thủ tục chuyển đổi xâu thành số trong quá trình tính toán.
+ Nếu xâu lưu số bị trừ bé hơn xâu lưu số trừ thực hiện đặt dấu trừ (-) vào phần đầu kết quả, đồng thời thực hiện hoán đổi hai xâu cho nhau và thực hiện phép trừ tương tự như ở trên.
-Bước 4: Phép trừ được thực hiện như sau:
+ Các kí tự sâu St1 được chuyển thành số và lưu vào mảng h1.
+ Các kí tự sâu St2 được chuyển thành số và lưu vào mảng h2.
+ Thực hiện phép trừ hai mảng h1 và h2 (lưu ý trương hợp số bị trừ bé hơn số trừ). Nếu h1[i]=h2[i] thì c[i]:=h1[i]-h2[i]; 
-Bước 5: Mảng C thu được chính là kết quả.
Qua đó, ta có thể viết được thành chương trình như sau:
Nhận xét: 
- Chương trình trên thực hiện phép trừ hai số lớn rất lớn được nhập từ bàn phím với các biến kiểu xâu được khai báo là ANSISTRING. Hiệu của hai số được hiển thị trên màn hình.
Cần chú ý tới phần dấu của phép trừ (nếu số bị trừ bé hơn số trừ ghi vào kết quả dấu -)
c) Giải thuật nhân:
 Thông thường, khi nhân a với b, chúng ta thực hiện từ phải qua trái. Mỗi lần sẽ nhân một chữ số của b với số a và đặt kết quả dịch sang trái 1 chữ số. Nhưng trong mỗi lần đó chúng ta lại lần lượt nhân từng chữ số của a với chữ số nói trên của b. Cũng như phép cộng, kết quả cũng phụ thuộc việc nhớ của lần nhân trước và xác định giá trị nhớ mới. Việc nhận này được thực hiện từ trái qua phải đó...[6] 
Quá trình làm được tiến hành qua các bước như sau:
-Bước 1: Nhập hai số lưu ở dạng hai biến xâu s1, s2.
-Bước 2: Sử dụng mảng C lưu kết quả phép nhân hai xâu s1, s2 (các kí tự trong xâu được chuyển đối thành số khi tính toán).
 L1:=length(s1); L2:=length(s2);
 For i:=1 to L1 do 
 For j:=1 to L2 do
 Begin 
 val(s1[i],A,code);
 val(s2[j],B,code);
 c[i+j]:=c[i+j]+a*b; 
 End;
-Bước 3: Xử lý mảng kết quả:
 For i:=L1+L2 downto 3 do
 Begin
 c[i-1]:=c[i-1] + c[i] Div 10;
 c[i]:=c[i] Mod 10;
 End; 
Sau đây là chương trình:
Nhận xét: 
- Chương trình trên thực hiện phép nhân hai số lớn được nhập từ bàn phím. Kết quả phép nhân được hiển thị trên màn hình.
 	 - Khi sử dụng mảng để lưu kết quả phép nhân, độ dài của mảng kết quả lớn hơn hoặc bằng tổng độ dài của hai số (xâu).
 	 - Ta có thể thay đổi kiểu dữ liệu cho các biến kiểu xâu thành ANSISTRING để có thể nhân 2 số nguyên dương không âm lớn hơn 255 chữ số.
d) Giải thuật chia:
Để chia số a cho số b. ta tiến hành qua các bước như sau:
-Bước1: Dùng 2 xâu a và b chứa các chữ số của số bị chia và số chia (các mảng có số phần tử tương ứng là n và m), dùng xâu c để chứa kết quả.
-Bước 2: Lấy m phần tử đầu của chuỗi a được chuỗi a1, đem số này chia cho chuỗi b, vì 2 số đều lớn nên có thể dùng vòng for để lặp từ 1 đến 10, nếu i = 1...9, mà i*b > a1 thì được thương bằng i-1 và số dư là t1 = a1 -b*(i-1)
-Bước 3: Có số dư t1 từ bước 2, tiếp túc lấy t1*10+ số thứ m+1 trong chuỗi a ban đầu để được số chia a2, lại dùng vòng for để lặp và lại tính đc số dư t2, tiếp tục như vậy đến khi nào đến phần tử n trong chuỗi a thì dừng. Có thể tiếp tục nếu muốn lấy số thập phân.
Như vậy ta có thể xây dựng được một hàm là chương trình con dùng để chia 2 số nguyên lớn dựa vào kết quả của hai hàm cộng và trừ ở trên: 
Nhận xét:
- Kết quả của phép chia ta được đó là phần nguyên
- Trong chương trình con trên ta sử dụng lời gọi của 2 chương trình con cộng và trừ 2 số nguyên lớn (cong(kb[i-1],b) và tru(hold,kb[k-1])) ở trên.
- Muốn lấy kết quả là phần dư ta có thể sửa chương trình con trên.[1] thành như sau:
2.4. Hiệu quả của sáng kiến kinh nghiệm đối với hoạt động giáo dục, với bản thân, đồng nghiệp và nhà trường.
- Thông qua sáng kiến kinh nghiệm này học sinh có thể thực hiện được phép toán cộng trừ nhân chia với các số nguyên dương không âm vượt ra ngoài phạm vi biểu diễn của các kiểu dữ liệu mà ngôn ngữ lập trình cung cấp.
- Sáng kiến kinh nghiệm này giúp học sinh và các thầy cô giáo có thêm các giải thuật để cộng trừ nhân chia với các số nguyên lớn bằng cách sử dụng các kiến thức đã học như mảng một chiều và xâu ký tự... 
- Qua các giải thuật trong sáng kiến kinh nghiệm này thầy cô và các em học sinh có thể phát triển để cộng trừ nhân chia cho các số nguyên bất kỳ và cho số thực lớn.[4]
- Sáng kiến kinh nghiệm này góp phần giúp các thầy cô giáo cùng bộ môn và nhà trường có thêm tài liệu để ôn cho học sinh giỏi cấp trường, tỉnh, Đồng thời, giúp học sinh khắc sâu kiến thức và vận dụng kiến thức về mảng một chiều và xâu ký tự đã học vào giải quyết các bài toán khác.
3. KẾT LUẬN
3.1. Kết luận.
Đề tài này mang tính thực tiễn rất cao. Các em có thể sử dụng kiến thức lập trình để giải các bài toán thực tế thường gặp, các bài toán tính toán với số lớn. Kết quả là có rất nhiều em đã dễ dàng vận dụng được kiến thức để giải các bài toán lặp do giáo viên đặt ra.
Trong khuôn khổ sáng kiến kinh nghiệm này, tôi mới chỉ trình bày thuật toán và code chương trình cho các phép toán cộng trừ nhân chia với các số nguyên dương không âm. Còn với các số nguyên khác tôi sẽ trình bày trong sáng kiến kinh nghiệm lần sau. 
3.2. Kiến nghị.
	- Đề nghị các cấp lãnh đạo quan tâm và chỉ đạo sát sao hơn nữa để tạo điều kiện cho bộ môn tin học nói chung và môn tin học 11 nói riêng phát triển lên tầm cao mới.
XÁC NHẬN CỦA THỦ TRƯỞNG ĐƠN VỊ
Nguyễn Văn Thủy
Thanh Hóa, ngày 11 tháng 04 năm 2017
Tôi xin cam đoan đây là SKKN của mình viết, không sao chép nội dung của người khác.
(Ký và ghi rõ họ tên)
Lê Văn Như
TÀI LIỆU THAM KHẢO
1. Tài liệu giáo khoa chuyên tin quyển 1, Hồ Sĩ Đàm (chủ biên )- Đỗ Đức Đông- Lê Minh Hoàng-Nguyễn Thanh Hùng, Nhà xuất bản giáo dục Việt Nam, năm 2009.
2. Tin học 11, Hồ Sĩ Đàm (chủ biên)- Nguyễn Thanh Tùng, Nhà xuất bản giáo dục Việt Nam, năm 2014.
3. Bài tập Tin học 11, Hồ Sĩ Đàm (chủ biên)-Hồ Cẩm Hà-Trần Đỗ Hùng-Nguyễn Đức Nghĩa-Nguyễn Thanh Tùng- Ngô Ánh Tuyết, Nhà xuất bản giáo dục Việt Nam, năm 2014.
4. Phương pháp giải các bài toán trong tin học, ThS. Trần Đức Huyên, Nhà xuất bản Hà Nội (xuất bản lần 5), năm 2003.
5. Giáo trình lý thuyết và bài tập Pascal - Toàn tập : Ấn bản dành cho sinh viên, Nguyễn Đình Tê(Chủ Biên)- Hoàng Đức Hải, Nhà xuất bản Lao động xã hội, năm 2004.
6. Nguồn từ Internet: 
- Thao tác với số nguyên lớn-trình bày thuật toán và cách thực hiện, Donvuon, 2010, mã nguồn: