goupee.vn goupee.com Phần 3: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Chương 10: Giải thuật và thủ tục đệ quy cuu duong than cong . comĐại Học Bách Khoa Hà Nội Khoa Điện Tử - Viễn Thông Bộ môn Điện Tử - Tin Học fb.com/goupee.vn Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin Học Chương 10: Giải Thuật Đệ Quy 1 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Nội dung goupee.com • Khái niệm – Sự đệ quy – Giải thuật đệ quy • Cấu tạo giải thuật đệ quy • Hoạt động của giải thuật đệ quy • Xây dựng thủ tục đệ quy – Thủ tục đệ quy – Phương pháp xây dựng • Cấu trúc thủ tục đệ quy • Hoạt động của thủ tục đệ quycuu duong than cong . com • Nguyên tắc cài đặt – Sự khử đệ quy fb.com/goupee.vn Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin Học Chương 10: Giải Thuật Đệ Quy 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Nội dung goupee.com • Các ví dụ minh họa – Tìm kiếm trong danh sách liên kết – Bài toán Tháp Hà Nội – Bài toán 8 con hậu • Đánh giá thời gian thực hiện giải thuật – Khái niệm – Các ký hiệu – Các quy tắc đánh giá – Phân tích một số giải thuật cuu duong than cong . com fb.com/goupee.vn Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin Học Chương 10: Giải Thuật Đệ Quy 3 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Khái niệm đệ quy goupee.com • Khái niệm về đệ quy (recursion / recursive) Các ví dụ: – String • Quy tắc 1: 1 char = String • Quy tắc 2: String = 1 char + (sub) String – Số tự nhiên • Quy tắc 1: 1 N • Quy tắc 2: x N if (x-1) N – N! • Quy tắc 1: 0! = 1 • Quy tắc 2: n! = n (n-1)! – Định nghĩa danh sách tuyến tính: • Quy tắc 1: L = rỗng là một DSTTcuu duong than cong . com • Quy tắc 2: Nếu Ln-1 là một danh sách kích thước n-1 thì cấu trúc Ln=<a,Ln-1> cũng là một DSTT, với a là một phần tử có cùng kiểu dữ liệu như các phần tử trong Ln-1, và a đứng trước Ln-1 trong danh sách Ln fb.com/goupee.vn Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin Học Chương 10: Giải Thuật Đệ Quy 4 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Khái niệm đệ quy goupee.com • Các khái niệm về đệ quy (recursion / recursive) 1. Khái niệm: (sách "Cấu trúc dữ liệu giải thuật", tác giả Đỗ Xuân Lôi) ta gọi một đối tượng là đệ quy nếu nó bao gồm chính nó như một bộ phận hoặc nó được định nghĩa dưới dạng của chính nó. Đệ quy bao gồm: • Các quy tắc cơ sở (basic rules) • Các quy tắc quy nạp (inductive rules) 2. Khái quát – Khái niệm định nghĩa kiểu đệ quy: là cách định nghĩa về một đối tượng/khái niệm mà dựa vào một hay một tập các đối tượng/khái niệm có cùng bản chất với đối tượng/khái niệm cần định nghĩa nhưng có quy mô nhỏ hơn – Tính chất đệ quy:cuu duong than cong . comcác đối tượng/khái niệm có thể định nghĩa một cách đệ quy thì ta gọi chúng có tính chất đệ quy. Tức là các đối tượng/khái niệm này phải chứa các thành phần có cấu trúc tương tự như chính nó, chỉ khác là quy mô nhỏ hơn. fb.com/goupee.vn Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin Học Chương 10: Giải Thuật Đệ Quy 5 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Khái niệm đệ quy goupee.com • Giải thuật đệ quy (recursive algorithm) – Ví dụ 1: Tìm phần tử trong một tập hợp (tìm từ trong từ điển) ... T11 T111 T112 T T1 T2 T12 T121 T122 ... – Nhận xét ... T21 – Sau mỗi lần tách đôi, ta lại dùng đúng giải thuật đã dùng để áp dụng với các phần nhỏ hơn T22 – Trường hợp đặc biệt khi ta chia nhỏcuu duong than cong . com ... đến 1 trang. Khi đó việc tìm kiếm sẽ trở nên dễ dàng và có thể thực hiện trực tiếp fb.com/goupee.vn Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin Học Chương 10: Giải Thuật Đệ Quy 6 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Khái niệm đệ quy goupee.com • Giải thuật đệ quy (recursive algorithm) – Ví dụ 2: Tính giá trị dãy số Fibonacci • F (1) = 1 với n <= 2; • F (n) = F (n-1) + F (n-2) với n > 1; – Nhận xét: • Thay vì tính F (n) ta quy về tính các giá trị hàm F với biến n nhỏ hơn là F(n-1) và F(n-2). • Cách tính các hàm F(n-1), F(n-2) này cũng giống như cách tính F(n), có nghĩa là cũng quy về việc tính các hàm F với biến n nhỏ hơn nữa • Trường hợp đặc biệt: khi n đủ nhỏ ( n <= 2 ) ta tính được trực tiếp giá trị của hàm F (1) = 1, F (2) = 1 cuu duong than cong . com fb.com/goupee.vn Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin Học Chương 10: Giải Thuật Đệ Quy 7 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Khái niệm đệ quy goupee.com • Giải thuật đệ quy (recursive algorithm) – Khái niệm: • Từ P ta đưa về một bài toán P1 có bản chất tương tự P nhưng có quy mô bé hơn. Nghĩa là tồn tại một quan hệ giữa P và P1, khẳng định nếu giải được P1 thì ta sẽ giải được P. • Tương tự, từ P1 ta lại đưa về giải bài toán P2 có cùng bản chất với P1 và cũng có quy mô nhỏ hơn P1. Quá trình cứ tiếp tục cho đến khi ta đưa bài toán về bài toán con Pn tương tự như Pn-1 và có quy mô nhỏ hơn Pn-1 • Pn có thể giải một cách trực tiếp, tức là không cần đưa về bài toán tương tự có quy mô nhỏ hơn nữa do Pn đã đủ nhỏ và đơn giản. • Sau khi giải được Pn, ta quay lại giải các bài toán con theo trật tự ngược lại và cuối cùng giải được bài toán ban đầu P. suy diễn đệ quy cuu duong than cong . com P P P … P P điểm dừng 1 2 n-1 n quay lui fb.com/goupee.vn Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin Học Chương 10: Giải Thuật Đệ Quy 8 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Khái niệm đệ quy goupee.com • Giải thuật đệ quy (recursive algorithm) – Ví dụ 3: Tìm số nhỏ nhất trong một dãy N số a , a , …, a 1 2 N • 1) Nếu N=1 thì min=a ; 1 • 2) Chia dãy ban đầu thành hai dãy con: L = a , a ,…, am và L = am+1, am+2,…, aN 1 1 2 2 với m=(1+N) DIV 2. Tìm min trong dãy L và min trong dãy L . 1 1 2 2 So sánh min và min để tìm ra min của dãy ban đầu 1 2 – Lưu ý: • Trong trường hợp khái quát hơn, từ bài toán ban đầu ta có thể phải đưa về nhiều bài toán con tương tự. • Trong trường hợp không có trường hợp đặc biệt, giải thuật thường dễcuu duong than cong . com rơi vào vòng lặp vô hạn (không có tính dừng) và bài toán không thể giải được. Ví dụ vòng lặp vô hạn - Ví dụ 4: Tính giá trị dãy số Fibonacci F (n) = F (n-1) + F (n-2) ; fb.com/goupee.vn Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin Học Chương 10: Giải Thuật Đệ Quy 9 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Khái niệm đệ quy goupee.com • Giải thuật đệ quy (recursive algorithm) – Cấu tạo giải thuật đệ quy: gồm hai thành phần sau: • Trường hợp cơ sở: là trường hợp bài toán Pn, có quy mô đủ nhỏ để ta có thể giải trực tiếp. Nó đóng vai trò điểm dừng trong quá trình suy diễn đệ quy, và cũng quyết định tính dừng của giải thuật đệ quy. • Trường hợp đệ quy: là trường hợp khái quát chứa cơ chế đệ quy, là cơ chế đưa bài toán cần giải về một hay nhiều bài toán tương tự nhưng có quy mô nhỏ hơn. Cơ chế này được áp dụng nhiều lần để thu nhỏ quy mô bài toán cần giải, từ bài toán ban đầu cho đến bài toán nhỏ nhất ở trường hợp cơ sở. • Hai trường hợp trên có mối quan hệ khăng khít để tạo thành giải thuật đệ quy và đảm bảo giải thuật đệ quy có thể giải được và có điểm dừng.cuu duong than cong . com fb.com/goupee.vn Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin Học Chương 10: Giải Thuật Đệ Quy 10 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Khái niệm đệ quy goupee.com • Giải thuật đệ quy (recursive algorithm) – Hoạt động của giải thuật bao gồm hai quá trình: • Quá trình suy diễn đệ quy: là quá trình thu nhỏ bài toán ban đầu về các bài toán trung gian tương tự nhưng có quy mô giảm dần bằng cách áp dụng cơ chế đệ quy, cho đến khi gặp trường hợp cơ sở (điểm dừng của quá trình suy diễn đệ quy). • Quá trình quay lui (hay suy diễn ngược): là quá trình từ kết quả thu được trong trường hợp cơ sở, thực hiện giải các bài toán trung gian ở quá trình suy diễn đệ quy theo trật tự ngược lại, cho đến khi giải quyết được bài toán ban đầu. • Ví dụ 5: tính 3! theo giải thuật đệ quy cuu duong than cong . com3! = 3 x 2! Suy diễn 2! = 2 x 1! quay lui đệ quy 1! = 1 x 0! 0! = 1: TH cơ sở fb.com/goupee.vn Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin Học Chương 10: Giải Thuật Đệ Quy 11 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Xây dựng thủ tục đệ quy goupee.com • Thủ tục đệ quy – Khái niệm: để cài đặt các giải thuật đệ quy một cách đơn giản và hiệu quả, đa số các ngôn ngữ lập trình hiện nay đều có cơ chế, công cụ để hỗ trợ công việc này, đó là thủ tục đệ quy. – Thủ tục đệ quy là một chương trình con trực tiếp cài đặt cho giải thuật đệ quy. Tuỳ theo ngôn ngữ lập trình, nó có thể có các tên gọi khác nhau như: trong Pascal ta có thể có thủ tục đệ quy hay hàm con đệ quy, trong C/C++ chỉ có hàm con đệ quy, … cuu duong than cong . com fb.com/goupee.vn Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin Học Chương 10: Giải Thuật Đệ Quy 12 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Xây dựng thủ tục đệ quy goupee.com • Thủ tục đệ quy – Ví dụ 6: Tính giá trị n! int Fact (int n){ • 0! = 1 if (n <= 1) return 1; • n! = n (n-1)! else return n * Fact (n-1); } – Quay lại ví dụ 2: Tính giá trị dãy Fibonacci • F (1) = 1 với n <= 2; • F (n) = F (n-1) + F (n-2) với n > 1; int Fibo1 (int n) { cuu duong than cong . comif (n <= 2) return 1; else return (Fibo1 (n-1) + Fibo1 (n-2)); } fb.com/goupee.vn Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin Học Chương 10: Giải Thuật Đệ Quy 13 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Xây dựng thủ tục đệ quy goupee.com • Thủ tục đệ quy - Phương pháp xây dựng Nhận xét: qua các ví dụ trên ta có thể rút ra các đặc điểm chung cho các thủ tục (hàm) đệ quy như sau: – Trong thủ tục đệ quy có lời gọi đến chính thủ tục đó – Mỗi lần thực hiện gọi lại thủ tục thì kích thước của bài toán (tham số n) lại thu nhỏ hơn trước: bài toán được chia nhỏ – Trường hợp cơ sở - Trường hợp suy biến (degenerate case): các trường hợp mà ta có thể giải quyết bài toán một cách khác, một cách dễ dàng và hiển nhiên (ở 2 ví dụ trên, các hàm được tính một cách dễ dàng) và bài toán kết thúc. – Việc chia nhỏ dần bài toán đảm bảo dẫn tới tính trạng suy biếncuu duong than cong . com nói trên fb.com/goupee.vn Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin Học Chương 10: Giải Thuật Đệ Quy 14 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Xây dựng thủ tục đệ quy goupee.com • Thủ tục đệ quy – Phương pháp xây dựng – Cấu trúc của thủ tục đệ quy: Viết dưới dạng tựa C cấu trúc chung của một thủ tục đệ quy như sau: void P (A) { if A==A then 0 Trường hợp cơ sở else { //Trường hợp đệ quy Q1(); P(A ); //Lời gọi đệ quy 1 Q2(); P(A ); //Lời gọi đệ quy 2 } } cuu duong than cong . com fb.com/goupee.vn Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin Học Chương 10: Giải Thuật Đệ Quy 15 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Xây dựng thủ tục đệ quy goupee.com • Thủ tục đệ quy - Phương pháp xây dựng Nhận xét cấu trúc của thủ tục đệ quy: – Phần đầu thủ tục: thủ tục đệ quy luôn luôn phải có tham số. Ngoài vai trò biểu diễn các thông tin vào/ra như các thủ tục thông thường không đệ quy, tham số của thủ tục đệ quy còn biểu diễn quy mô bài toán cần giải. Tham số này phải có khả năng thu nhỏ khi gọi đệ quy và có quy mô nhỏ nhất khi đến trường hợp cơ sở. – Phần thân thủ tục: bao gồm hai nhánh của một cấu trúc rẽ nhánh tương ứng với hai trường hợp của giải thuật đệ quy: • Trường hợp cơ sở: khi quy mô bài toán suy biến đủ nhỏ, bài toán có thể được giải trực tiếp, nên trong trường hợp này sẽ chứa các lệnh thi hànhcuu duong than cong . com việc giải trực tiếp này. • Trường hợp đệ quy: nó chứa một hay nhiều lời gọi đệ quy, là lời gọi đến chính thủ tục đang xây dựng, nhưng có các tham số khác với (mà thường là nhỏ hơn) tham số ban đầu. fb.com/goupee.vn Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin Học Chương 10: Giải Thuật Đệ Quy 16 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Xây dựng thủ tục đệ quy goupee.com • Thủ tục đệ quy - Phương pháp xây dựng – Thủ tục đệ quy: gọi đến chính nó – Trong một số trường hợp, việc gọi đến chính nó có thể được thực hiện qua hai cách: • Gọi trực tiếp (2 ví dụ trên): ta có Đệ quy trực tiếp (directly recursive) Ví dụ: xem ví dụ 6, ví dụ 2 • Gọi gián tiếp: gọi tới nó thông qua việc ta gọi đến một thủ tục (hàm) khác và tại đó, ta mới gọi đến thủ tục (hàm) đệ quy. Ta có Đệ quy gián tiếp (indirectly recursive) Ví dụ: void RecursiveA () { void ProcedureB (){ ...cuu duong than cong . com... ProcedureB(); RecursiveA(); ... ... } } fb.com/goupee.vn Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin Học Chương 10: Giải Thuật Đệ Quy 17 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Xây dựng thủ tục đệ quy goupee.com • Thủ tục đệ quy - Hoạt động của thủ tục đệ quy Quá trình hoạt động của thủ tục đệ quy gồm hai giai đoạn: – Giai đoạn gọi đệ quy: • Bắt đầu từ lời gọi thủ tục đầu tiên, CT sẽ đi theo nhánh gọi đệ quy trong thân thủ tục để liên tục gọi các lời gọi đệ quy trung gian cho đến khi gặp trường hợp cơ sở. • Khi đến điểm dừng này, hệ thống sẽ tự động kích hoạt giai đoạn thứ hai là giai đoạn quay lui. – Giai đoạn quay lui: • Hệ thống sẽ thi hành các thủ tục đệ quy trung gian trong giai đoạn đầu theo thứ tự ngược lại, cho đến khi thi hành xong thủ tục được gọi đầu tiên thì kết thúc, đồng thời kết thúc hoạt động của thủ tục đệ quy. – Vấn đề cài đặt:cuu duong than cong . comlàm thế nào hệ thống có thể lưu giữ các lời gọi đệ quy trung gian và các kết quả xử lý trung gian trong giai đoạn gọi đệ quy để ta có thể lấy chúng ra để xử lý trong giai đoạn quay lui. fb.com/goupee.vn Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin Học Chương 10: Giải Thuật Đệ Quy 18 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Xây dựng thủ tục đệ quy goupee.com • Thủ tục đệ quy - Nguyên tắc cài đặt thủ tục đệ quy Nhận xét: việc lưu trữ, xử lý các lời gọi đệ quy có đặc điểm sau: – Tính vào sau ra trước (LIFO): • Việc lưu trữ các lời gọi theo đúng thứ tự của quá trình gọi đệ quy, lời gọi trước lưu trữ trước và ngược lại. • Trong quá trình quay lui, các lời gọi được lấy ra theo thứ ngược lại để xử lý. Vậy cần sử dụng cấu trúc ngăn xếp để lưu trữ các lời gọi đệ quy. – Tính đồng nhất: • Do cấu trúc các lời gọi đệ quy và các kết quả trung gian giống nhau, nên cấu trúc ngăn xếp được sử dụng cũng có tính đồng nhất. – Trong thực tế • Các ngôn ngữ lập trình có hỗ trợ cài đặt thủ tục đệ quy đều đã tự độngcuu duong than cong . com cài đặt các cấu trúc ngăn xếp thích hợp để phục vụ cho quá trình cài đặt và hoạt động của thủ tục đệ quy. fb.com/goupee.vn Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin Học Chương 10: Giải Thuật Đệ Quy 19 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Xây dựng thủ tục đệ quy goupee.com • Thủ tục đệ quy - Nguyên tắc cài đặt thủ tục đệ quy – Hoạt động của thủ tục đệ quy trong chương trình (1) Khởi tạo ngăn xếp (2) Giai đoạn gọi đệ quy • Bắt đầu từ lời gọi thủ tục đầu tiên, đi theo nhánh gọi đệ quy trong thân thủ tục để liên tục gọi các lời gọi đệ quy trung gian cho đến khi gặp trường hợp cơ sở. • Song song với quá trình gọi đệ quy, hệ thống sẽ lưu các lời gọi đệ quy và các kết quả trung vào ngăn xếp. • Khi đến điểm dừng, hệ thống sẽ tự động kích hoạt giai đoạn thứ hai là giai đoạn quay lui. (3) Giai đoạn quay lui • Hệ thống lần lượt lấy các lời gọi đệ quy và các kết quả trung giancuu duong than cong . com trong ngăn xếp ra để xử lý cho đến khi hết ngăn xếp. • Khi đó, giai đoạn quay lui kết thúc và đồng thời cũng kết thúc hoạt động của thủ tục đệ quy. Kết quả cuối cùng sẽ là kết quả của thủ tục đệ quy. fb.com/goupee.vn Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin Học Chương 10: Giải Thuật Đệ Quy 20 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Chưa có bình luận nào. Hãy là người đầu tiên!
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!