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: Đệ quy - Nguyễn Minh Huy

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

Thêm vào BST
Báo xấu
8
lượt xem 3
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: Đệ quy, được biên soạn gồm các nội dung chính sau Tổng quan về đệ quy; Phân loại đệ quy; Các vấn đề đệ quy thông dụng. 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: Đệ quy - Nguyễn Minh Huy

  1. Đệ quy GV. Nguyễn Minh Huy Kỹ thuật lập trình - Nguyễn Minh Huy 1
  2. Nội dung Tổng quan về đệ quy. quy. Phân loại đệ quy. quy. Các vấn đề đệ quy thông dụng. dụng. Kỹ thuật lập trình - Nguyễn Minh Huy 2
  3. Nội dung Tổng quan về đệ quy. quy. Phân loại đệ quy. quy. Các vấn đề đệ quy thông dụng. dụng. Kỹ thuật lập trình - Nguyễn Minh Huy 3
  4. Tổng quan về đệ quy Khái niệm đệ quy: quy: Đệ quy là gì? gì? Xem phần…”Đệ quy là gì?”!! phần…”Đệ gì?”!! Đệ quy là… là… Định nghĩa một vấn đề bằng chính vấn đề đó!! đó!! Một vài định nghĩa đệ quy: quy: n! = n * (n – 1)!. f(n) = f(n – 1) + f(n – 2). n là số tự nhiên nếu n – 1 cũng là số tự nhiên N. Tổ tiên của A là những người sinh ra…tổ tiên của A. ra… Kỹ thuật lập trình - Nguyễn Minh Huy 4
  5. Tổng quan về đệ quy Khái niệm đệ quy: quy: Cấu trúc một định nghĩa đệ quy: quy: Phần dừng: trường hợp cơ bản. dừng: bản. Phần đệ quy: suy biến vấn đề về trường hợp đơn giản hơn. quy: hơn. - 0! = 1 - n! = n * (n – 1)!. - f(0) = 0 - f(1) = 1 - f(n) = f(n – 1) + f(n – 2). - 0 là số tự nhiên nhỏ nhất. nhất. - n là số tự nhiên nếu n – 1 là số tự nhiên. nhiên. - Người trực tiếp sinh ra A là tổ tiên của A. - Người sinh ra tổ tiên của A là tổ tiên của A. Kỹ thuật lập trình - Nguyễn Minh Huy 5
  6. Tổng quan về đệ quy Đệ quy trong lập trình: trình: Hàm đệ quy: quy: Thân hàm có lời gọi hàm lại chính nó. nó. Lời gọi hàm trức tiếp hay gián tiếp. tiếp. // Đệ quy trực tiếp. tiếp. // Đệ quy gián tiếp. tiếp. void func() func() void func1() func1() { { // … // … func(); func(); func2(); // … // … } } void func2() func2() { // … func1(); // … } Kỹ thuật lập trình - Nguyễn Minh Huy 6
  7. Tổng quan về đệ quy Đệ quy trong lập trình: trình: Cấu trúc hàm đệ quy: quy: ( [Danh sách tham số] ) về> hàm> [Danh số] { if () () // Xử lý trường hợp cơ bản. bản. else // Gọi lại hàm đệ quy. quy. } int tinhGT(int n) tinhGT( int fibo(int n) fibo( { { if (n == 0) (n 0) if (n == 0) (n 0) return 1; return 0; return n * tinhGT(n – 1); tinhGT(n 1); if (n == 1) (n 1) } return 1; return fibo(n – 1) + fibo(n – 2); fibo(n fibo(n 2); } Kỹ thuật lập trình - Nguyễn Minh Huy 7
  8. Tổng quan về đệ quy Đệ quy trong lập trình: trình: Kiểu dữ liệu đệ quy: quy: struct trúc> { // … ; trúc> // … }; struct Person struct NhanVien { { char *name; char *hoten; *hoten; int age; char *diachi; diachi; Person *father; double luong; luong; Person *mother; NhanVien *nguoiquanly; nguoiquanly; }; }; Kỹ thuật lập trình - Nguyễn Minh Huy 8
  9. Tổng quan về đệ quy Đệ quy trong cuộc sống: sống: Thực phẩm Búp bê Nga Quảng cáo Thực vật Đồ họafractal Kỹ thuật lập trình - Nguyễn Minh Huy 9
  10. Nội dung Tổng quan về đệ quy. quy. Phân loại đệ quy. quy. Các vấn đề đệ quy thông dụng. dụng. Kỹ thuật lập trình - Nguyễn Minh Huy 10
  11. Phân loại đệ quy Các loại đệ quy: quy: Đệ quy tuyến tính: tính: Thân hàm có duy nhất một lời gọi đệ quy. quy. int tinhGT(int n) tinhGT( { tinhGT(n) if (n == 0) (n 0) return 1; tinhGT(n-1) return n * tinhGT(n – 1); tinhGT(n 1); } tinhGT(n-2) Độ phức tạp: tuyến tính O(n). tạp: … Đệ quy đuôi: đuôi: Một dạng của đệ quy tuyến tính. tính. Lời gọi đệ quy là duy nhất và là lệnh cuối cùng. cùng. Ít tốn bộ nhớ (không lưu các trường hợp trước đó). đó). Kỹ thuật lập trình - Nguyễn Minh Huy 11
  12. Phân loại đệ quy Các loại đệ quy: quy: Đệ quy nhị phân: phân: Thân hàm có 2 lời gọi đệ quy. quy. int fibo(int n) fibo( { if (n == 0) (n 0) return 0; if (n == 1) (n 1) return 1; return fibo(n – 1) + fibo(n – 1); fibo(n fibo(n 1); } fibo(n) Độ phức tạp: O(2n). tạp: fibo(n-1) fibo(n-2) fibo(n-2) fibo(n-3) fibo(n-3) fibo(n-4) … … … … Kỹ thuật lập trình - Nguyễn Minh Huy 12
  13. Phân loại đệ quy Các loại đệ quy: quy: Đệ quy hỗ tương: tương: Hàm f1 có lời gọi đến hàm f2. Hàm f2 có lời gọi đến hàm f1. bool soChan(int n) soChan( bool soLe(int n) soLe( { { if (n == 0) (n 0) if (n == 0) (n 0) return true; return false; return soLe(n – 1); soLe(n 1); return soChan(n – 1); soChan(n 1); } } Độ phức tạp: tùy thuộc độ phức tạp từng hàm đệ quy. tạp: quy. Kỹ thuật lập trình - Nguyễn Minh Huy 13
  14. Phân loại đệ quy Các loại đệ quy: quy: Đệ quy phi tuyến: tuyến: Thân hàm có lời gọi đệ quy đặt trong vòng lặp. lặp. Tính: Tính: S(1) = 1 S(n) = S(1) + S(2) + … + S(n – 1). int tinh(int n) tinh( S(n) { if (n == 1) (n 1) return 1; S(1) S(2) S(3) … S(n-1) int S = 0; … for (int i = 1; i
  15. Nội dung Tổng quan về đệ quy. quy. Phân loại đệ quy. quy. Các vấn đề đệ quy thông dụng. dụng. Kỹ thuật lập trình - Nguyễn Minh Huy 15
  16. Các vấn đề đệ quy thông dụng Cách giải bài toán bằng đệ quy: quy: Cách giải không đệ quy: quy: Lời giải trực tiếp. tiếp. Tìm các bước đi đến kết quả. quả. Cách giải đệ quy: quy: Lời giải gián tiếp. tiếp. Định nghĩa lại bài toán bằng đệ quy. quy. Bước 1: định nghĩa trường hợp cơ bản. bản. Bước 2: suy biến bài toán về trường hợp đơn giản hơn. hơn. Công thức truy hồi (suy biến bằng công thức). thức). Chia để trị (suy biến bằng chia nhỏ). nhỏ). Lần ngược (tìm tất cả lời giải). giải). Kỹ thuật lập trình - Nguyễn Minh Huy 16
  17. Các vấn đề đệ quy thông dụng Công thức truy hồi: hồi: Tính phần tử An của dãy số { A }: Công thức tính trực tiếp: tiếp: Tính An độc lập với các phần tử khác. khác. Công thức truy hồi: hồi: Tính A0. Giả sử đã tính An-1. Tính An dựa vào An-1. Phụ hợp với cách giải bằng đệ quy. quy. Kỹ thuật lập trình - Nguyễn Minh Huy 17
  18. Các vấn đề đệ quy thông dụng Công thức truy hồi: hồi: Ví dụ 1: Vi khuẩn cứ 1 phút nhân đôi. đôi. int tinhVK(int phut) tinhVK( phut) Ban đầu có 1 vi khuẩn. khuẩn. { if (phut == 0) (phut Sau 20 phút bao nhiêu con? return 1; V(0) = 1 return 2 * tinhVK(phut – 1); tinhVK( V(n) = 2 * V(n - 1). } Ví dụ 2: Lãi suất tiết kiệm 7%/năm. 7%/năm. int tinhTK(int nam) tinhTK( nam) { Ban đầu gửi 1 triệu. triệu. if (nam == 0) (nam Sau 20 năm bao nhiêu tiền?tiền? return 1; T(0) = 1 return 1.07 * tinhTK(nam – 1); tinhTK( T(n) = T(n – 1) + 0.07 * T(n – 1) } = 1.07 T(n – 1). Kỹ thuật lập trình - Nguyễn Minh Huy 18
  19. Các vấn đề đệ quy thông dụng Kỹ thuật chia để trị (Divide & Conquer): Làm sao để ăn hết một con bò? bò? Chia thành từng phần nhỏ. nhỏ. Thế nào là đủ nhỏ? nhỏ? Giải toán bằng kỹ thuật chia để trị: trị: Trị ( P ) { if (P đủ nhỏ) (P nhỏ) Xử lý P; else Chia P P1, P2, … Pn; for (int i = 0; i < n; i++) (int Trị ( Pi ); Tổng hợp kết quả; quả; } Kỹ thuật lập trình - Nguyễn Minh Huy 19
  20. Các vấn đề đệ quy thông dụng Kỹ thuật chia để trị (Divide & Conquer): Ví dụ: dụ: Cho mảng nguyên 1 chiều. chiều. int demAm(int *a, int l, int r) demAm( Đếm số âm trong mảng. mảng. { if (l == r) (l r) - Mảng đủ nhỏ (1 phần tử): tử): return a[r] < 0 ? 1 : 0; + Kiểm tra âm phần tử duy nhất. nhất. - Mảng nhiều phần tử: tử: int mid = (l + r) / 2; + Chia mảng làm 2 phần. phần. int dem1 = demAm(a, l, mid); demAm(a, + Đếm âm từng phần. phần. int dem2 = demAm(a, mid+1, r); demAm(a, + Cộng kết quả lại. lại. return dem1 + dem2; dem2; } Kỹ thuật lập trình - Nguyễn Minh Huy 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
8=>2