›
›

Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 2: Các sơ đồ thuật toán - Nguyễn Khánh Phương

Download
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: [email protected].vn  
Nội dung khóa học  
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
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: [email protected].vn  
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
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
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  
– ...  
Ví dụ Đệ qui: Điểm quân  
Ví dụ Đệ qui: Điểm quân  
Ví dụ Đệ qui: Điểm quân  
Ví dụ Đệ qui: Điểm quân  
Ví dụ Đệ qui: Điểm quân  
Ví dụ Đệ qui: Điểm quân  
Ví dụ Đệ qui: Điểm quân  
Ví dụ Đệ qui: Điểm quân  
Ví dụ Đệ qui: Điểm quân  
Ví dụ Đệ qui: Điểm quân  
Ví dụ Đệ qui: Điểm quân  
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).  
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:  
đệ qui  
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)  
điều kiện đầu  
return 1;  
else  
return n*factorial(n-1);  
}
Tải về để xem bản đầy đủ
pdf 131 trang yennguyen 13440 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 2: Các sơ đồ thuật toán - Nguyễn Khánh Phương", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_giang_cau_truc_du_lieu_va_thuat_toan_chuong_2_cac_so_do.pdf