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