TAILIEUCHUNG - Chương 5: Đệ qui

Khái niệm (định nghĩa) đệ qui có dùng lại chính nó. Ví dụ: giai thừa của n là 1 nếu n là 0 hoặc là n nhân cho giai thừa của n-1 nếu n 0 Quá trình đệ qui gồm 2 phần: Trường hợp cơ sở (base case) Trường hợp đệ qui: cố gắng tiến về trường hợp cơ sở Ví dụ trên: Giai thừa của n là 1 nếu n là 0 Giai thừa của n là n * (giai thừa của n-1) nếu n0 | CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Chương 5: Đệ qui Khái niệm đệ qui Khái niệm (định nghĩa) đệ qui có dùng lại chính nó. Ví dụ: giai thừa của n là 1 nếu n là 0 hoặc là n nhân cho giai thừa của n-1 nếu n > 0 Quá trình đệ qui gồm 2 phần: Trường hợp cơ sở (base case) Trường hợp đệ qui: cố gắng tiến về trường hợp cơ sở Ví dụ trên: Giai thừa của n là 1 nếu n là 0 Giai thừa của n là n * (giai thừa của n-1) nếu n>0 Chương 5: Đệ qui Tính giai thừa Định nghĩa không đệ qui: n! = n * (n-1) * * 1 Định nghĩa đệ qui: n! = 1 nếu n=0 n * (n-1)! nếu n>0 Mã C++: int factorial(int n) { if (n==0) return 1; else return (n * factorial(n - 1)); } Chương 5: Đệ qui Thi hành hàm tính giai thừa n=2 2*factorial(1) factorial (2) n=1 1*factorial(0) factorial (1) n=0 return 1; factorial (0) 1 1 6 2 n=3 3*factorial(2) factorial (3) Chương 5: Đệ qui Trạng thái hệ thống khi thi hành hàm tính giai thừa factorial(3) factorial(3) factorial(2) factorial(3) factorial(2) factorial(1) factorial(3) factorial(2) factorial(1) factorial(0) factorial(3) factorial(2) factorial(1) factorial(3) factorial(2) factorial(3) t Gọi hàm factorial(3) Gọi hàm factorial(2) Gọi hàm factorial(1) Gọi hàm factorial(0) Trả về từ hàm factorial(0) Trả về từ hàm factorial(1) Trả về từ hàm factorial(2) Trả về từ hàm factorial(3) Stack hệ thống Thời gian hệ thống t Chương 5: Đệ qui Bài toán Tháp Hà nội Luật: Di chuyển mỗi lần một đĩa Không được đặt đĩa lớn lên trên đĩa nhỏ Chương 5: Đệ qui Bài toán Tháp Hà nội – Thiết kế hàm Hàm đệ qui: Chuyển (count-1) đĩa trên đỉnh của cột start sang cột temp Chuyển 1 đĩa (cuối cùng) của cột start sang cột finish Chuyển count-1 đĩa từ cột temp sang cột finish magic Chương 5: Đệ qui Bài toán Tháp Hà nội – Mã C++ void move(int count, int start, int finish, int temp) { if (count > 0) { move(count − 1, start, temp, finish); cout Chương 5: Đệ qui

• Cơ sở dữ liệu
• cây nhị phân tìm kiếm
• ưu điểm cây nhị phân
• định hướng tìm kiếm
• cấu trúc dữ liệu
• tạo cây rỗng
• gán trường dữ liệu
• cây đa phân
• bảng
• sắp xếp thứ tự
• tìm kiếm
• danh sách chuỗi
• đệ quy
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu và giải thuật
• Sử dụng cây nhị phân tìm kiếm
• Thao tác trên cây nhị phân tìm kiếm
• Cách biểu diễn cây
• duyệt cây nhị phân
• hiện thực liên kết cuả cây nhị phân
• đặc tả cây nhị phân
• tìm kiếm trên cây
• Bài giảng Cấu trúc dữ liệu
• Thành phần của cây nhị phân
• Cấu trúc cây
• Bài giảng Trees
• Cấu trúc dữ liệu cây nhị phân
• Cấu trúc dữ liệu nhị phân tìm kiếm
• Tổ chức dữ liệu nhị phân tìm kiếm
• Thuật toán dữ liệu nhị phân tìm kiếm
• Cây nhị phân
• Nhị phân tìm kiếm
• lập trình cơ bản
• tổng quan lập trình
• lập trình đối tượng
• Cây tìm kiếm nhị phân cân bằng
• Cây tìm kiếm nhị phân
• AVL tree
• Cây splay
• Cây 2‐3
• Bài giảng Giải thuật
• Tìm kiếm tuần tự
• Tìm kiếm nhị phân
• Cây nhị phân tìm kiếm cân bằng
• Tìm kiếm trên cây nhị phân
• Cơ sở dữ liệu
• Cài đặt cây nhị phân tìm kiếm
• Tìm phần tử nhỏ nhất
• Giải thuật tìm kiếm
• Bài toán tìm kiếm
• Cây quyết định
• Đánh giá thuật toán
• Thiết kế thuật toán
• Bài giảng đánh giá thuật toán
• Bài giảng thiết kế thuật toán
• Cây tìm kiếm nhị phân
• Cấu trúc cây nhị phân
• Cấu trúc cây nhị phân tìm kiếm
• Cấu trúc giải thuật
• Thành phần dữ liệu
• Khai báo cài đặt cây nhị phân
• Hàm xác định số nút của cây
• Hàm kiểm tra rỗng
• Cấu trúc dữ liệu rời rạc
• Biểu diễn cây nhị phân
• Thuật toán tìm kiếm trên đồ thị
• Mất cân bằng cây nhị phân
• Cấu trúc dữ liệu và thuật toán
• Khoa học máy tính