Sáng kiến kinh nghiệm Phương pháp xử lý đối với số nguyên dương lớn trong lập trình pascal

MỤC LỤC
PHẦN I. MỞ ĐẦU.
1. Lý do chọn đề tài
Trong quá trình dạy học và bồi dưỡng học sinh thi Tin học trẻ, mặc dù Free Pascal có kiểu số 64 bit (khoảng 19 chữ số), tuy nhiên để thực hiện các phép tính với số nguyên ngoài phạm vi biểu diễn được cung cấp (có hàng trăm chữ số chẳng hạn), tôi nhận thấy học sinh gặp rất nhiều khó khăn. Nhằm khắc phục khó khăn này và để đáp ứng được yêu cầu trong công tác bồi dưỡng học sinh giỏi, tôi nghiên cứu đề tài: “PHƯƠNG PHÁP XỬ LÝ ĐỐI VỚI SỐ NGUYÊN DƯƠNG LỚN TRONG LẬP TRÌNH PASCAL” .
2. Mục đích nghiên cứu.
- Xây dựng bộ công cụ lập trình đối với số nguyên lớn trong quá trình tiếp xúc và làm việc với số nguyên lớn.
- 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
- Học sinh khối 8 trường THCS Nguyễn Du - Quảng Xương.
4. Phương pháp nghiên cứu
- Phương pháp nghiên cứu xây dựng cơ sở lý thuyết.
- Phương pháp điều tra khảo sát thực tế.
- Phương pháp xử lý số liệu và lập trình.
PHẦN II. NỘI DUNG SÁNG KIẾN KINH NGHIỆM
Cơ sở lý luận:
Trong thời kỳ cuộc cách mạng công nghiệp 4.0, Tin học là một môn khoa học được ứng dụng vào thực tế hiện nay khá nhiều. Chính vì vậy các bài toán mà Tin học giải quyết có tính thực tiễn rất cao. Tuy nhiên, đây cũng là một môn học mới đối với các em học sinh THCS. Các em gặp không ít khó khăn trong việc tiếp cận và giải quyết các bài toán trong Tin học, nhất là các bài toán có kiểu dữ liệu số nguyên dương lớn.
Thực trạng của vấn đề:
Trong chương trình Tin học THCS, kiểu dữ liệu số nguyên lớn nhất mà các em được biết đó là kiểu integer có phạm vi -215 đến 215-1. Trong khi thực tế cần phải giải quyết các bài toán, phép toán với các số nguyên dương rất lớn. Vì vậy việc các em có thể giải quyết các bài toán này sẽ góp phần đưa kiến thức lập trình vào đời sống thực. 
3. Giải pháp giải quyết vấn đề.
Thông thường người ta sử dụng các cách biểu diễn số nguyên lớn sau:
Xâu kí tự: Đây là cách biểu diễn tự nhiên và đơn giản nhất, mỗi kí tự của xâu tương ứng với một chữ số của số nguyên lớn tính từ trái qua phải.
Mảng các số: Sử dụng mảng lưu các chữ số (hoặc một nhóm chữ số), và một biến ghi nhận số chữ số để thuận tiện trong quá trình xử lí.
Danh sách liên kết các số: Sử dụng danh sách liên kết các chữ số (hoặc một nhóm chữ số), cách làm này sẽ linh hoạt hơn trong việc sử dụng bộ nhớ.
Trong phần này, sử dụng cách biểu diễn thứ nhất, biểu diễn số nguyên lớn bằng xâu kí tự và chỉ xét các số nguyên lớn không âm.
Type bigNum = string;
3.1 Phương pháp: 
- Các số nguyên dương lớn được lưu dưới dạng xâu. Độ dài xâu tối đa là 255 kí tự. Vì vậy, xâu có thể lưu trữ được số có tối đa là 255 chữ số.
- 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ố và ngược lại từ số thành xâu.
- Hiển thị kết quả dạng xâu (hoặc mảng).
3.2 Tổ chức thực hiện: 
Bài toán1 : Phép so sánh. [1]
*) Ý tưởng thuật toán:
Để so sánh hai số nguyên lớn a, b được biểu diễn bằng xâu kí tự, trước tiên ta thêm các chữ số 0 vào đầu số có số chữ số nhỏ hơn để hai số có số lượng chữ số bằng nhau. Sau đó sử dụng trực tiếp phép toán so sánh trên xâu kí tự.
Hàm cmp so sánh hai số nguyên lớn a, b. Giá trị hàm trả về:
0 nếu a = b
 1 nếu a > b
—1 nếu a < b
*) Code:
Function	cmp(a,b : bigNum): integer; 
begin
while length(a)<length(b) do a:='0'+a; 
while length(b)<length(a) do b:='0'+b; 
if a = b then exit(0);
if a > b then exit(1); 
exit(-1);
end; 
Bài toán2 : Phép cộng 2 số nguyên. [1]
*) Ý tưởng thuật toán:
Phép cộng hai số nguyên được thực hiện từ phải qua trái và phần nhớ được mang sang trái.
*) Code:
Function	add(a,b : bigNum): bigNum;
var	sum, carry, i, x, y : integer; c:bigNum;
begin
carry:=0;
c:='';
while length(a)<length(b) do a:='0'+a; 
while length(b)<length(a) do b:='0'+b; 
for i:=length(a) downto 1 do
begin
x:= ord(a[i])-ord('0'); {ord('0')=48} 
y:= ord(b[i])-ord('0');
sum:=x + y + carry; 
carry:=sum div 10;
c:=chr(sum mod 10 +48)+c;
end;
if carry>0 then c:='1'+c; add:=c;
end;
Bài toán 3: Chương trình trừ 2 số tự nhiên lớn. [1]
*) Ý tưởng:
Thực hiện phép trừ ngược lại với việc nhớ ở phép cộng ta phải chú ý đến việc vay mượn từ hàng cao hơn. Trong hàm trừ dưới đây, chỉ xét trường hợp số lớn trừ số nhỏ hơn.
*) Code:
Function	sub(a,b:bigNum):bigNum;
Var c: bigNum;s,borrow,i:integer;
begin
borrow:=0;
c:='';
while length(a)<length(b) do a:='0'+a; 
while length(b)<length(a) do b:='0'+b; 
for i:=length(a) downto 1 do
begin
s:=ord(a[i])-ord(b[i])-borrow; 
if s<0 then
begin
s:=s+10;
borrow:=1; 
end 
else borrow:=0; 
c:=chr(s +48)+c;
end;
while (length(c)>1)and(c[1]='0') do delete(c,1,1); 
sub:=c;
end;
Bài toán 4: Phép nhân một số lớn với một số nhỏ. [1]
Số nhỏ ở đây được hiểu là số nguyên do ngôn ngữ lập trình cung cấp (như: longint, integer,..). 
Hàm multiply1(a:bigNum;b:longint):bigNum, trả về là một số nguyên lớn (bigNum) là kết quả của phép nhân một số nguyên lớn a (bigNum) với một số b (longint).
*) Code:
function	multiply1(a:bigNum;b:longint):bigNum; 
var i	:integer;
carry,s:longint;
c,tmp:bigNum; 
begin
c:='';
carry:=0;
for i:=length(a) downto 1 do 
begin
s:=(ord(a[i])-48) * b + carry; 
carry:= s div 10;
c:=chr(s mod 10 + 48)+c; 
end;
if carry>0 then str(carry,tmp) else tmp:=''; 
multiply1:=tmp+c;
end;
Bài toán 5: Phép nhân hai số nguyên lớn. [1]
*) Code:
 Function	multiply2(a,b:bigNum):bigNum;
var	sum,tmp:bigNum;
m,i,j:integer;
begin
m:= -1;
sum:='';
for i:=length(a) downto 1 do 
begin
m:=m+1;
tmp:=multiply1(b,ord(a[i])-48);
for j:=1 to m do tmp:=tmp+'0'; 
sum:=add(tmp,sum);
end; 
multiply2:=sum;
end;
Bài toán 6: Phép toán chia lấy thương nguyên (div) của một số lớn với một số nhỏ. [1]
*) Code:
function	bigDiv1(a:bigNum;b:longint):bigNum; 
var s,i,hold:longint;
c:bigNum; 
begin
hold:=0;s:=0; c:=''; 
for i:=1 to length(a) do
begin
hold:=hold*10 + ord(a[i])-48; 
s:=hold div b;
hold:=hold mod b; 
c:=c+chr(s+48);
end;
while (length(c)>1)and(c[1]='0')do delete(c,1,1);
bigDiv1:=c;
end;
Bài toán 7: Phép toán chia lấy dư (mod) của một số lớn với một số nhỏ[1]
*) Ý tưởng: 
Dựa vào các công thức sau:
(A + B) mod N = ((A mod N) + (B mod N)) mod N
(A × B)mod N = ((A mod N) × (B mod N))mod N
*) Code:
Function	bigMod1(a:bigNum;b:longint):longint;
var i,hold:longint; 
begin
hold:=0;
for i:=1 to length(a) do 
hold:=(ord(a[i])-48+hold*10) mod b;
bigMod1:=hold;
end;
Bài toán 8: Phép toán chia lấy thương nguyên (div) của hai số lớn. [1]
*) Code:
Function	 bigDiv2(a,b:bigNum):bigNum;
var	c,hold	:bigNum;
kb :array[0..10]of bigNum;
i,k:longint;
begin
kb[0]:='0';
for i:=1 to 10 do kb[i]:=add(kb[i-1],b);
hold:='';
c:='';
for i:=1 to length(a) do 
begin
hold:=hold+a[i]; 
k:=1;
while cmp(hold,kb[k])-1 do inc(k);
c:=c+chr(k-1+48); 
hold:=sub(hold,kb[k-1]);
end;
while (length(c)>1)and(c[1]='0') do delete(c,1,1); 
bigDiv2:=c;
end;
Bài toán 9: Phép toán chia lấy dư (mod) của hai số lớn. [1]
*) Code:
Function	 bigMod2(a,b:bigNum):bigNum; 
var	hold	:bigNum;
kb	:array[0..10]of bigNum; i,k:longint;
begin
kb[0]:='0';
for i:=1 to 10 do kb[i]:=add(kb[i-1],b);
hold:='';
for i:=1 to length(a) do 
begin
hold:=hold+a[i]; 
k:=1;
while cmp(hold,kb[k])-1 do
inc(k); 
hold:=sub(hold,kb[k-1]);
end; 
bigMod2:=hold;
end;
Bài toán 10: Bài tập vận dụng các hàm đã xây dựng:
Tính số Fibonacci thứ n (n ≤ 500). [2]
Số Fibonacci được xác định bởi công thức sau:
F0 = 0
 F1 = 1
 Fn = Fn–1 + Fn–2 với n >=2
*) Ý tưởng:
Trước tiên ta xây dựng chương trình tính số Fibonacci bằng kiểu dữ liệu Extended như sau:
*) Code:
function 	Fibo(n : longint):extended; 
var 	i :longint;
fi_1, fi_2, fi : extended; 
begin
if n<=1 then exit(n); 
fi_2:=0; 
fi_1:=1;
for i:=2 to n do 
begin 
fi:=fi_1 + fi_2; 
fi_2:=fi_1; 
fi_1:=fi;
end; 
exit(fi);
end;
var n : longint; 
BEGIN
write('Nhap N:'); 
readln(n);
 writeln(Fibo(n));
END.
Chạy chương trình với n = 500 ta nhận được kết quả:
1.3942322456169788E+0104, như vậy số Fibonacci thứ 500 có 105 chữ số ,ta xây dựng chương trình tính số Fibonacci lớn bằng cách sau:
- Thay kiểu extended bằng kiểu bigNum.
- Thay các phép toán bằng các hàm tính toán số lớn, xây dựng các hàm tính toán số lớn cần thiết.
*) Code:
Type	 bigNum = string;
Function	add(a,b : bigNum): bigNum; 
var	sum, carry, i : integer;
c: bigNum;
begin
carry:=0;c:='';
while length(a)<length(b) do a:='0'+a; 
while length(b)<length(a) do b:='0'+b; 
for i:=length(a) downto 1 do
begin
sum:=ord(a[i])-48+ord(b[i])-48+carry;
 carry:=sum div 10;
c:=chr(sum mod 10 +48)+c;
end;
if carry>0 then c:='1'+c; 
add:=c;
end;
function	 Fibo(n : longint):bigNum; 
var 	i :longint;
fi_1, fi_2, fi : bigNum; 
begin
if n<=1 then exit(char(n+48)); 
fi_2:='0'; 
fi_1:='1';
for i:=2 to n do 
begin 
fi:=add(fi_1,fi_2); {fi:=fi_1 + fi_2;} 
fi_2:=fi_1;
fi_1:=fi; 
end;
 exit(fi);
end;
var n : longint; 
BEGIN
write('Nhap N:'); 
readln(n); 
writeln(Fibo(n));
END.
4. Hiệu quả của Sáng kiến kinh nghiệm.
	Trong quá trình nghiên cứu, thực hiện và áp dụng đề tài vào công tác bồi dưỡng học sinh giỏi thi Tin học trẻ, đề tài này đã giúp Thầy và trò trường THCS Nguyễn Du gặt hái được một số thành công. Năm học 2014-2015, 2016-2017 đồng đội xếp thứ nhất và thứ hai toàn tỉnh, có 02 học sinh được tham gia Kỳ thi Tin học trẻ Toàn quốc.
Qua quá trình vận dụng đề tài này tôi nhận thấy đề tài này có một số ưu, nhược điểm như sau:
*) Ưu điểm:
- Giải quyết được bài toán đối với những số nguyên dương lớn.
- Xây dựng được bộ công cụ hỗ trợ hữu hiệu, giúp cho quá trình bỗi dưỡng học sinh giỏi của giáo viên đạt kết quả cao hơn và là bộ tài liệu hiệu quả giúp học sinh học lập trình giải được các bài toán số nguyên lớn tốt hơn .
*) Nhược điểm: Thuật toán để xây dựng các công cụ chưa phải là thuật toán tối ưu nhất, cần phải hoàn chỉnh thêm.
PHẦN III. KẾT LUẬN
Cuộc cách mạng công nghiệp 4.0, có sự đóng góp rất lớn của Tin học nói chung và lập trình nói riêng. Đề 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. Từ đó tạo sự hứng thú trong học tập và nghiên cứu cho học sinh.
Quảng Xương, ngày 22 tháng 4 năm 2018.
Người viết
Đỗ Chí Huấn
Ý KIẾN CỦA NHÀ TRƯỜNG:
...
...
...
...
...
...
...
...
...TÀI LIỆU THAM KHẢO
1. Sách giáo khoa Tin học Quyển 3	
2. Sách bài tập Tin học Quyển 3.