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

Bài giảng Nhập môn lập trình - Chương 16: Kỹ thuật lập trình đệ quy

Chia sẻ: Kiếp Này Bình Yên | Ngày: | Loại File: PPT | Số trang:43

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

Chương 16 trang bị cho người học những hiểu biết về kỹ thuật lập trình đệ quy. Trong chương này chúng ta sẽ cùng tìm hiểu một số nội dung cơ bản sau: Tổng quan về đệ quy, các vấn đề đệ quy thông dụng, phân tích giải thuật và khử đệ quy, các bài toán kinh điển. 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 Nhập môn lập trình - Chương 16: Kỹ thuật lập trình đệ quy

  1. && VC VC BB BB Nội dung 1 Tổng quan về đệ quy 2 Các vấn đề đệ quy thông dụng 3 Phân tích giải thuật & khử đệ quy 4 Các bài toán kinh điển NMLT ­ Kỹ thuật lập trình đệ quy 1
  2. && VC VC BB BB Bài toán  Cho S(n) = 1 + 2 + 3 + … + n =>S(10)? S(11)? S(10) = 11 + 22 + … + 10 10 = 55 55 S(11) = 11 + 22 + … + 10 10 + 11 11 = 66 66 = S(10) + 11 11 = 55 55 + 11 11 = 66 66 NMLT ­ Kỹ thuật lập trình đệ quy 2
  3. && VC VC BB BB 2 bước giải bài toán Bước 2. Thế ngược ác  định  kết  quả  bài  toán  đồng  S(n) = S(n­1) + nn dạng từ  đơn giản  đến phức tạp   Kết quả cuối cùng. S(n­1) = S(n­2) + n­1 n­1 … = … + … … Bước 1. Phân tích S(1) = S(0) + 11 hân  tích  thành  bài  toán  đồng  dạng nhưng đơn giản hơn. S(0) = 00 ừng  lại  ở  bài  toán  đồng  dạng  đơn  giản  nhất  có  thể  xác  định  ngay kết quả. NMLT ­ Kỹ thuật lập trình đệ quy 3
  4. && VC VC BB BB Khái niệm đệ quy Khái niệm Vấn đề đệ quy là vấn đề được  định nghĩa bằng chính nó. Ví dụ Tổng S(n) được tính thông qua  tổng S(n­1). 2 điều kiện quan trọng  Tồn tại bước đệ quy.  Điều kiện dừng. NMLT ­ Kỹ thuật lập trình đệ quy 4
  5. && VC VC BB BB Hàm đệ quy trong NNLT C  Khái niệm  Một hàm được gọi là đệ quy nếu bên trong thân của hàm đó có lời gọi hàm lại chính nó một cách trực tiếp hay gián tiếp. … Hàm(…) … Hàm1(…) … Hàm2(…) { { { … … … … … … Lời gọi Hàm Lời gọi Hàm2 Lời gọi Hàmx … … … … … … … … … } } } ĐQ trực tiếp ĐQ gián tiếp NMLT ­ Kỹ thuật lập trình đệ quy 5
  6. && VC VC BB BB Cấu trúc hàm đệ quy { (TS) Phần dừng    if ()(Base step)    { • Phần khởi tính toán hoặc điểm  kết thúc của thuật toán       … • Không chứa phần đang được        return ; định nghĩa    } Phần đệ quy    …  (Recursion step)    … Lời gọi Hàm• Có sử dụng thuật toán đang  được định nghĩa.    … } NMLT ­ Kỹ thuật lập trình đệ quy 6
  7. && VC VC BB BB Phân loại Trong  thân  hàm  có  duy  nhất  một  TUYẾN TÍNH 1 lời  gọi  hàm  gọi  lại  chính  nó  một  cách tường minh. Trong  thân  hàm  có  hai  lời  gọi  NHỊ PHÂN 2 hàm  gọi  lại  chính  nó  một  cách  tường minh. HỖ TƯƠNG Trong  thân  hàm  này  có  lời  gọi  hàm  tới  PHI TUYẾN 3 hàm  kia  và  bên  trong  thân  hàm  kia  có  lời gọi hàm tới hàm này. 4 Trong thân hàm có lời gọi hàm lại chính  nó được đặt bên trong thân vòng lặp. NMLT ­ Kỹ thuật lập trình đệ quy 7
  8. && VC VC BB BB Đệ quy tuyến tính Ví dụ Tính S(n) = 1 + 2 + … + n  S(n) = S(n – 1) + n ĐK dừng: S(0) = 0 Cấu trúc chương trình .: Chương trình :. long Tong(int n) {  TênHàm() {    if (n == 0)    if () {       return 0;       …    return Tong(n–1) + n;       return ; }    }    … TênHàm(); … } NMLT ­ Kỹ thuật lập trình đệ quy 8
  9. && VC VC BB BB Đệ quy nhị phân Ví dụ Tính số hạng thứ n của dãy  Fibonacy: f(0) = f(1) = 1 f(n) = f(n – 1) + f(n – 2) n > 1 Cấu trúc chương trình ĐK dừng: f(0) = 1 và f(1) = 1  TênHàm() {    if () { .: Chương trình :.       … long Fibo(int n)       return ; {    }    if (n == 0 || n == 1)    … TênHàm();       return 1;    …    return Fibo(n–1)+Fibo(n–2);    … TênHàm(); }    … } NMLT ­ Kỹ thuật lập trình đệ quy 9
  10. && VC VC BB BB Đệ quy hỗ tương Ví dụ Tính số hạng thứ n của dãy: x(0) = 1, y(0) = 0 x(n) = x(n – 1) + y(n – 1) y(n) = 3*x(n – 1) + 2*y(n – 1) Cấu trúc chương trình ĐK dừng: x(0) = 1, y(0) = 0  TênHàm1() { .: Chương trình :.    if () long yn(int n);       return ; long xn(int n) {    … TênHàm2(); …    if (n == 0) return 1; }    return xn(n­1)+yn(n­1);  TênHàm2() { }    if () long yn(int n) {       return ;    if (n == 0) return 0;    … TênHàm1(); …    return 3*xn(n­1)+2*yn(n­1); } } NMLT ­ Kỹ thuật lập trình đệ quy 10
  11. && VC VC BB BB Đệ quy phi tuyến Ví dụ Tính số hạng thứ n của dãy: x(0) = 1 x(n) = n2x(0) + (n­1)2x(1) + … +  22x(n – 2) + 12x(n – 1) Cấu trúc chương trình ĐK dừng: x(0) = 1  TênHàm() {    if () { .: Chương trình :.       … long xn(int n)       return ; {    }    if (n == 0) return 1;    … Vòng lặp {    long s = 0;       … TênHàm(); …    for (int i=1; i
  12. && VC VC BB BB Các bước xây dựng hàm đệ quy  Tổng quát hóa bài toán cụ thể thành bài toán tổng quát. Thông số hóa  Thông số hóa cho bài toán tổng quát bài toán  VD: n trong hàm tính tổng S(n), …  Chia bài toán tổng quát ra thành:  Phần không đệ quy. Tìm thuật giải  Phần như bài toán trên nhưng tổng quát kích thước nhỏ hơn.  VD: S(n) = S(n – 1) + n, …  Các trường hợp suy biến của bài toán.  Kích thước bài toán trong trường hợp Tìm các trường này là nhỏ nhất. hợp suy biến (neo)  VD: S(0) = 0 NMLT ­ Kỹ thuật lập trình đệ quy 12
  13. && VC VC BB BB Cơ chế gọi hàm và STACK main() B() main { {    …;    …;    A();    D();    …;    …;       D(); } A D    …; } C() { A()    …; { } B C    …;    B(); D D() STACK    …; B B B C    C(); {    …;    …; D A A A A A A A D } } M M M M M M M M M M M Thời gian NMLT ­ Kỹ thuật lập trình đệ quy 13
  14. && VC VC BB BB Nhận xét  Cơ chế gọi hàm dùng STACK trong C phù hợp cho giải thuật đệ quy vì:  Lưu thông tin trạng thái còn dở dang mỗi khi gọi đệ quy.  Thực hiện xong một lần gọi cần khôi phục thông tin trạng thái trước khi gọi.  Lệnh gọi cuối cùng sẽ hoàn tất đầu tiên. NMLT ­ Kỹ thuật lập trình đệ quy 14
  15. && VC VC BB BB Ví dụ gọi hàm đệ quy  Tính số hạng thứ 4 của dãy Fibonacy F(4) 5 3 F(3) 5 + 2 F(2) 2 F(2) 3 + 1 F(1) 1 F(1) 2 + 1 F(0) 1 F(1) 2 + 1 F(0) NMLT ­ Kỹ thuật lập trình đệ quy 15
  16. && VC VC BB BB Một số lỗi thường gặp  Công thức đệ quy chưa đúng, không tìm được bài toán đồng dạng đơn giản hơn (không hội tụ) nên không giải quyết được vấn đề.  Không xác định các trường hợp suy biến – neo (điều kiện dừng).  Thông điệp thường gặp là StackOverflow do:  Thuật giải đệ quy đúng nhưng số lần gọi đệ quy quá lớn làm tràn STACK.  Thuật giải đệ quy sai do không hội tụ hoặc không có điều kiện dừng. NMLT ­ Kỹ thuật lập trình đệ quy 16
  17. && VC VC BB BB Các vấn đề đệ quy thông dụng ĐĐệệ    quy?? quy?? NMLT ­ Kỹ thuật lập trình đệ quy 17
  18. && VC VC BB BB 1.Hệ thức truy hồi  Khái niệm  Hệ thức truy hồi của 1 dãy An là công thức biểu diễn phần tử An thông qua 1 hoặc nhiều số hạng trước của dãy. AA00 AA11 … … AAn­2 n­2 AAn­1 n­1 Hàm truy h AAnn Hàm truy h ồồii AA00 AA11 … … AAn­2 n­2 AAn­1 n­1 Hàm truy h AAnn Hàm truy h ồồii NMLT ­ Kỹ thuật lập trình đệ quy 18
  19. && VC VC BB BB 1.Hệ thức truy hồi  Ví dụ 1  Vi trùng cứ 1 giờ lại nhân đôi. Vậy sau 5 giờ sẽ có mấy con vi trùng nếu ban đầu có 2 con?  Giải pháp  Gọi Vh là số vi trùng tại thời điểm h.  Ta có: • Vh = 2Vh-1 • V0 = 2  Đệ quy tuyến tính với V(h)=2*V(h-1) và điều kiện dừng V(0) = 2 NMLT ­ Kỹ thuật lập trình đệ quy 19
  20. && VC VC BB BB 1.Hệ thức truy hồi  Ví dụ 2  Gửi ngân hàng 1000 USD, lãi suất 12%/năm. Số tiền có được sau 30 năm là bao nhiêu?  Giải pháp  Gọi Tn là số tiền có được sau n năm.  Ta có: • Tn = Tn-1 + 0.12Tn-1 = 1.12Tn-1 • V(0) = 1000  Đệ quy tuyến tính với T(n)=1.12*T(n-1) và điều kiện dừng V(0) = 1000 NMLT ­ Kỹ thuật lập trình đệ 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