lOMoAR cPSD| 27879799
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
Cấu trúc dữ liệu và thuật toán Nguyễn Khánh Phương Computer Science department
School of Information and Communication technology
E-mail: phuongnk@soict.hust.edu.vn Nội dung khóa học lOMoAR cPSD| 27879799
Chương 1. Các khái niệm cơ bản
Chương 2. Các sơ đồ thuật toán
Chương 3. Các cấu trúc dữ liệu cơ bản Chương 4. Cây Chương 5. Sắp xếp Chương 6. Tìm kiếm Chương 7. Đồ thị 2 lOMoAR cPSD| 27879799
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Chương 2. Các sơ ồ thuật toán Nguyễn Khánh Phương Computer Science department
School of Information and Communication technology
E-mail: phuongnk@soict.hust.edu.vn lOMoAR cPSD| 27879799 N i dung 1. Khái niệm ệ qui 2. Thuật toán ệ qui
3. Một số ví dụ minh hoạ
4. Phân tích thuật toán ệ qui 5. Đệ qui có nhớ 6. Thuật toán quay lui 4 lOMoAR cPSD| 27879799 N i dung 1. Khái niệm ệ qui 2. Thuật toán ệ qui
3. Một số ví dụ minh hoạ
4. Phân tích thuật toán ệ qui 5. Đệ qui có nhớ 6. Thuật toán quay lui 5 lOMoAR cPSD| 27879799 1. Khái niệm ệ qui
• Trong thực tế ta thường gặp những ối tượng bao gồm chính nó hoặc
được định nghĩa dưới dạng của chính nó. Ta nói các đối tượng đó
ược xác ịnh một cách ệ qui. • Ví dụ: – Điểm quân số – Fractal
– Các hàm ược ịnh nghĩa ệ qui – Tập hợp ược ịnh nghĩa ệ qui
– Định nghĩa ệ qui của cây – ... lOMoAR cPSD| 27879799
Ví dụ Đệ qui: Điểm quân lOMoAR cPSD| 27879799
Ví dụ Đệ qui: Điểm quân lOMoAR cPSD| 27879799
Ví dụ Đệ qui: Điểm quân lOMoAR cPSD| 27879799
Ví dụ Đệ qui: Điểm quân lOMoAR cPSD| 27879799
Ví dụ Đệ qui: Điểm quân lOMoAR cPSD| 27879799
Ví dụ Đệ qui: Điểm quân lOMoAR cPSD| 27879799
Ví dụ Đệ qui: Điểm quân lOMoAR cPSD| 27879799
Ví dụ Đệ qui: Điểm quân lOMoAR cPSD| 27879799
Ví dụ Đệ qui: Điểm quân lOMoAR cPSD| 27879799
Ví dụ Đệ qui: Điểm quân lOMoAR cPSD| 27879799
Ví dụ Đệ qui: Điểm quân lOMoAR cPSD| 27879799 Ví dụ Đệ qui: Fractals
fractals là ví dụ về hình ảnh ược xây dựng một cách ệ qui ( ối tượng lặp lại một cách ệ qui). Hàm ệ qui (Recursive Functions)
Các hàm ệ qui ược xác ịnh phụ thuộc vào biến nguyên không âm n theo sơ ồ sau:
Bước cơ sở (Basic Step): Xác
ịnh giá trị của hàm tại n=0: f(0). lOMoAR cPSD| 27879799
Bước ệ qui (Recursive Step): Cho giá trị của f(k), k ≤ n, ưa ra qui tắc tính giá trị của f(n+1). Ví dụ 1: f(0) = 3, n = 0 f(n+1) = 2f(n) + 3, n > 0
Khi ó ta có: f(1) = 2 × 3 + 3 = 9, f(2) = 2 × 9 + 3 = 21, ...
Hàm ệ qui (Recursive Functions)
Ví dụ 2: Định nghĩa ệ qui của n! f(0) = 1 f(n) = n * f(n-1)
Để tính giá trị của hàm ệ qui ta thay thế dần theo ịnh nghĩa ệ qui ể thu ược biểu thức
với ối số càng ngày càng nhỏ cho ến tận iều kiện ầu. Chẳng hạn: lOMoAR cPSD| 27879799
5! = 5 · 4! = 5 · 4 · 3! = 5 · 4 · 3 · 2! = 5 · 4 · 3 · 2 · 1!
= 5 · 4 · 3 · 2 · 1 · 0! = 5 · 4 · 3 · 2 · 1 · 1 = 120 int factorial(int n){ if (n==0) return 1;
else return n*factorial(n-1); } factorial(4); factorial(4) int factorial(int n){ if (n==0) return 1;
else return n*factorial(n-1); }