Sáng kiến kinh nghiệm THPT: Ứng dụng thuật toán đệ quy - khử đệ quy trong giảng dạy bồi dưỡng học sinh giỏi

Chia sẻ: Ganuongmuoiot | Ngày: | Loại File: PDF | Số trang:34

Thêm vào BST

Báo xấu

22
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu nghiên cứu của đề tà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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Sáng kiến kinh nghiệm THPT: Ứng dụng thuật toán đệ quy - khử đệ quy trong giảng dạy bồi dưỡng học sinh giỏi

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 ĐỀ.................................................................................. 3 1. LÝ DO CHỌN ĐỀ TÀI .............................................................................. 3 2. MỤC ĐÍCH NGHIÊN CỨU ...................................................................... 3 3. ĐỐI TƯỢNG NGHIÊN CỨU .................................................................... 4 4. ĐỐI TƯỢNG KHẢO SÁT, THỰC NGHIỆM .......................................... 4 5. PHƯƠNG PHÁP NGHIÊN CỨU .............................................................. 4 6. PHẠM VI VÀ THỜI GIAN NGHIÊN CỨU............................................. 4 PHẦN II. NỘI DUNG .................................................................................... 5 1. THUẬT TOÁN ĐỆ QUY ........................................................................... 5 1.1. Khái niệm.............................................................................................. 5 1.2. Phân loại ................................................................................................ 6 1.3. Thuật toán đệ quy ................................................................................... 7 1.4. Chương trình con đệ quy ...................................................................... 10 1.4.1. Hàm đệ quy....................................................................................... 10 1.4.2. Thủ tục đệ quy .................................................................................. 11 1.5. Các bước xây dựng chương trình con đệ quy........................................ 11 1.6. Cơ chế thực hiện thuật toán đệ quy...................................................... 12 1.7. Một số bài toán về đệ quy..................................................................... 14 1.7.1. Bài toán tháp Hà Nội......................................................................... 14 1.7.2. Bài toán chia thưởng ......................................................................... 17 1.7.3. Bài toán sắp xếp mảng – Thuật toán sắp xếp nhanh .......................... 19 1.7.4. Bài toán tìm kiếm – Thuật toán tìm kiếm nhị phân............................ 23 2. KỸ THUẬT KHỬ ĐỆ QUY .................................................................... 26 2.1. Lý do sử dụng kỹ thuật khử đệ quy ..................................................... 26 2.2. Một số kỹ thuật khử đệ quy đơn giản .................................................. 27 2.3. Khử một số dạng đệ quy thường gặp .................................................... 27 2.4. Nhận xét chung về kỹ thuật khử đệ quy ................................................ 31 PHẦN III. KẾT LUẬN VÀ KIẾN NGHỊ .................................................. 32 I. KẾT LUẬN .............................................................................................. 32 II. KIẾN NGHỊ ........................................................................................... 32 TÀI LIỆU THAM KHẢO............................................................................ 33 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. 5
Ví dụ 3: Xét bài toán tính n! (Với n là một số nguyên bất kỳ). 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 n!    n(n - 1)! khi n  0 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 khi n  0  n  1 Fn   Fn-1  Fn -2 khi n  1 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
- Đệ 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ố {X n} 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] hoặc P  P[S, if (B) 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)] 7
hoặc P(n)  P[S, if (n>0) P(n- 1)] 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: 8
P  {if(điều kiện dừng) thực hiện S; else { 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
Ví dụ: Cho dãy A(n) được xác định theo công thức sau: 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=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=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) return 1; else return n*GT(n-1); 10
} 1.4.2. Thủ tục đệ quy 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
1 khi n  0  n  1 Fn    Fn-1  Fn-2 khi n  1 Xây dựng chương trình con đệ quy để giải bài toán trên theo 3 bước như sau: Bước 1: Ta gọi thuật toán giải bài toán ở mức tổng quát là hàm Fibo(n) chứa 1 thông số n, với n thuộc kiểu số nguyên và n là thông số quyết định độ phức tạp của bài toán. Bước 2: Với n2 thì: Fibo(n) = Fibo(n-1)+Fibo(n-2). 1.6. Cơ chế thực hiện thuật toán đệ quy Trạng thái của tiến trình xử lý một thuật toán ở một thời điểm được đặc trưng bởi các biến và lệnh cần thực hiện kế tiếp. Với tiến trình xử lý một thuật toán đệ quy ở từng thời điểm thực hiện, cần lưu trữ cả các trạng thái xử lý đang còn dang dở. Đặc điểm của cơ chế thực hiện thuật toán đệ quy là việc thực thi lời gọi đệ quy sinh ra lời gọi đệ quy mới cho đến khi gặp trường hợp neo (trường hợp suy biến) cho nên để thực thi thuật toán đệ quy cần có cơ chế lưu trữ thông tin thỏa các yêu cầu sau: - Ở mỗi lần gọi phải lưu trữ thông tin trạng thái con dang dở của tiến trình xử lý ở thời điểm gọi. Số trạng thái này bằng số lần gọi chưa được hoàn tất. - Khi thực hiện xong một lần gọi, cần khôi phục lại toàn bộ thông tin trạng thái trước khi gọi. - Lệnh gọi cuối cùng (ứng với trường hợp neo) sẽ được hoàn tất đầu tiên, thứ tự dãy các lệnh gọi được hoàn tất ngược với thứ tự gọi, tương ứng dãy thông tin trạng thái được hồi phục theo thứ tự ngược với thứ tự lưu trữ. Cấu trúc dữ liệu cho phép lưu trữ dãy thông tin thỏa 3 yêu cầu trên là câu trúc lưu trữ thỏa luật LIFO (Last In First Out). Một kiểu cấu trúc lưu trữ thường được sử dụng trong trường hợp này là cấu trúc ngăn xếp (Stack). Ví dụ 1: Xét thuật toán đệ quy tính n giai thừa: Ta có: GT(n) { if n=0 GT=1 else GT=n*GT(n-1); } 12
Giả sử với n = 3, khi đó thuật toán đệ quy tính n giai thừa sẽ được thực hiện như sau: GT(3)=3*GT(2) GT(2)=2*GT(1) GT(1)=1*GT(0) GT(0)=1 Các lời gọi đệ quy khi thực hiện hàm GT(3) Qua hình 2, ta thấy khi thực hiện lời gọi GT(3) sẽ phát sinh lời gọi GT(2), đồng thời phải lưu trữ thông tin trạng thái xử lý còn dang dở (GT(3)=3*GT(2)), để thực hiện lời gọi GT(2) thì lại phát sinh lời gọi GT(1), đồng thời vẫn phải lưu trữ thông tin trạng thái xử lý còn dang dở (GT(2)=2*GT(1)), cứ tiếp tục như vậy cho đến khi gặp trường hợp neo GT(0)=1. Tiếp sau quá trình gọi là quá trình xử lý ngược được thực hiện như sau: - Dùng GT(0) để tính GT(1) theo sơ đồ xử lý còn lưu trữ. - Dùng GT(1) để tính GT(2) theo sơ đồ xử lý còn lưu trữ. - Dùng GT(2) để tính GT(3) theo sơ đồ xử lý còn lưu trữ. Đồng thời với quá trình xử lý ngược là quá trình xóa bỏ các thông tin về thuật toán xử lý trung gian (quá trình thu hồi bộ nhớ). Ví dụ 2: Xét thuật toán tính tính số Fibonacci thứ n như sau: Fib(n)  {if((n==0)||(n==1)) Fib=1; else Fib= Fib(n-1)+Fib(n-2); } Lời gọi Fibo(5) sẽ dẫn đến việc thực hiện theo sơ đồ sau: 13
Fib(5)=Fib(4)+Fib(3) Fib(4)=Fib(3)+Fib(2) Fib(3)=Fib(2)+Fib(1) Fib(3)=Fib(2)+Fib(1) Fib(2)=Fib(1)+Fib(0) Fib(2)=Fib(1)+Fib(0) Fib(1)=1 Fib(2)=Fib(1)+Fib(0) Fib(1)=1 Fib(1)=1 Fib(0)=1 Fib(1)=1 Fib(0)=1 Fib(1)=1 Fib(0)=1 Các lời gọi đệ quy được thực hiện khi gọi hàm Fib(5) Khi thực hiện lời gọi Fib(5) sẽ phát sinh lời gọi Fib(4) tiếp đến là lời gọi Fib(3), đến khi thực hiện lời gọi Fib(4) lại dẫn đến lời gọi Fib(3) và Fib(2) và cứ tiếp tục như vậy cho đến khi gặp trường hợp neo Fib(1) hoặc Fib(0) thì dừng việc gọi đệ quy. Tiếp sau quá trình gọi là quá trình xử lý ngược được thực hiện để cho ra kết quả Fib(5). Qua hai ví dụ minh họa về cơ chế hoạt động của thuật toán đệ quy, ta rút ra được một nhận xét đó là mặc dù chương trình đệ quy ngắn gọn, thể hiện rõ bản chất của vấn đề cần giải quyết nhưng hoạt động của chương trình đệ quy không tường minh, làm người đọc khó hiểu, khó hình dung chương trình sẽ tính toán như thế nào trong lúc chạy chậm chương trình. 1.7. Một số bài toán về đệ quy 1.7.1. Bài toán tháp Hà Nội Có 3 cột A, B, C và cột A hiện có n đĩa, trong đó, đĩa nhỏ được nằm trên đĩa lớn. Yêu cầu của bài toán là hãy chuyển n đĩa từ cột A sang cột C theo cách: - Mỗi lần chỉ chuyển 1 đĩa. - Khi chuyển có thể dùng cột trung gian B. - Trong suốt quá trình chuyển các đĩa ở các cột thì đĩa có kích thước lớn hơn phải được đặt ở dưới. 14
Cột A Cột B Cột C Hình 1. Bài toán Tháp Hà Nội Phân tích bài toán Xác định Input, Output: - Input: số lượng đĩa n, 3 cột A, B, C. - Output: in ra màn hình quy trình để chuyển n đĩa từ cột A sang cột C đúng quy định. Phân tích bài toán: - Trường hợp n = 1: chuyển đĩa từ cột A sang cột C - Trường hợp n = 2: + Chuyển đĩa thứ nhất từ cột A sang cột B. + Chuyển đĩa thứ hai từ cột A sang cột C. + Chuển đĩa thứ nhất từ cột B sang cột C. - Trường hợp n>2: + Chuyển (n-1) đĩa từ cột A sang cột B. + Chuyển đĩa thứ n từ cột A sang cột C. + Chuển (n-1) đĩa từ cột B sang cột C. Thông số hóa bài toán Ta gọi thuật toán giải bài toán ở mức tổng quát là thủ tục ThapHN(n,A,B,C) chứa 4 thông số n, A, B, C. Trong đó, n thuộc kiểu số nguyên, A, B, C thuộc kiểu ký tự và trong 4 thông số thì thông số n là thông số quyết định độ phức tạp của bài toán. Trường hợp neo và thuật toán tương ứng Với n = 1, bài toán tổng quát suy biến thành bài toán đơn giản ThapHN(1,A,B,C) và trong trường hợp này thuật toán giải bài toán ThapHN(1,A,B,C) chỉ thực hiện một thao tác cơ bản đó là chuyển 1 đĩa từ cột A sang cột C (sử dụng lệnh đưa thông báo bước chuyển ra màn hình). Phân rã bài toán trong trường hợp tổng quát Ta có thể phân rã bài toán ThapHN(k,A,B,C): chuyển k (k>1) đĩa từ cột A sang cột C lấy cột B làm cột trung gian ta thực hiện tuần tự 3 công việc sau: 15
- Chuyển (k-1) đĩa từ cột A sang cột B lấy cột C làm cột trung gian khi đó ta có thủ tục ThapHN(k-1,A,C,B) (bài toán ThapHN với n=k-1, A=A, B=C, C=B). - Chuyển 1 đĩa thứ k từ cột A sang cột C: đưa thông báo bước chuyển ra màn hình - Chuyển (k-1) đĩa từ cột B sang cột C lấy cột A làm cột trung gian khi đó ta có thủ tục ThapHN(k-1,B,A,C) (bài toán ThapHN với n=k-1, A=B, B=A, C=C). Vậy thuật toán trong trường hợp tổng quát (n>1) là: ThapHN(n,A,B,C)  { ThapHN(k-1,A,C,B); writeln(A,’->’,C); ThapHN(k-1,B,A,C); } Mã hóa thuật toán #include using namespace std; void THN(int n , char a, char b, char c ){ if(n==1){ cout
1.7.2. Bài toán chia thưởng Có m phần thưởng đem chia cho n học sinh giỏi đã được xếp hạng sao cho học sinh giỏi hơn không ít phần thưởng hơn. Có bao nhiêu cách khác nhau để thực hiện cách chia? Ta thấy ngay rằng việc tìm ra lời giải cho bài toán sẽ không dễ dàng nếu ta không tìm ra cách thích hợp để tiếp cận với nó. Ta sẽ tìm thuật toán giải bài toán bằng phương pháp đệ quy. Phân tích bài toán Xác định Input, Output của bài toán: - Input: m, n - Output: số cách chia. Ta mã hóa n đối tượng theo thứ tự xếp hạng 1, 2, 3, 4, …, n và Si là số phần thưởng mà học sinh thứ i nhận được. Khi đó, các điều kiện ràng buộc lên cách chia là: Si 0 S1  S2  S3  S4 … Sn S1 + S2 + S3 + S4 +… + Sn = m Ví dụ: Với m = 5 và n = 3 ta có 5 cách chia như sau: 5 0 0 4 1 0 3 2 0 3 1 1 2 2 1 Thông số hóa bài toán Ta sẽ giải bài toán ở mức độ tổng quát: Tìm số cách chia m vật (phần thưởng) cho n đối tượng (học sinh) có thứ tự. Gọi Chiathuong(m,n) là số cách chia m vật (phần thưởng) cho n đối tượng (học sinh). Chiathuong là hàm của hai biến m, n. Trường hợp neo và thuật toán tương ứng Khi m = 0: có duy nhất một cách chia, đó là mọi học sinh đều nhận được 0 phần thưởng. Khi đó, ChiaThuong(0,n) = 1. Khi n = 0, m  0: không có cách nào để thực hiện việc chia. Khi đó, Chiathuong(m,0) = 0, với mọi m  0. 17
Khi n = 1, m  0: có duy nhất một cách chia, đó là m phần thưởng đều chia cho một học sinh. Khi đó, ta có Chiathuong(m,1) = 1. Vậy ta có thể thay trường hợp neo Chiathuong(m,0) = 0 bằng trường hợp Chiathuong(m,1) = 1. Phân rã bài toán trong trường hợp tổng quát Khi m 0). Dễ thấy rằng số cách chia của nhóm này bằng số cách chia m-n phần thưởng cho n học sinh (vì phương thức chia mà tất cả học sinh đều nhận được phần thưởng có thể thực hiện bằng cách cho mỗi người nhận trước một phần thưởng rồi mới chia). Khi đó, số cách chia trong nhóm thứ hai bằng hàm Chiathuong(m-n,n). - Vậy khi m n: Chiathuong(m,n) = Chiathuong(m,n-1) + Chiathuong(m-n,n). Mã hóa thuật toán #include using namespace std; int Chiathuong(int m,int n) { if ((m==0)||(n==1)) return 1; else if (m
return 0; } 1.7.3. Bài toán sắp xếp mảng – Thuật toán sắp xếp nhanh Sắp xếp là một bài toán thường gặp, ngoài ý nghĩa tổ chức lại dữ liệu theo một yêu cầu nào đó, việc sắp xếp còn tạo thuận lợi cho việc tìm kiếm. Có nhiều phương pháp sắp xếp khác nhau, trong đó Quicksort là một phương pháp sắp xếp được nghiên cứu và sử dụng rộng rãi trong lớp các thuật toán sắp xếp. Các đối tượng dữ liệu cần sắp xếp thường có nhiều thuộc tính, về cấu trúc dữ liệu được tổ chức khá đa dạng, và ta cần chọn một khóa để sắp xếp dữ liệu theo khóa này. Ví dụ như mô tả đối tượng con người có các thuộc tính cơ bản như họ tên, ngày sinh, giới tính, v.v.., và thuộc tính họ tên được chọn làm khóa để sắp xếp. Tuy nhiên, để thuận lợi cho việc trình bày cũng như tập trung vào thuật toán ta sẽ làm việc với mảng đơn giản gồm các số nguyên. Đối với các bài toán sắp xếp được xét ở đây chúng ta sẽ quan tâm tới việc sắp xếp mảng các số nguyên theo thứ tự không giảm. Phân tích bài toán Xác định Input, Output: - Input: mảng số nguyên gồm n phần tử - Output: mảng số nguyên được sắp xếp theo thứ tự không giảm. Ý tưởng cơ bản của Quicksort dựa trên phương pháp chia để trị và được mô tả dưới dạng đệ quy. Đầu tiên chọn một phần tử trong mảng làm mốc, sau đó chia mảng thành hai phần ở hai phía của mốc: các phần tử lớn hơn mốc được chuyển sang phải mốc và các phần tử không lớn hơn mốc được chuyển sang trái mốc. Để có được sự phân chia này, các phần tử sẽ được so sánh với mốc và hoán đổi vị trí cho nhau hoặc cho mốc nếu nó lớn hơn mốc mà lại nằm bên trái hoặc không lớn hơn mốc mà lại nằm bên phải. Áp dụng kỹ thuật trên cho hai phần vừa được chia và tiếp tục thực hiện như vậy cho đến khi mỗi mảng con chỉ còn một phần tử. Khi đó toàn bộ mảng đã được sắp xếp không giảm. Giả sử để chia mảng A[d..c] thành hai phần thỏa mãn yêu cầu trên. Ta tiến hành các bước cụ thể như sau: - Lấy một phần tử trong mảng làm mốc. Ở đây ta sẽ chọn phần tử đầu tiên của mảng làm mốc là A[d]. - Tiến hành duyệt mảng A đồng thời từ hai đầu, dùng hai biến i, j để duy trì hai vị trí duyệt. Khởi tạo i = d+1 và j = c. Duyệt từ bên trái mảng và tăng i cho tới khi gặp một phần tử có giá trị lớn hơn mốc (A[i]>A[d]), đồng thời tiến hành 19
duyệt từ bên phải sang và giảm j cho tới khi gặp một phần tử có giá trị nhỏ hơn hoặc bằng mốc (A[j] A[d]). Rõ ràng hai phần tử này nằm ở những vị trí không phù hợp khi đó đổi chỗ A[i] và A[j]. Quá trình này còn tiếp tục khi nào mà i