intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Kỹ thuật lập trình: Chương 6 - Trường Đại học Ngoại ngữ - Tin học TP.HCM

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:37

Thêm vào BST
Báo xấu
12
lượt xem 5
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Kỹ thuật lập trình: Chương 6 Kỹ thuật đệ quy, cung cấp cho người đọc những kiến thức như: Khái niệm Đệ quy; Kỹ thuật cài đặt Hàm đệ quy; Cơ chế hoạt động của Hàm đệ quy. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Kỹ thuật lập trình: Chương 6 - Trường Đại học Ngoại ngữ - Tin học TP.HCM

  1. KỸ THUẬT ĐỆ QUY (RECURSION) Khoa Công nghệ thông tin Trường Đại học Ngoại ngữ - Tin học TP.HCM (HUFLIT)
  2. Nội dung • Khái niệm Đệ quy • Kỹ thuật cài đặt Hàm đệ quy • Cơ chế hoạt động của Hàm đệ quy • Bài tập vận dụng 2
  3. KHÁI NIỆM ĐỆ QUY
  4. Khái niệm Đệ quy • Một hàm toán học có thể được định nghĩa: • Thông qua công thức toán học tường minh • Thông qua chính hàm đang muốn định nghĩa (định nghĩa theo cách đệ quy) • Ví dụ 1: Định nghĩa hàm n! (n giai thừa) 1 𝑛ế𝑢 𝑛 = 0 𝒏! = ቈ 1 𝑛ế𝑢 𝑛 = 0 𝒏! = ቈ 1 ∗ 2 ∗ ⋯∗ 𝑛 𝑛ế𝑢 𝑛 > 0 𝑛 ∗ 𝒏− 𝟏 ! 𝑛ế𝑢 𝑛 > 0 4
  5. Khái niệm Đệ quy • Ví dụ 2: Hãy tính f(1), f(2), f(3) với 1 𝑛ế𝑢 𝑛 = 0 𝑓 𝑛 =൦ 1 𝑓 𝑛−1 + 𝑛ế𝑢 𝑛 > 0 𝑓(𝑛 − 1) • Ví dụ 3: Hãy tính f(3), f(4), f(5), f(6) với 1 𝑛ế𝑢 𝑛 = 1 ℎ𝑎𝑦 𝑛 = 2 𝑓 𝑛 =ቈ 𝑓 𝑛 − 1 + 𝑓(𝑛 − 2) 𝑛ế𝑢 𝑛 > 2 5
  6. Khái niệm Đệ quy • Một đối tượng được gọi là đệ quy nếu nó được định nghĩa thông qua chính nó hoặc một đối tượng khác cùng dạng với nó bằng quy nạp. • Bài toán đệ quy là bài toán có thể được phân rã thành các bài toán nhỏ hơn nhưng mang cùng tính chất với bài toán ban đầu, các bài toán nhỏ lại được phân rã thành các bài toán nhỏ hơn nữa. Cứ tiếp tục như thế cho đến khi không thể chia nhỏ được hoặc đạt được kết quả mong muốn. 6
  7. Khái niệm Đệ quy • Các thành phần của một hàm đệ quy: • Thành phần không đệ quy (phần neo) • Điều kiện thoát khỏi đệ quy, gọi là trường hợp suy biến. • Chứa quy tắc, công thức để tính ngay giá trị của hàm số. • Thành phần đệ quy (công thức đệ quy) • Thân hàm có chứa lời gọi đệ quy. Điều Thành phần không đệ quy kiện dừng 1 𝑛ế𝑢 𝑛 = 1 ℎ𝑎𝑦 𝑛 = 2 𝑓 𝑛 =ቈ 𝑓 𝑛 − 1 + 𝑓(𝑛 − 2) 𝑛ế𝑢 𝑛 > 2 Điều Thành phần đệ quy kiện đệ quy 7
  8. Khái niệm Đệ quy • Nhận xét: Khi thực hiện tính toán hàm đệ quy: • Thường chúng ta xuất phát từ Thành phần đệ quy • Quá trình tính toán sẽ lặp đi lặp lại theo công thức đệ quy và quá trình tính toán này phải tiến về Thành phần không đệ quy 8
  9. Khái niệm Đệ quy • Ví dụ: Mô tả hàm đệ quy tính USCLN(A, B). Minh họa quá trình thực hiện với: 1) A = 126 và B = 72 2) A= 72 và B = 126 𝐴 𝑛ế𝑢 𝐵 = 0 USCLN(A, B) = ቈ 𝑈𝑆𝐶𝐿𝑁(𝐵, 𝐴 𝑚𝑜𝑑 𝐵) 𝑛ế𝑢 𝐵 ≠ 0 9
  10. Khái niệm Đệ quy 𝐴 𝑛ế𝑢 𝐵 = 0 USCLN(A, B) = ቈ 𝑈𝑆𝐶𝐿𝑁(𝐵, 𝐴 𝑚𝑜𝑑 𝐵) 𝑛ế𝑢 𝐵 ≠ 0 • Minh họa 1: USCLN(126, 72) = USCLN(72, 54) //B = 72 ≠ 0 = USCLN(54, 18) //B = 54 ≠ 0 = USCLN(18, 0) //B = 18 ≠ 0 = 18 //B = 0 • Minh họa 2: USCLN(72, 126) = USCLN(126, 72) //B = 126 ≠ 0 = USCLN(72, 54) //B = 72 ≠ 0 = USCLN(54, 18) //B = 54 ≠ 0 = USCLN(18, 0) //B = 18 ≠ 0 = 18 //B = 0 10
  11. KỸ THUẬT CÀI ĐẶT HÀM ĐỆ QUY
  12. Thiết kế thuật giải đệ quy • 3 bước thiết kế thuật giải đệ quy: • Tham số hóa bài toán. • Phân tích trường hợp chung: đưa bài toán về bài toán nhỏ hơn cùng loại, dần dần tiến tới trường hợp suy biến. • Tìm trường hợp suy biến. 12
  13. Một số dạng đệ quy • Đệ quy tuyến tính (Linear Recursion): mỗi lần thực thi chỉ gọi đệ quy một lần. • Ví dụ: Bài toán tính giai thừa, Dãy Fibonaci. int Factorial(int n) { if (n == 0) { return 1; } else { // Linear Recursion return n * Factorial(n - 1); } } 13
  14. Một số dạng đệ quy • Đệ quy nhị phân (Binary Recursion): mỗi lần thực thi có thể gọi đệ quy 2 lần. • Ví dụ: Bài toán tháp Hà Nội, Tính tổ hợp chập K của N. int Combine(int n, int k) { if (k == 0 || k == n) { return 1; } else { // Binary Recursion return (Combine(n - 1, k) + Combine(n - 1, k - 1)); } } 14
  15. Một số dạng đệ quy • Đệ quy lồng (Nested Recursion): tham số trong lời gọi đệ quy là một lời gọi đệ quy. Đệ quy lồng chiếm bộ nhớ rất nhanh. • Ví dụ: Hàm số Ackermann. int Ackerman(int m, int n) { if (m == 0) return (n + 1); else if (n == 0) return Ackerman(m - 1, 1); else // Nested Recursion return Ackerman(m - 1, Ackerman(m, n - 1)); } 15
  16. Một số dạng đệ quy • Đệ quy hỗ tương (Mutual Recursion): các hàm gọi đệ quy lẫn nhau. • Ví dụ: Xét tính chẵn lẻ của một số nguyên dương bằng đệ quy. bool isEven(unsigned int n) { if (n == 0) return true; else return isOdd(n - 1); } bool isOdd(unsigned int n) { if (n == 1) return true; else return isEven(n - 1); } 16
  17. Một số dạng đệ quy • Quay lui (Backtracking): phương pháp Thử và Sai (Try and Error). • Ví dụ: Bài toán N-quân Hậu, Trò chơi Soduku 17
  18. Kỹ thuật cài đặt hàm đệ quy • Hàm đệ quy (trong lập trình): • Một hàm A (trong lập trình) được gọi là Hàm Đệ quy nếu trong định nghĩa hàm A có lời gọi đến chính hàm A. TenHamA(tham So) { … TenHamA(tham So); … } 18
  19. Kỹ thuật cài đặt hàm đệ quy • Khi cài đặt công thức toán đệ quy: Chúng ta cần biểu diễn đầy đủ: • Điều kiện không đệ quy và công thức phần không đệ quy • Điều kiện đệ quy và công thức phần đệ quy 19
  20. Kỹ thuật cài đặt hàm đệ quy • Sơ đồ cài đặt 1: KieuTraVe TenHam(Kieu n) { if (điều kiện dừng) [return] công thức không đệ quy; else [return] TenHam(n-1) …; } Công thức đệ quy 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2