NHẬP MÔN LẬP TRÌNH KỸ THUẬT LẬP TRÌNH ĐỆ QUY 1 & VC 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 2 & VC BB Bài toán Cho S(n) = 1 + 2 + 3 + ầ + n =>S(10)? S(11)? S(10) = 1 + 2 + … + 10 = 55 S(11) = 1 + 2 + … + 10 + 11 = 66 = S(10) = 55 + 11 + 11 = 66 NMLT - Kỹ thuật lập trình đệ quy 3 & VC BB 2 bước giải bài toán Bước 2. Thế ngược S(n)  Xác định kết quả bài toán đồng dạng từ đơn giản đến phức tạp  Kết quả cuối cùng. = S(n-1) + n S(n-1) = S(n-2) + n-1 … Bước 1. Phân tích  Phân tích thành bài toán đồng dạng nhưng đơn giản hơn.  Dừng lại ở bài toán đồng dạng đơn giản nhất có thể xác định ngay kết quả. = … S(1) + … = S(0) + 1 S(0) = 0 NMLT - Kỹ thuật lập trình đệ quy 4 & VC 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 5 & VC 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(ầ) { ầ ầ Lời gọi Hàm ầ ầ ầ } ĐQ trực tiếp ầ Hàm1(ầ) { ầ ầ Lời gọi Hàm2 ầ ầ ầ } ầ Hàm2(ầ) { ầ ầ Lời gọi Hàmx ầ ầ ầ } ĐQ gián tiếp NMLT - Kỹ thuật lập trình đệ quy 6 & VC BB Cấu trúc hàm đệ quy <Kiểu> <TênHƠm>(TS) { Phần dừng (Base step) if (<ĐK dừng>) • 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 <Giá trị>; đị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 7 & VC BB Phân loại TUY N TÍNH NH PHÂN H PHI TUY N T 1 2 Trong thân hàm có duy nhất một 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 hàm gọi lại chính nó một cách tường minh. NG 3 Trong thân hàm này có lời gọi hàm tới 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 8 & VC 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 <Kiểu> TênHàm(<TS>) { if (<ĐK đừng>) { … return <Giá Trị>; } … TênHàm(<TS>); … } .: Chương trình :. long Tong(int n) { if (n == 0) return 0; return Tong(n–1) + n; } NMLT - Kỹ thuật lập trình đệ quy 9 & VC BB Đệ quy nhị phân Ví dụ C u trúc ch ng trình <Kiểu> TênHàm(<TS>) { if (<ĐK dừng>) { … return <Giá Trị>; } … TênHàm(<TS>); … … TênHàm(<TS>); … } 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 ĐK dừng: f(0) = 1 và f(1) = 1 .: Chương trình :. long Fibo(int n) { if (n == 0 || n == 1) return 1; return Fibo(n–1)+Fibo(n–2); } NMLT - Kỹ thuật lập trình đệ quy 10 & VC BB Đệ quy hỗ tương Ví dụ C u trúc ch ng trình <Kiểu> TênHàm1(<TS>) { if (<ĐK dừng>) return <Giá trị>; … TênHàm2(<TS>); … } <Kiểu> TênHàm2(<TS>) { if (<ĐK dừng>) return <Giá trị>; … TênHàm1(<TS>); … } 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) ĐK dừng: x(0) = 1, y(0) = 0 .: Chương trình :. long yn(int n); long xn(int n) { if (n == 0) return 1; return xn(n-1)+yn(n-1); } long yn(int n) { if (n == 0) return 0; return 3*xn(n-1)+2*yn(n-1); } NMLT - Kỹ thuật lập trình đệ quy 11 & VC BB Đệ quy phi tuyến Ví dụ C u trúc ch ng trình <Kiểu> TênHàm(<TS>) { if (<ĐK dừng>) { … return <Giá Trị>; } … Vòng lặp { … TênHàm(<TS>); … } … } 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) ĐK dừng: x(0) = 1 .: Chương trình :. long xn(int n) { if (n == 0) return 1; long s = 0; for (int i=1; i<=n; i++) s = s + i*i*xn(n–i); return s; } NMLT - Kỹ thuật lập trình đệ quy 12 & VC BB Các bước xây dựng hàm đệ quy Thông số hóa bài toán Tìm thu t giải t ng quát Tìm các tr ờng hợp suy bi n (neo)  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 cho bƠi toán t ng quát  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.  Ph n nh bài toán trên nh ng 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 nƠy lƠ nhỏ nh t.  VD: S(0) = 0 NMLT - Kỹ thuật lập trình đệ quy 13 & Cơ chế gọi hàm và STACK BB main() { } …; A(); …; D(); …; } { } main …; D(); …; D A C() A() { B() { } …; B(); …; C(); …; …; D() { } …; C B STACK VC D D B B B C 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 14 & VC 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 15 & VC 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) 1 F(1) 2 F(2) 3 + 2 + 1 F(0) 5 + 1 F(1) 2 F(2) 1 F(1) 2 + 1 F(0) NMLT - Kỹ thuật lập trình đệ quy 16 & VC 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 17 & VC BB Các vấn đề đệ quy thông dụng Đệ quy?? NMLT - Kỹ thuật lập trình đệ quy 18 & VC 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. A0 A1 … An-2 An-1 An hồi Hàm truy A0 A1 … An-2 An-1 An hồi Hàm truy NMLT - Kỹ thuật lập trình đệ quy 19 & VC 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 20 & VC 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 21 & VC BB 2.Chia để trị (divide & conquer) Khái niệm  Chia bài toán thành nhiều bƠi toán con.  Giải quy t từng bƠi toán con.  T ng hợp k t quả từng bƠi toán con để ra lời giải. NMLT - Kỹ thuật lập trình đệ quy 22 & VC BB 2.Chia để trị (divide & conquer) Ví dụ 1  Cho dãy A đư sắp x p thứ tự tăng. Tìm v trí ph n tử x trong dưy (n u có) Giải pháp  mid = (l + r) / 2;  N u A[mid] = x  trả về mid.  Ng ợc lại • N u x < A[mid]  tìm trong đoạn [l, mid ậ 1] • Ng ợc lại  tìm trong đoạn [mid + 1, r]  Sử dụng đệ quy nh phơn. NMLT - Kỹ thuật lập trình đệ quy 23 & VC BB 2.Chia để trị (divide & conquer) Ví dụ 2  Tính tích 2 chu i số cực lớn X vƠ Y Giải pháp  X = X2n-1ầXnXn-1ầX0, Y = Y2n-1ầYnYn-1ầY0  Đặt XL=X2n-1ầXn, XN=Xn-1ầX0  X=10nXL+XN  Đặt YL=Y2n-1ầYn, YN=Yn-1ầY0  Y=10nYL+YN   X*Y = 102nXLYL + 10n(XLYL+XNYN)+XNYN  và XLYL+XNYN = (XL-XN)(YN-YL)+XLYL+XNYN NMLT - Kỹ thuật lập trình đệ quy 24 & VC BB 2.Chia để trị (divide & conquer) M t số bƠi toán khác  BƠi toán tháp HƠ N i  Các giải thu t sắp x p: QuickSort, MergeSort  Các giải thu t tìm ki m trên cơy nh phơn tìm ki m, cơy nh phơn nhiều nhánh tìm ki m. L u ý  Khi bƠi toán lớn đ ợc chia thƠnh các bƠi toán nhỏ h n mƠ những bƠi toán nhỏ h n này không đ n giản nhiều so với bƠi toán gốc thì không nên dùng kỹ thu t chia để tr . NMLT - Kỹ thuật lập trình đệ quy 25 & VC BB 3.Lần ngược (Backtracking) Khái niệm  Tại b ớc có nhiều lựa chọn, ta chọn thử 1 b ớc để đi ti p.  N u không thƠnh công thì “l n ng ợc” chọn b ớc khác.  N u đư thƠnh công thì ghi nh n lời giải nƠy đồng thời “l n ng ợc” để truy tìm lời giải mới.  Thích hợp giải các bƠi toán kinh điển nh bài toán 8 h u vƠ bƠi toán mư đi tu n. NMLT - Kỹ thuật lập trình đệ quy 26 & 3.Lần ngược (Backtracking) VC BB Ví dụ  Tìm đ ờng đi từ X đ n Y. D A B Y X C NMLT - Kỹ thuật lập trình đệ quy 27 & VC BB Một số bài toán kinh điển THÁP HÀ N I TÁM H U ầ # $ @ 1 2 3 1 3 2 MÃ ĐI TU N PHÁT SINH HOÁN V NMLT - Kỹ thuật lập trình đệ quy 28 & VC BB Tháp Hà Nội Mô tả bƠi toán  Có 3 c t A, B vƠ C vƠ c t A hiện có N đĩa.  Tìm cách chuyển N đĩa từ c t A sang c t C sao cho: • M t l n chuyển 1 đĩa • Đĩa lớn h n phải nằm d ới. • Có thể sử dụng các c t A, B, C lƠm c t trung gian. NMLT - Kỹ thuật lập trình đệ quy 29 & VC BB Tháp Hà Nội N đĩa A  C = N-1 ? đĩa A  B + Đĩa N A  C + N-1 đĩa B  C 1 … N-1 N Cột nguồn A Cột trung gian B Cột đích C NMLT - Kỹ thuật lập trình đệ quy 30 & VC BB Tám hậu Mô tả bƠi toán  Cho bƠn cờ vua kích th ớc 8x8  Hãy đặt 8 hoƠng h u lên bƠn cờ nƠy sao cho không có hoƠng h u nƠo “ăn” nhau: • Không nằm trên cùng dòng, cùng c t • Không nằm trên cùng đ ờng chéo xuôi, ng ợc. NMLT - Kỹ thuật lập trình đệ quy 31 & VC BB Tám hậu – Các dòng 0 1 n đường 2 3 4 5 6 7 NMLT - Kỹ thuật lập trình đệ quy 32 & VC BB Tám hậu – Các cột 0 1 2 3 4 5 6 7 n đường NMLT - Kỹ thuật lập trình đệ quy 33 & VC BB Tám hậu – Các đường chéo xuôi 0 2n-1 đường 1 2 3 4 5 6 14 13 12 11 10 9 8 7 NMLT - Kỹ thuật lập trình đệ quy 34 & VC BB Tám hậu – Các đường chéo ngược 2n-1 đường 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 NMLT - Kỹ thuật lập trình đệ quy 35 & VC BB Tám hậu – Các dòng i=2 j=3 j+i=5 j-i+n-1=8 NMLT - Kỹ thuật lập trình đệ quy 36 & VC BB Mã đi tuần Mô tả bƠi toán  Cho bƠn cờ vua kích th ớc 8x8 (64 ô)  Hãy đi con mã 64 n ớc sao cho m i ô ch đi qua 1 l n (xu t phát từ ô b t kỳ) theo lu t: 5 6 4 7 3 8 2 1 NMLT - Kỹ thuật lập trình đệ quy 37 & VC BB Phân tích giải thuật đệ quy Sử dụng cơy đệ quy (recursive tree)  Giúp hình dung b ớc phơn tích vƠ th ng ợc.  B ớc phân tích: đi từ trên xuống d ới.  B ớc th ng ợc đi từ trái sang phải, từ d ới lên trên.  Ý nghĩa • Chiều cao của cơy  Đ lớn trong STACK. • Số nút  Số lời gọi hƠm. NMLT - Kỹ thuật lập trình đệ quy 38 & VC BB Nhận xét  u điểm  Sáng sủa, dễ hiểu, nêu rõ bản ch t v n đề.  Ti t kiệm thời gian thực hiện mư nguồn.  M t số bƠi toán r t khó giải n u không dùng đệ qui. Khuy t điểm  Tốn nhiều b nhớ, thời gian thực thi lơu.  M t số tính toán có thể b lặp lại nhiều l n.  M t số bƠi toán không có lời giải đệ quy. NMLT - Kỹ thuật lập trình đệ quy 39 & VC BB Ví dụ cây đệ quy Fibonacy F(4) F(3) F(2) F(1) F(2) F(1) F(0) F(1) F(0) Lặp lại NMLT - Kỹ thuật lập trình đệ quy 40 & VC BB Khử đệ quy (Tham khảo) Khái niệm  Đ a các bài toán đệ quy về các bƠi toán không sử dụng đệ quy.  Th ờng sử dụng vòng lặp hoặc STACK tự tạo. ầ NMLT - Kỹ thuật lập trình đệ quy 41 & VC BB Tổng kết Nh n xét  Ch nên dùng ph ng pháp đệ quy để giải các bài toán kinh điển nh giải các v n đề “chia để tr ”, “l n ng ợc”.  V n đề đệ quy không nh t thi t phải giải bằng ph ng pháp đệ quy, có thể sử dụng ph ng pháp khác thay th (khử đệ quy)  Tiện cho ng ời l p trình nh ng không tối u khi chạy trên máy.  B ớc đ u nên giải bằng đệ quy nh ng từng b ớc khử đệ quy để nơng cao hiệu quả. 42 NMLT - Kỹ thuật lập trình đệ quy & VC BB Bài tập thực hành Bài 1: Các bƠi t p trên mảng sử dụng đệ quy. Bài 2: Vi t hƠm xác đ nh chiều dƠi chu i. Bài 3: Hiển th n dòng của tam giác Pascal.  a[i][0] = a[i][i] = 1  a[i][k] = a[i-1][k-1] + a[i-1][k] Bài 4: Vi t hƠm đệ quy tính C(n, k) bi t  C(n, k) = 1 n u k = 0 hoặc k = n  C(n, k) = 0 n u k > n  C(n ,k) = C(n-1, k) + C(n-1, k-1) n u 0<k<n NMLT - Kỹ thuật lập trình đệ quy 43 & VC BB Bài tập thực hành Bài 5: Đ i 1 số th p phơn sang c số khác. Bài 6: BƠi toán 8 h u Bài 7: Bài toán mã đi tu n Bài 8: Tính các t ng truy hồi. NMLT - Kỹ thuật lập trình đệ quy 44