Chương 2: Giải thuật đệ quy

Chia sẻ: Kieu Quang Vinh | Ngày: | Loại File: PPT | Số trang:27

Thêm vào BST

Báo xấu

297
lượt xem 85
download

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

Một đối tượng được gọi là đệ quy nếu nó bao gồm chính nó như một bộ phận hoặc được định nghĩa bởi chính nó.

Chủ đề:

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

Lưu

Nội dung Text: Chương 2: Giải thuật đệ quy

Chương 2 GIẢI THUẬT ĐỆ QUY
NỘI DUNG Khái niệm đệ quy  Giải thuật đệ quy  Thiết kế giải thuật đệ quy  Hiệu lực của đệ quy  2/27
2.1 KHÁI NIỆM ĐỆ QUY Một đối tượng được gọi là đệ quy nếu nó bao gồm  chính nó như một bộ phận hoặc được định nghĩa bởi chính nó. Ví dụ : Số tự nhiên  là số tự nhiên. +1 + n là số tự nhiên nếu n-1 là số tự nhiên. Giai thừa của số n (n!) + 0! = 1 3/27 + Nếu n>0 thì n! = n*(n-1)!
2.2 GIẢI THUẬT ĐỆ QUY Nếu lời giải của của một bài toán T được giải bằng lời  giải của một bài toán T1, có dạng giống như T thì lời giải đó được gọi là lời giải đệ quy. Giải thuật tương ứng với lời giải đệ quy gọi là giải thuật đệ quy. Ở đây T1 có dạng giống T nhưng theo một nghĩa nào  đó T1 phải “nhỏ” hơn T. Chẳng hạn với bài toán tính n!, thì tính n! là bài toán T  còn tính (n -1)! là bài toán T1 ta thấy T1 cùng dạng với T nhưng nhỏ hơn (n -1 < n). 4/27
2.3 THIẾT KẾ GIẢI THUẬT ĐỆ QUY Khi bài toán đang xét hoặc dữ liệu đang xử lý được định  nghĩa dưới dạng đệ quy thì việc thiết kế các giải thu ật đệ quy tỏ ra rất thuận lợi. Hầu như nó phản ánh rất sát nội dung của định nghĩa đó Không có giải thuật đệ quy vạn năng cho tất cả các bài  toán đệ quy, nghĩa là mỗi bài toán cần thiết kế m ột gi ải thuật đệ quy cho phù hợp 5/27
Ví dụ 1 Hàm n!  nÕu = 0 1 n Factorial (n) =  n * Factorial( - 1) nÕu > 0 n n Giải thuật đệ quy được viết dưới dạng hàm như sau  int Factorial (int n) { if (n==0) return 1; return n*Factorial(n-1); } 6/27
Ví dụ 2 Bài toán dãy số FIBONACI  nÕu ≤ 2 1 n F ( n) =  F(n - 2) + F(n - 1) nÕu > 2 n (Với n>0) int Fibonaci (int n) { if (n
Đặc điểm của giải thuật đệ quy Trong hàm đệ quy có lời gọi đến chính hàm đó  Sau mỗi lần có lời gọi đệ quy thì kích thước của bài  toán được thu nhỏ hơn trước. Có it nhất một trường hợp suy biến xảy ra. Khi đó bài  toán sẽ được giải quyết theo một cách khác, việc gọi đệ quy kết thúc. 8/27
Ví dụ 3 Bài toán Tháp Hà Nội  Có n đĩa, kích thước khác nhau, được xếp chồng lên nhau trên cột A, đĩa to ở dưới, đĩa nhỏ ở trên. Yêu cầu : Chuyển n đĩa từ cột A sang cột B sử dụng cột C là  cột trung gian. Mỗi lần chỉ được chuyển một đĩa  Không được chồng đĩa to lên trên đĩa nhỏ  9/27
Ví dụ 3 n đĩa A B C Chồng đĩa trước khi chuyển 10/27
Ví dụ 3 Xét các trường hợp đơn giản sau Trường hợp có 1 đĩa:  Chuyển đĩa từ cọc A sang cọc B.  Trường hợp có 2 đĩa:  Chuyển đĩa thứ nhất từ cọc A sang cọc C  Chuyển đĩa thứ hai từ cọc A sang cọc B  Chuyển đĩa thứ nhất từ cọc C sang cọc B  11/27
Ví dụ 3 Trường hợp có 3 đĩa  A B C Chồng đĩa trước khi chuyển 12/27
Ví dụ 3 Bước 1 A B C Chuyển 1 đĩa từ A sang B 13/27
Ví dụ 3 Bước 2 A B C Chuyển 1 đĩa từ A sang C 14/27
Ví dụ 3 Bước 3 A B C Chuyển 1 đĩa từ B sang C 15/27
Ví dụ 3 Bước 4 A B C Chuyển 1 đĩa từ A sang B 16/27
Ví dụ 3 Bước 5 A B C Chuyển 1 đĩa từ C sang A 17/27
Ví dụ 3 Bước 6 A B C Chuyển 1 đĩa từ C sang B 18/27
Ví dụ 3 Bước 7 A B C Chuyển 1 đĩa từ A sang B 19/27
Ví dụ 3 A B C Chồng đĩa sau khi chuyển 20/27