SÁNG KIẾN KINH NGHIỆM
ĐỀ TÀI:
"MỘT SỐ BIỆN PHÁP RÈN LUYỆN KỸ NĂNG GIẢI BÀI TOÁN
TRUY HỒI BẰNG CẤU TRÚC LẶP TRONG PASCAL"
1

A. ĐẶT VẤN ĐỀ
I. Lời mở đầu :
Sự phát triển mạnh mẽ của công nghệ thông tin đã làm cho xã hội có nhiều nhận thức
mới về cách tổ chức các hoạt động. Nhiều quốc gia trên thế giới ý thức được rất rõ tầm
quan trọng của tin học và có những đầu tư lớn cho lĩnh vực này, đặc biệt trong giáo dục
nhằm nâng cao dân trí về tin học và đào tạo nguồn nhân lực có chất lượng cao.
Người Việt Nam có nhiều tố chất thích hợp với ngành khoa học này, vì thế chúng ta hi vọng
có thể sớm hoà nhập với khu vực và trên thế giới về tốc độ phát triển nền công nghệ thông tin.
Đảng, Nhà nước ta đã nhận thấy được tầm quan trọng của ngành Tin học và đã đưa môn học
này vào nhà trường phổ thông như những môn khoa học khác bắt đầu từ năm học 2006-2007.
Bộ trưởng Bộ GDĐT cũng đã đưa ra chỉ thị số 55/2008/CT- BGTĐT ngày 30/9/2008 về tăng
cường giảng dạy, đào tạo và ứng dụng công nghệ thông tin trong ngành giáo dục giai đoạn
2008-2011.
Ngành Giáo dục và Đào tạo đang nỗ lực đổi mới phương pháp dạy học theo hướng phát
huy tính tích cực chủ động của học sinh. Cốt lõi của việc đổi mới phương pháp dạy học ở
trường phổ thông là giúp học sinh hướng tới việc học tập chủ động, chống lại thói quen
học tập thụ động, học sinh có thể tự học, tự rèn luyện thông qua một số bài tập, dạng bài
tập cụ thể.
II. Thực trạng của vấn đề nghiên cứu :
1. Thực trạng :
Tin học là một môn học mới ở các trường phổ thông nên học sinh còn nhiều bỡ ngỡ khi
tiếp cận với môn học này. Trong đó nội dung tin học lớp 11 là một nội dung tương đối
khó với đa số học sinh. Việc học ngôn ngữ lập trình Turbo Pascal là khởi đầu cho việc
tiếp cận ngôn ngữ lập trình bậc cao. Học sinh được làm quen với nhiều khái niệm, thuật

sử dụng cấu trúc lặp trong Pascal phù hợp với từng bài toán cụ thể.
- Một số không ít học sinh khi giải bài toán có dạng truy hồi chưa phân biệt được
nên sử dụng cấu trúc lặp với số lần biết trước hay chưa biết trước. Xuất phát
từ cơ sở trên, tôi mạnh dạn đề xuất SKKN “Rèn luyện kĩ năng sử dụng cấu trúc lặp
trong Pascal để giải một số bài toán truy hồi cho học sinh lớp 11”.
B. GIẢI QUYẾT VẤN ĐỀ
I. Bài toán truy hồi và cấu trúc lặp :
1. Bài toán truy hồi :
Trong khoa học tính toán ngày nay, phép truy hồi là thuật toán cơ bản để giải một số bài
toán. Ưu điểm của phương pháp truy hồi là ở chỗ nó dùng một công thức nhất định để
diễn tả những phép tính lặp đi lặp lại bất chấp số lần lặp lại là bao nhiêu. Chẳng hạn với
bài toán cấp số cộng là một ví dụ :
3

Cho
0
1
U
( n 1)
n n
a
U U d
−
=


= + ∀ ≥

với a là một số cho trước và d là hằng số cố định (công
sai).

1. Sử dụng cấu trúc For … To Do
* Cấu trúc:
4

for <biến đếm>:= <biểu thức 1> to <biểu thức 2> do <câu lệnh>;
* Trong đó:
- for, to, do là các từ khoá.
- <biến đếm> là một biến có kiểu đếm được (nguyên, kí tự, liệt kê, logic…)
- <biểu thức 1>, <biểu thức 2> là các biểu thức có giá trị cùng kiểu với <biến đếm>
- <câu lệnh> là một câu lệnh, có thể là câu lệnh đơn hoặc câu lệnh phức.
* Hoạt động:
Câu lệnh viết sau từ khóa do sẽ được thực hiện tuần tự, với biến đếm lần lượt nhận các
giá trị liên tiếp tăng từ giá trị đầu đến giá trị cuối, nếu giá trị đầu lớn hơn giá trị cuối thì
vòng lặp không được thực hiện.
Ví dụ 1: Với a là số nguyên và a > 2, tính tổng:

1 1 1 1

1 2 100
S
a a a a
= + + + +
+ + +
(SGK Tin học 11 – Trang 42)
Phân tích:
Với bài toán trên dễ thấy ta có công thức truy hồi để tính giá trị S như sau:
0
1
S
a

Ví dụ 2: Lập trình tính giai thừa của một số nguyên n (do giới hạn lưu trữ số nguyên cho
n<8).
Phân tích:
Giai thừa của n: n! = 1.2…n (tích các số tự nhiên từ 1 đến n). Không có công thức tổng
quát để tính n! nhưng ta có công thức truy hồi sau:



=
=
)!1n.(n-n!
1!0
Đặt g
n
=n!, theo công thức trên ta có:
0
n n-1
g =1
g =g .n



Như vậy ta có chương trình tính giai thừa như sau:
program Vidu_2;
var n, i, g : integer;
begin
writeln('Chuong trinh tinh n! ');
write('Nhap (n<8): ');
readln(n);
g := 1;

Toàn văn chương trình:
program Vidu_3;
var
i, f0, f1, f2 : integer;
begin
writeln('Chuong trinh tinh cac so Fibonaxi tu 1 den 20 ');
f1 := 1; f2 := 1;
writeln('F1 = 1');
writeln('F2 = 1');
for i := 3 to 20 do
begin
f0 := f1 + f2;
writeln('F',i,' = ',f0);
f1 := f2;
f2 := f0;
end;
readln;
7

end.
2. Sử dụng cấu trúc for downto do
* Cấu trúc:
for <biến đếm>:= <biểu thức 1> downto <biểu thức 2> do <câu lệnh>;
* Trong đó:
- for, downto, do là các từ khoá.
- <biến đếm> là một biến có kiểu đếm được (nguyên, kí tự, liệt kê, logic…)
- <biểu thức 1>, <biểu thức 2> là các biểu thức có giá trị cùng kiểu với <biến đếm>
- <câu lệnh> là một câu lệnh, có thể là câu lệnh đơn hoặc phức.
* Hoạt động:
Câu lệnh viết sau từ khóa do sẽ được thực hiện tuần tự, với biến đếm lần lượt nhận các

+

Với n từ 50 giảm dần về 1
Việc cộng vào tổng Y được lặp lại 50 lần, giá trị n khi tham gia vòng lặp là 50
và sau mỗi lần lặp n giảm đi 1 cho đến khi n =1 thì dừng. Như vậy số lần lặp là biết
trước, biến n được sử dụng là một biến đếm giảm từ 50 về 1, tổng cần tính là Y
0

Ta viết chương trình như sau:
program vidu_4;
var Y: real;
n : integer;
begin
clrscr;
Y := 0;
for n := 50 downto 1 do
Y := Y + n/(n+1);
writeln('Tong Y la: ',Y:10:4);
readln;
end.
Tuy nhiên trong một số trường hợp thì chỉ có thể dùng một cấu trúc, đặc biệt là khi
tính các công thức truy hồi. Ta xét một ví dụ dùng for … downto … do thích hợp hơn:
Ví dụ 5:
Tính tổng S =
2 4 2n+ +
với n là một số tự nhiên nhập từ bàn phím.
9
n dấu căn

Phân tích:

program Vidu_5;
var
i,n : integer;
s : real;
begin
write('Nhap mot so tu nhien n = ');
readln(n);
s:=0;
for i := n downto 1 do
s := sqrt (2 * i + s);
writeln('Ket qua can tinh: s = ',s:10:5);
readln;
end.
10

3. Sử dụng cấu trúc While … do…
* Cấu trúc:
While <điều kiện> do <câu lệnh>;
* Trong đó:
- While, do là các từ khoá;
- <điều kiện> là một biểu thức logic;
- <câu lệnh> là một câu lệnh. Có thể là câu lệnh đơn hoặc câu lệnh phức.
* Cấu trúc hoạt động như sau:
- Bước 1: Tính <biểu thức>;
- Bước 2: Nếu kết quả là đúng (true) thì thực hiện <câu lệnh> và quay lại bước 1, ngược
lại thì chuyển sang câu lệnh tiếp theo trong chương trình.
Ví dụ 6: Tính tổng
1 1 1
1
3 5 2 1

s =0
s =s +r



và S
n
≈ S khi r
n
<= 10
-4
.
Quá trình tính là một quá trình lặp cho đến khi điều kiện dừng xảy ra.
Toàn bộ chương trình:
program vidu_6;
var
s,r : real;
n : integer;
begin
writeln('Chuong trinh tinh tong chuoi S = 1+1/3+1/5+ ');
s := 0; n := 0; r:= 1/(2*n+1);
11

While r>= 1E-4 do
Begin
s := s + r; n := n + 1; r:= 1/(2*n+1);
end;
writeln('Tong can tinh voi do chinh xac 1E-4 la S = ',s :10:6);
readln;
end.

(n là số tự nhiên bắt đầu từ 1)
Ta có:
0
n n-1 n
s =0
s =s +r



và S
n
≈ S khi r
n
<= 10
-6
.
Quá trình tính là một quá trình lặp cho đến khi điều kiện dừng xảy ra.
Toàn bộ chương trình:
program vidu_7;
var s,r : real;
n : integer;
begin
writeln(' Chuong trinh tinh tong chuoi S = 1+1/4+1/9+ ');
s := 0; n := 1; r:= sqr(1/n);
While r>= 1E-6 do
Begin
s := s + r; n := n + 1; r := sqr(1/n);
end;
writeln('Tong can tinh voi do chinh xac 1E-6 la S = ',s :10:6);
12

cho đến khi S
n
>100 thì dừng.
* Toàn văn chương trình:
program Vidu_8;
var
n : integer;
s : real;
Begin
n := 0;
s := 75;
while s<=100 do
begin
n := n + 1;
s := s + s*0.017;
end
writeln('Dan so hien nay la 75 trieu. Ti le tang 1.7%.');
writeln('Sau ',n,' nam thi dan so dat 100 trieu nguoi.');
readln;
13

End.
4. Sử dụng cấu trúc lặp Repeat … Until…
* Cấu trúc:
Repeat
<câu lệnh>;
until <điều kiện>;
* Trong đó:
- Repeat, until là từ khoá;
- <câu lệnh>; là một hay nhiều câu lệnh cách nhau bởi dấu ;

n
r
=


= +

đến khi S > a thì dừng.
Quá trình tính là một quá trình lặp cho đến khi điều kiện dừng xảy ra.
* Toàn bộ chương trình:
Program vidu_9;
Uses crt;
Var a, S : real;
14

n: longint;
Begin
Clrscr;
Write(‘Nhap gia tri cua a:’); Readln(a);
S:=0; n:=1;
Repeat
S:= S+ 1/n;
n:= n+1;
Until S>a;
Writeln(‘ So nguyen n la:’, n );
Readln;
End.
Ví dụ 10: Turbo Pascal đã có hàm exp để tính e
x
, tuy nhiên e

0
n n-1
s 1
s s
n
r
=


= +

và
S
≈
n
s
khi r
n
<= 2*10
-6
.
Với
n
n
x
r
n!
=
ta cũng có thể tính theo công thức truy hồi:
0

cos1 cos1+cos2 cos1+cos2+ cosn
= + + +
sin1 sin1+sin2 sin1+sin2+ sinn
T
với số n là số nguyên
nhập từ bàn phím.
Bài tập 2: Tính các giá trị biểu thức sau với số n tự nhiên nhập từ bàn phím:
1 2 2 3 4 1 2S . . . n(n ) ( n)
= + + +
Bài tập 3: Viết chương trình nhập số thực x, tính các giá trị sau với độ chính xác của số
hạng cuối cùng là 10
-6
:

!n2
x
)1(
!4
x
!2
x
1xcos

)!1n2(
x
)1(
!5
x
!3
x

trình có sử dụng cấu trúc lặp. Đồng thời nâng cao việc yêu thích học tin học đối với một
bộ phận học sinh, trong đó có một số em có khả năng tìm hiểu sâu hơn về các dạng bài
toán lập trình.
2. Kiến nghị, đề xuất :
Sau khi thực hiện đề tài này tôi xin mạnh dạn đưa ra một số đề xuất như sau :
- Để học sinh thực sự hiểu rõ các loại cấu trúc lặp trong lập trình mà cụ thể đối với học
sinh lớp 11 là ngôn ngữ lập trình Pascal thì cần tăng cường hơn nữa lượng thời gian trong
phân phối chương trình để học sinh rèn luyện các dạng bài tập về cấu trúc lặp, giúp học
sinh nắm chắc cú pháp, cách sử dụng cấu trúc này.
- Giáo viên cần đưa ra các bài tập để phù hợp với từng đối tượng học sinh, với mỗi
loại cấu trúc lặp nên đưa ra bài có tính đặc trưng để học sinh ghi nhớ được cách sử dụng
và cú pháp của cấu trúc lặp.
17

- Với đối tượng học sinh khá giỏi thì có thể khai thác sâu hơn một số bài toán khó của
dạng bài toán truy hồi mà có thể áp dụng cấu trúc lặp để giải (chẳng hạn bài toán Tháp
Hà Nội ).
C. KẾT LUẬN:
Đối với đa số học sinh, việc học lập trình là tương đối khó đối với các em, đòi hỏi các em
phải có kiến thức nhất định về mặt toán học, đồng thời phải biết vận dụng phù hợp với
từng cấu trúc cụ thể của ngôn ngữ lập trình mới có thể lập trình giải quyết bài toán đó.
Tuy nhiên, nếu như được rèn luyện kĩ năng, áp dụng từng cấu trúc cụ thể vào từng dạng
bài toán, học sinh sẽ ghi nhớ, sử dụng thành thạo cấu trúc, từ đó các em thấy hứng thú với
việc học lập trình để giải các bài toán.
Với đối tượng học sinh khá giỏi thì việc khai thác cách để giải các bài toán truy hồi bằng
cấu trúc lặp sẽ giúp học sinh hứng thú học lập trình và tìm hiểu sâu hơn các dạng bài toán
khác. Giáo viên nên khuyến khích học sinh để các em học tập và nghiên cứu.
Trên đây là một số kinh nghiệm của tôi qua nhiều năm liền dạy ở khối lớp 11, trường
THPT Hậu Lộc 4, cũng như tham khảo qua nhiều nguồn thông tin, tư liệu khác nhau, rất
mong được sự đóng góp của các đồng nghiệp nhằm giúp đề tài của tôi được hoàn thiện