Chương 2: Đệ Qui và giải thuật đệ qui - Cô Võ Thị Hường

1. 2. 3. Phép lặp, quy nạp và đệ quy Giải thuật đệ quy Các bài toán liên quan đệ qui   Lặp (interation): biến thể của cùng một thao tác. Quy nạp (induction): kĩ thuật chứng minh các mệnh đề thuộc dạng với mọi n thì P(n) là đúng. Ví dụ: với mọi n, tổng n số lẻ đầu tiên bằng n2 . Bước cơ sở: Chỉ ra P(1) là đúng , vì 12=1. Bước quy nạp: Chứng minh nếu P(n) là đúng thì kéo theo P(n+1) cũng đúng Tổng n số lẻ là n2, cần cm tổng (n+1) số lẻ là (n+1)2. Tổng n số lẻ: 1+3+5+….+ (2n-1)= n2. Khi đó: [1+3+5+….+ (2n-1)] +(2n+1) = n2+2n+1= (n+1)2.  Đệ quy (recursion): là một kĩ thuật định nghĩa một khái niệm trực tiếp hoặc gián tiếp theo chính nó. a) Định nghĩa Nếu lời giải P được thực hiện bằng lời giải P’ có dạng giống như P thì ta nói đó là lời giải đệ quy  thuật toán đệ quy  Chú ý: ◦ P’ giống P ◦ P’ “nhỏ hơn” P theo nghĩa nào đó   Định nghĩa một hàm hay thủ tục đệ quy gồm hai phần: (i) Phần neo (anchor): công việc đơn giản, có thể giải trực tiếp mà không cần nhờ bài toán con (ii) Phần đệ quy: TH bài toán không giải quyết bằng phần neo, ta xác định bài toán con và gọi đệ qui để giải bài toán con đó Phần đệ quy thể hiện tính “quy nạp” của lời giải. Phần neo đảm bảo cho tính dừng của thuật toán.   3.1 Hàm tính giai thừa 3.2 Dãy số Fibonacci 0!=1  1!=1*0!=1  2!=2*1!  3!=3*2!  ……  N!=n*(n-1)! Phần neo là phần định nghĩa kq hàm tại n=0 Phần đệ qui (n>0) là phần tính giai thừa của n dựa vào n và giai thừa n-1  Giải thuật Funtion F(n: integer) Begin if n=0 then F:=1 else F:=n*F(n-1) End;  Phần neo Phần đệ qui  • • • Dựa vào bài toán cổ liên quan đến ss của các cặp thỏ Các cặp thỏ không bao giờ chết Hai tháng sau khi ra đời mỗi cặp thỏ sinh ra 1 cặp thỏ con (1 đực 1 cái) Mỗi tháng sau đó nó lại sinh ra 1 cặp mới Giả sử đầu tháng 1 có 1 cặp thỏ ra đời thì đến giữa tháng n có bao nhiêu cặp thỏ?  N=5 Giữa tháng 1 có 1 cặp (ab) Giữa tháng 2 có 1 cặp (ab) Giữa tháng 3 có 2 cặp (AB)(cd) Giữa tháng 4 có 3 cặp (AB)(cd)(ef) Giữa tháng 5 có 5 cặp( AB)(CD)(ef)(c’d’)(a’b’)  Tính F(n) như sau +F(n)=1 nếu n<=2 +F(n)=F(n-1)+F(n-2) nếu n>2 Viết hàm đệ qui của dãy số Fibonacci? Funtion F(n: integer) Begin if n<=0 then F:=1 else F:=F(n-1)+F(n-2) End;  Cho biết số Fibonacci F 11 = 89 và F 12 = 144 a. Hãy tính F 16 . b. Viết một thủ tục không đệ quy ( dùng phép lặp) để tính và in ra n số Fibonacci đầu tiên.  Bc1: Tính F1=1, F2=1 thì F=1  N>=3 thì F=F(n-1)+F(n-2)  Kết thúc b) Ví dụ: Dãy số Fibonacci: F(n)= F(n-1)+F(n2) (phần đệ quy) ◦ với n<=2 thì F(n)=1 ( phần neo). Recursion - Example • Fibonacci Numbers Pseudo-code C fib( n ) = if ( n = 0 ) then 1 else if ( n = 1 ) then 1 else fib(n-1) + fib(n-2) int fib( n ) { if ( n < 2 ) return 1; else return fib(n-1) + fib(n-2); } Simple, elegant solution!  Bài toán tháp Hà nội : Ngôi đền Benares có 03 cái cọc kim cương, Thượng đế đặt n chiếc đĩa bằng vàng: - Có bán kính khác nhau - Chồng lên nhau ở một chiếc cọc - Theo thứ tự đĩa lớn ở dưới, đĩa nhỏ ở trên. Các nhà sư lần lượt chuyển các đĩa sang một cọc khác theo quy tắc sau:    Khi chuyển một đĩa phải đặt vào một trong 03 cọc Mỗi lần chỉ chuyển đúng một đĩa trên cùng tại một cọc và đặt vào trên cùng ở cọc chuyển đến. Đĩa lớn hơn không được phép đặt lên đĩa nhỏ hơn.     Ví dụ, với trường hợp n=2 ta có thể chuyển như sau: Chuyển đĩa nhỏ sang cọc 3 Chuyển đĩa lớn sang cọc 2 Chuyển đĩa từ cọc 3 sang cọc 2 Nếu n=1 thì chuyển đĩa duy nhất đó từ cọc 1 sang cọc 2. Kết thúc. Giả thiết ta có cách chuyển (n-1) đĩa từ cọc 1 sang cọc 3.  Chuyển đĩa lớn nhất đang ở cọc 1 sang cọc 2  Chuyển (n-1) đĩa từ cọc 3 sang cọc 2.  Kết thúc.  c) Đánh giá về đệ quy Ưu điểm: ◦ Mạnh, rõ ràng, chặt chẽ ◦ Thiết kế TT đơn giản Nhược điểm: ◦ Lời gọi hàm tốn rất nhiều thời gian. ◦ Thận trọng đừng để chạy vô hạn.