tailieunhanh - Bài giảng Chương 2: Giải thuật đệ quy

Bài giảng "Chương 2: Giải thuật đệ quy" cung cấp cho người đọc các kiến thức về: 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. nội dung chi tiết. | 27 02 12 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 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 1 là số tự nhiên. 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 Nếu n 0 thì n n n-1 3 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 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 Ví dụ 1 Hàm n Í1 nếu n 0 Factorial n In Factorial n- 1 nếu n 0 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 else return n Factorial n-1 6 1 27 02 12 Ví dụ 2 Bài toán dãy số FIBONACI F n Với n 0 1 nếu n 2 F n - 2 F n - 1 nếu n 2 int Fibonaci intn if n 2 return 1 else return Fibonaci n-2 Fibonaci n-I Đặ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 Phương pháp thiết kế giải thuật đệ quy Cần trả lời 3 câu hỏi Bài toán được định nghĩa đệ quy như thế nào Kich thước của bài toán giảm ra sao sau mỗi lần gọi đệ quy Trường hợp nào là trường

• Cơ sở dữ liệu
• Giải thuật đệ quy
• Bài giảng Giải thuật đệ quy
• Thiết kế giải thuật đệ quy
• Hiệu lực của đệ quy
• Thiết kế giải thuật
• Khái niệm đệ quy
• tác vụ hướng đệ quy
• cách hiện thực hàm đệ quy
• Phân loại các loại đệ quy
• cách chạy một hàm đệ quy
• Cơ cấu ngăn xếp
• cậy biểu diễn cá lần gọi hàm
• cachs hiện thực đệ quy
• đệ quy đôi
• so sánh đệ quy và không đệ quy
• Phân tích thuật giải
• Thiết kế thuật giải
• Đệ quy tuyến tính
• Đệ quy nhị phân
• Luận văn tốt nghiệp
• Cấu trúc dữ liệu và giải thuật
• Mô phỏng thuật toán đệ quy
• Bài tập về đệ quy
• Giải thuật đệ qui
• Đệ qui quay lui
• cấu trúc dữ liệu
• giải thuật
• danh sách
• đệ quy
• dữ liệu máy tính
• quản lý dữ liệu
• Bài giảng Kỹ thuật lập trình
• Kỹ thuật lập trình
• Kỹ thuật đệ quy
• Phân loại các dạng đệ qui
• Giải pháp đệ qui
• Giải pháp thay thế cho đệ qui
• Kỹ thuật lập trình đệ quy
• Lập trình đệ quy
• Xây dựng giải thuật đệ quy
• Giải thuật đệ quy tiêu biểu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Bài giảng Đệ quy
• Khái niệm về đệ quỵ
• Đệ quy đuôi
• Phân loại các dạng đệ quy
• Giải pháp thay thế cho đệ quy
• Thuật toán đệ quy
• Phân tích thuật toán đệ quy
• Đệ quy có nhớ
• Thuật toán quay lui
• Backtracking algorithm
• Bài giảng Cấu trúc dữ liệu
• Cơ sở dữ liệu
• Đệ quy có thể không kết thúc
• tài liệu về đệ quy
• Recursion
• thủ thuật lập trình
• Phân loại đệ quy
• Hệ cơ sở dữ liệu
• Quản trị cơ sở dữ liệu
• Thông tin cấu trúc
• Bài giảng Ngôn ngữ lập trình
• Ngôn ngữ lập trình
• Hàm đệ quy tính số Fibonaci
• Tường hợp suy biến
• Chương trình đệ quy
• Giải thuật đệ qui quay lui
• Quy nạp toán học
• Phương pháp khử đệ quy
• Ứng dụng giải thuật đệ quy
• Bài giảng giải thuật
• Lý thuyết cấu trúc dữ liệu
• Khử đệ quy
• Khử đệ quy cho bài toán QuickSort
• Bài toán tháp Hanoi
• Đệ quy hỗ tương
• Bài tập đệ quy
• Ước số chung nhỏ nhất
• Tính giai thừa đệ qui
• Cây đệ qui chữ H
• Giải pháp đệ quy
• Lập trình C++
• Hàm đệ quy