SKKN Ứng dụng thuật toán đệ quy – khử đệ quy trong giảng dạy bồi dưỡng học sinh giỏi
Các nội dung liên quan đến đệ quy, khử đệ quy, hay đệ quy quay lui không phải là nội dung quá mới trong việc giảng dạy, có thể dễ dàng tìm thấy các tài liệu tham khảo liên quan, nhưng chưa có tài liệu nào đầy đủ, chi tiết, bài tập đa dạng phong phú để các giáo viên cũng như các em học sinh có thể hiểu được toàn bộ kiến thức liên quan.
SỞ GIÁO DỤC VÀ ĐÀO TẠO QUẢNG TRỊ
TRƯỜNG THPT HƯỚNG HÓA
SÁNG KIẾN KINH NGHIỆM
Tên đề tài:
ỨNG DỤNG THUẬT TOÁN
ĐỆ QUY - KHỬ ĐỆ QUY TRONG GIẢNG
DẠY BỒI DƯỠNG HỌC SINH GIỎI
HỌ VÀ TÊN GIÁO VIÊN: NGUYỄN TIẾN LONG
TỔ TIN HỌC
TRƯỜNG THPT HƯỚNG HÓA
Hướng Hóa, Tháng 7 năm 2020
MỤC LỤC
PHẦN I. ĐẶT VẤN ĐỀ ....................................................................................4
1. LÝ DO CHỌN ĐỀ TÀI ................................................................................4
PHẦN II. NỘI DUNG.......................................................................................6
1.1. Khái niệm.................................................................................................6
1.2. Phân loại ...................................................................................................7
1.3. Thuật toán đệ quy .....................................................................................8
1.4. Chương trình con đệ quy ........................................................................11
1.4.1. Hàm đệ quy .........................................................................................11
1.4.2. Thủ tục đệ quy.....................................................................................11
1.7. Một số bài toán về đệ quy.......................................................................15
1.7.1. Bài toán tháp Hà Nội...........................................................................15
1.7.2. Bài toán chia thưởng ...........................................................................18
I. KẾT LUẬN.................................................................................................32
II. KIẾN NGHỊ ..............................................................................................32
2
PHẦN I. ĐẶT VẤN ĐỀ
1. LÝ DO CHỌN ĐỀ TÀI
Việc nâng cao chất lượng giáo dục mũi nhọn là một vấn đề cấp thiết hiện
nay được nhà trường và toàn ngành giáo dục tỉnh nhà đặc biệt quan tâm, chú trọng.
Bồi dưỡng học sinh giỏi là một nhiệm vụ quan trọng không thể thiếu của ngành
giáo dục nói chung và của các trường nói riêng đặc biệt là đối với mỗi một giáo
viên tham gia bồi dưỡng thì đây là một nhiệm vụ không dễ dàng.
Bồi dưỡng học sinh giỏi là cả một quá trình, không thể ngày một ngày hai, mà
phải có tính chiến lược dài trong suốt cả một quá trình, có thể một, hai hoặc ba
năm học. Chỉ có quá trình này mới cung cấp được tương đối đầy đủ các kiến thức
cần thiết cho học sinh và phát hiện chính xác khả năng học tập của các em, từ đó
mới có thể thành lập các đội tuyển tham dự kỳ thi học sinh giỏi các cấp đạt kết
quả như mong đợi.
Các nội dung liên quan đến đệ quy, khử đệ quy, hay đệ quy quay lui không
phải là nội dung quá mới trong việc giảng dạy, có thể dễ dàng tìm thấy các tài liệu
tham khảo liên quan, nhưng chưa có tài liệu nào đầy đủ, chi tiết, bài tập đa dạng
phong phú để các giáo viên cũng như các em học sinh có thể hiểu được toàn bộ
kiến thức liên quan. Phần bài tập đệ quy- khử đệ quy là phần bài tập khó thường
chiếm một phần điểm trong các đề thi học sinh giỏi, cũng là phần có số dạng bài
và phương pháp giải phong phú. Mặt khác các bài tập về đệ quy luôn gây nhiều
hứng thú và đôi khi sẽ gặp vấn đề khó giải quyết nếu như không hiểu tường tận
về nó.
Với những lý do trên và qua thực tiễn giảng dạy nhiều năm, tôi đã tìm hiểu
nghiên cứu, tham khảo tài liệu và xây dựng nên đề tài: “ỨNG DỤNG THUẬT
TOÁN ĐỆ QUY - KHỬ ĐỆ QUY TRONG GIẢNG DẠY BỒI DƯỠNG HỌC
SINH GIỎI” nhằm giúp cho giáo viên bồi dưỡng học sinh giỏi cũng như giúp các
em học sinh giỏi có kinh nghiệm trong việc áp dụng thuật toán đệ quy để lập trình
cho các bài toán.
2. MỤC ĐÍCH NGHIÊN CỨU
Nhằm giúp giáo viên và học sinh khi đứng trước một bài toán, xác định
được là bài toán đó có thể áp dụng được thuật toán đệ quy hay không? Và cách
giải cụ thể như thế nào? Từ đó tôi đề ra mục đích, nhiệm vụ của việc thực hiện đề
tài như sau:
3
- Giới thiệu khái niệm “thuật toán đệ quy”, giới thiệu khái niệm đệ quy,
chương trình con đệ quy, các bước xây dựng chương trình con đệ quy và cơ
chế thực hiện thuật toán đệ quy và một số bài toán đệ quy điển hình.
- Giới thiệu kỹ thuật khử đệ quy
3. ĐỐI TƯỢNG NGHIÊN CỨU
Sáng kiến “Ứng dụng thuật toán đệ quy – khử đệ quy trong giảng dạy bồi
dưỡng học sinh giỏi” có đối tượng nghiên cứu là các bài toán giải bằng thuật toán
đệ quy.
Nội dung đề tài sử dụng ngôn ngữ lập trình C++ để giải quyết các bài toán.
4. ĐỐI TƯỢNG KHẢO SÁT, THỰC NGHIỆM
Đề tài lấy đối tượng khảo sát, thực nghiệm là học sinh giỏi môn Tin học
trường THPT Hướng Hóa mà bản thân đã và đang trực tiếp giảng dạy.
5. PHƯƠNG PHÁP NGHIÊN CỨU
Chủ yếu là nghiên cứu đề tài, tham khảo tài liệu, ý kiến đóng góp của đồng
nghiệp và đặc biệt là đúc rút kinh nghiệm qua thực tiễn giảng dạy.
6. PHẠM VI VÀ THỜI GIAN NGHIÊN CỨU
Trong khuôn khổ của một đề tài sáng kiến tôi chỉ khái quát nội dung lý
thuyết và giải một số bài tập ứng dụng thuật giải đệ quy – khử đệ quy. Đề tài được
nghiên cứu trong quá trình học tập và giảng dạy, bồi dưỡng các đội tuyển học sinh
giỏi, giới hạn thời gian nghiên cứu trong 2 năm học: năm học 2018 - 2019 và 2019
- 2020.
4
PHẦN II. NỘI DUNG
1. THUẬT TOÁN ĐỆ QUY
1.1. Khái niệm
Đệ quy là một khái niệm cơ bản trong toán học và khoa học máy tính. Một
đối tượng được gọi là đệ quy nếu nó hoặc một phần của nó được định nghĩa thông
qua khái niệm về chính nó.
Ví dụ 1: Định nghĩa số tự nhiên bằng đệ quy như sau:
- 0 là số tự nhiên.
- Nếu k là số tự nhiên thì k+1 cũng là số tự nhiên.
Theo đó, ta sẽ có 1 = 0 +1 là số tự nhiên, 2 = 1+1 cũng là số tự nhiên, …Cứ
như vậy ta sẽ định nghĩa được các số tự nhiên khác lớn hơn. Do đó, số tự
nhiên là một khái niệm mang bản chất đệ quy.
Ví dụ 2: Định nghĩa xâu kí tự bằng đệ quy như sau:
- Xâu rỗng là một xâu kí tự.
- Một kí tự bất kỳ ghép với một xâu kí tự sẽ tạo thành một xâu mới.
Thuật toán đệ quy đóng vai trò quan trọng trong việc giải quyết nhiều bài
toán. Một thuật toán đệ quy là thuật toán có yêu cầu thực hiện lại chính thuật toán
đó với mức độ dữ liệu nhỏ hơn.
Trong lĩnh vực lập trình, một chương trình máy tính được gọi là đệ quy nếu
trong chương trình đó có lời gọi chính nó. Nhưng một chương trình không thể gọi
mãi chính nó, vì như vậy sẽ tạo ra một vòng lặp vô hạn. Do đó, một chương trình
đệ quy trước khi gọi lại chính nó bao giờ cũng có một thao tác kiểm tra điều kiện
dừng. Nếu điều kiện dừng thỏa mãn thì quá trình gọi đệ quy sẽ chấm dứt.
Nhìn chung, các chương trình đệ quy đều có những đặc điểm sau:
- Chương trình này có thể gọi lại chính nó, mục đích là giải quyết vấn
đề tương tự nhưng trong phạm vi nhỏ hơn.
- Vấn đề nhỏ hơn này cho tới một lúc nào đó sẽ đơn giản tới mức
chương trình có thể tự giải quyết được mà không cần gọi tới chính
nó nữa, khi đó chương trình đệ quy kết thúc.
Mô tả thuật toán đệ quy gồm 2 phần:
- Phần neo (phần cơ sở/phần dừng): mô tả trường hợp suy biến (cá
biệt) của đối tượng qua một thao tác cụ thể xác định.
- Phần quy nạp (phần đệ quy): mô tả đối tượng thông qua chính đối
tượng đó một cách trực tiếp hoặc gián tiếp.
Ví dụ 3: Xét bài toán tính n! (Với n là một số nguyên bất kỳ).
5
Ta có: n! = n(n-1)!
Do đó ta có thể mô tả bài toán dưới dạng đệ quy như sau:
1
khi n 0
khi n 0
n!
n(n -1)!
Với bài toán này ta xác định :
- Phần neo : khi n = 0 thì n! = 1.
- Phần quy nạp : Khi n>0 thì n ! = n(n-1) !
Ví dụ 4: Định nghĩa các số Fibonacci như sau :
1
khin 0 n 1
khin 1
F
n
F F
n-1
n-2
Hãy tính Fn với n cho trước.
Với bài toán này ta xác định :
- Phần neo: khi n = 0 hoặc n = 1 thì Fn = 1.
- Phần quy nạp: khi n>1 thì Fn = Fn-1 +Fn-2
Ưu điểm của phương pháp mô tả đệ quy: có thể thực hiện một số lượng lớn
các thao tác tính toán thông qua một thuật toán ngắn gọn, đơn giản (Mô tả một bài
toán lớn chỉ qua một số ít thao tác).
Hạn chế: Tốn bộ nhớ (nếu quản lý không tốt có thể gây tràn bộ nhớ) và thời
gian thực hiện.
Ví dụ 5 : Thuật toán đệ quy sử dụng ngay định nghĩa đệ quy của các số
Fibonacci ở ví dụ 4 như sau:
int F(int n)
{
if (n<2) return 1;
else return F(n-1) + F(n-2);
}
Qua đó, ta thấy thuật toán đệ quy trên rất ngắn gọn, đơn giản, dễ hiểu và
nêu bật lên bản chất của vấn đề nhưng do việc gọi đệ quy ở bài toán trên tạo ra
những tính toán thừa nhiều lần, không cần thiết gây lãng phí bộ nhớ và thời gian
thực hiện.
1.2. Phân loại
Các chương trình đệ quy thường chia thành 2 loại:
- Đệ quy trực tiếp: là loại đệ quy mà đối tượng được mô tả trực tiếp
qua nó: A mô tả qua A, B, C, …trong đó B, C, …không chứa A.
6
- Đệ quy gián tiếp: là loại đệ quy mà đối tượng được mô tả gián tiếp
qua nó: A được mô tả qua A1, A2, …, An, trong đó có một Ai được
mô tả qua A.
Ví dụ 1: Chương trình tính ước số chung lớn nhất của hai số nguyên dựa
vào thuật toán Euclide sau là chương trình con đệ quy thuộc dạng đệ quy trực tiếp:
int UCLN(int m, int n)
{
if (n==0) return m;
else
return UCLN (n, m % n);
}
Ví dụ 2: Mô tả đệ quy hai dãy số {Xn} và {Yn} sau thuộc dạng đệ quy gián
tiếp:
X0 = 1; Xn = Xn-1 + Yn-1;
Y0 = 1; Yn = n2Xn-1 + Yn-1;
1.3. Thuật toán đệ quy
Thuật toán đệ quy là thuật toán có chứa thao tác gọi lại chính nó. Thuật toán
đệ quy cho phép mô tả một dãy lớn các thao tác bằng một số ít các thao tác trong
đó có chứa thao tác gọi lại thuật toán. Tức là nếu ta có lời giải S cho bài toán P, ta
lại sử dụng lời giải đó cho bài toán P’ giống P nhưng kích thước nhỏ hơn thì lời
giải S đó được gọi là lời giải đệ quy (thuật toán đệ quy).
Thực thi thuật toán đệ quy có thể dẫn tới một tiến trình gọi đệ quy không
kết thúc khi đó không có khả năng gặp trường hợp neo (điều kiện dừng), vì vậy ta
cần quan tâm đến điều kiện dừng. Để kiểm soát quá trình gọi đệ quy của thuật
toán đệ quy P người ta thường gắn thao tác gọi P với việc kiểm tra một điều kiện
B xác định và biến đổi qua mỗi lần gọi P và quá trình gọi P sẽ dừng khi B không
còn thỏa.
Mô hình tổng quát của một thuật toán đệ quy được biểu diễn như sau:
P
if (B) P[S, P]
P[S, if (B) P]
hoặc P
Thông thường với thuật toán đệ quy P, để đảm bảo P sẽ dừng sau n lần gọi
ta chọn B là (n>0). Khi đó, mô hình tổng quát của một thuật toán đệ quy có dạng
như sau:
P(n)
if (n>0) P[S, P(n-1)]
P[S, if (n>0) P(n-1)]
hoặc P(n)
7
Một số dạng thuật toán đệ quy đơn giản thường gặp:
- Đệ quy tuyến tính:
+ Một hàm được gọi là đệ quy tuyến tính nếu bên trong thân hàm
có duy nhất một lời gọi hàm lại chính nó một cách trực tiếp (tường
minh).
+ Là dạng đệ quy trực tiếp và đơn giản nhất có dạng sau:
P
{if(điều kiện dừng)
thực hiện S;
else
{
thực hiên S*;
gọi P;
}
}
Với S, S* là các thao tác không đệ quy.
Ví dụ: Tính tổng các chữ số của số nguyên dương n.
Ta phân tích bài toán này dưới dạng đệ quy như sau:
Gọi Tong(n) là tổng các chữ số của số nguyên dương n. Ta có:
Tong(n)
{
if(n=0) Tong = 0;
else
Tong=Tong(n / 10) +(n % 10);
}
Trong đó: P là Tong(n), S là lệnh gán Tong = 0, S* là lệnh rỗng.
Viết hàm bằng ngôn ngữ C++:
int TCS(int n)
{
if (n==0) return 0;
else
return (n % 10)+ TCS(n / 10);
}
- Đệ quy nhị phân :
+ Một hàm được gọi là đệ quy nhị phân nếu bên trong thân hàm
có hai lời gọi hàm lại chính nó một cách trực tiếp có dạng sau:
P
{if(điều kiện dừng)
thực hiện S;
else
8
{
thực hiên S*;
gọi P; gọi P;
}
}
Với S, S* là các thao tác không đệ quy.
Ví dụ: Hàm Fibo tính số hạng thứ n của dãy Fibonacci.
Ta phân tích bài toán này dưới dạng đệ quy như sau:
Gọi Fibo(n) là số hạng thứ n của dãy Fibonacci. Ta có:
Fibo(n) {if((n==0)||(n==1)) Fibo=1;
else
Fibo=(Fibo(n-1)+Fibo(n-2));
}
Trong đó: P là Fibo(n), S là lệnh gán Fibo = 1, S* là lệnh rỗng.
Viết hàm bằng ngôn ngữ lập trình C++:
int F(int n)
{
if (n==0) || (n==1) return 1;
else
return F(n-1)+F(n-2);
}
- Đệ quy phi tuyến
Là dạng đệ quy trực tiếp mà lời gọi đệ quy được thực hiện bên
trong vòng lặp có dạng như sau:
P
{if(điều kiện dừng)
thực hiện S;
else
for
(i=chỉ
số
đầu;i<=chỉ số
cuối;i++)
{
thực hiên S*;
gọi P;
}
}
Ví dụ: Cho dãy A(n) được xác định theo công thức sau:
9
n
, n 6
A(n)
A(n - 5) A(n - 4) A(n - 3) A(n - 2) A(n -1) , n 6
Gọi A(n) là tổng các số được xác định theo công thức trên. Ta có:
A(n) {if(n<6) s=n;
else
{
s=0;
for (i=5; i>=1;i--)
s=s+A(n-i);
}
A=s;}
Trong đó: P là A(n), S là lệnh gán s = n, S* là lệnh gán s = 0.
int A(int n)
{
int S,i;
if (n<6) S=n;
else
{
S=0;
for (i=5;i>=1;i--)
S= S + A (n-i);
}
return S;
}
1.4. Chương trình con đệ quy
1.4.1. Hàm đệ quy
Hàm đệ quy là hàm mà trong thân hàm có lời gọi lại chính nó.
Ví dụ: Hàm đệ quy tính n!
double GT(int n)
{
if (n==0)
else
return 1;
return n*GT(n-1);
1.4.2. Thủ tục đệ quy
}
10
Thủ tục đệ quy là thủ tục có chứa lệnh gọi đến chính nó. Thủ tục đệ quy
thường được sử dụng để mô tả các thao tác trên cấu trúc dữ liệu có tính đệ quy.
Ví dụ: Thủ tục đệ quy in đảo ngược một số nguyên dương n cho trước như
sau:
void IDN(int n)
{
if (n<10) cout<<n;
else
{
Cout<<n % 10;
IDN(n / 10);
}
}
1.5. Các bước xây dựng chương trình con đệ quy
Để xây dựng thuật toán giải một bài toán có tính đệ quy bằng phương pháp
đệ quy ta thực hiện 3 bước sau:
- Bước 1: Thông số hóa bài toán:
+ Tổng quát hóa bài toán cụ thể cần giải thành bài toán tổng quát.
+ Tìm ra các thông số cho bài toán tổng quát (các thông số điều khiển: các
thông số mà độ lớn của chúng đặc trưng cho độ phức tạp của bài toán, và
giảm đi một lần gọi đệ quy).
- Bước 2: Tìm các trường hợp neo cùng thuật toán giải tương ứng:
+ Đây là những trường hợp suy biến của bài toán tổng quát, là các trường
hợp tương ứng với giá trị biến của các biến điều khiển (trường hợp kích
thước bài toán nhỏ nhất) mà thuật toán giải không đệ quy.
- Bước 3: Tìm thuật toán giải trong trường hợp tổng quát bằng cách phân rã
bài toán theo kiểu đệ quy:
+ Tìm thuật toán giải bài toán trong trường hợp tổng quát bằng cách phân
nó thành các thành phần:
- Thuật toán không đệ quy
- Bài toán trên nhưng có kích thước nhỏ hơn
Ví dụ: Tính số hạng thứ n của dãy số Fibonacci được định nghĩa:
1
khin 0n 1
khin 1
F
n
F F
n-1
n-2
11
Tải về để xem bản đầy đủ
33 trang
30/07/2024
1160
Bạn đang xem 11 trang mẫu của tài liệu "SKKN Ứng dụng thuật toán đệ quy – khử đệ quy trong giảng dạy bồi dưỡng học sinh giỏi", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- skkn_ung_dung_thuat_toan_de_quy_khu_de_quy_trong_giang_day_b.docx
