1. Trang Chủ
  2. Cơ sở dữ liệu
  3. 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

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

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. 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

Thể loại Tài liệu miễn phí Cơ sở dữ liệu

Số trang 131

Ngày tạo 10/10/2021 7:17:27 PM +00:00

Loại tệp PDF

Kích thước 4.19 M

Tên tệp

Tải Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 2... (.pdf)

Xem mẫu

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. Ví dụ Đệ qui: Điểm quân om .c ng co an th o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
  8. Ví dụ Đệ qui: Điểm quân om .c ng co an th o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
  9. Ví dụ Đệ qui: Điểm quân om .c ng co an th o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
  10. Ví dụ Đệ qui: Điểm quân om .c ng co an th o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
  11. Ví dụ Đệ qui: Điểm quân om .c ng co an th o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
  12. Ví dụ Đệ qui: Điểm quân om .c ng co an th o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
  13. Ví dụ Đệ qui: Điểm quân om .c ng co an th o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
  14. Ví dụ Đệ qui: Điểm quân om .c ng co an th o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
  15. Ví dụ Đệ qui: Điểm quân om .c ng co an th o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
  16. Ví dụ Đệ qui: Điểm quân om .c ng co an th o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
  17. Ví dụ Đệ qui: Điểm quân om .c ng co an th o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
  18. 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
  19. 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
  20. 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
nguon tai.lieu . vn
Tin học văn phòng Đồ họa - Thiết kế - Flash Quản trị Web Cơ sở dữ liệu Quản trị mạng Kỹ thuật lập trình Hệ điều hành Phần cứng An ninh - Bảo mật Chứng chỉ quốc tế Thủ thuật máy tính Điện - Điện tử Kinh tế học Hoá học Xã hội học Môi trường