Đệ qui Recursion

ãTrong qui nạp, ta chứng minh mọi phần tử của tập vô hạn thoả mãn mệnh đề P nào đó bằng cách: –Chứng minh tính đúng đắn của mệnh đề cho các phần tử lớn hơn mà biểu diễn qua các phần tử bé hơn. ãTrong định nghĩa đệ qui, tương tự ta định nghĩa hàm số, mệnh đề, tập hợp, hay một cấu trúc phức tạp hơn trên miền biến thiên vô hạn bằng cách: –định nghĩa hàm, giá trị mệnh đề, tính chất thuộc của tập hợp, hoặc cấu trúc của các phần tử lớn hơn biểu diễn qua các phần tử nhỏ hơn. ãTrong qui nạp cấu trúc, ta chứng minh qui nạp các tính chất của các đối tượng xác định đệ qui theo cách mà nó song hành xây dựng lên chính đối tượng đệ qui đó.

ppt44 trang | Chia sẻ: tlsuongmuoi | Lượt xem: 2316 | Lượt tải: 0download
Bạn đang xem trước 20 trang tài liệu Đệ qui Recursion, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
University of Florida Dept. of Computer & Information Science & Engineering COT 3100 Applications of Discrete Structures Dr. Michael P. Frank Slides for a Course Based on the Text Discrete Mathematics & Its Applications (5th Edition) by Kenneth H. Rosen Module #16: Đệ qui Recursion Rosen 5th ed., §§3.4-3.5 ~34 slides, ~2 lectures Định nghĩa đệ qui §3.4: Recursive Definitions Trong qui nạp, ta chứng minh mọi phần tử của tập vô hạn thoả mãn mệnh đề P nào đó bằng cách: Chứng minh tính đúng đắn của mệnh đề cho các phần tử lớn hơn mà biểu diễn qua các phần tử bé hơn. Trong định nghĩa đệ qui, tương tự ta định nghĩa hàm số, mệnh đề, tập hợp, hay một cấu trúc phức tạp hơn trên miền biến thiên vô hạn bằng cách: định nghĩa hàm, giá trị mệnh đề, tính chất thuộc của tập hợp, hoặc cấu trúc của các phần tử lớn hơn biểu diễn qua các phần tử nhỏ hơn. Trong qui nạp cấu trúc, ta chứng minh qui nạp các tính chất của các đối tượng xác định đệ qui theo cách mà nó song hành xây dựng lên chính đối tượng đệ qui đó. Đệ qui - Recursion Đệ qui là thuật ngữ nói chung trong thực hành để định nghĩa một đối tượng thông qua chính nó Hoặc một phần của chính nó Điều đó trông có vẻ luẩn quẩn, nhưng không hẳn như vậy. Chứng minh qui nạp thiết lập tính đúng đắn của P(n+1) đệ qui qua thuật ngữ của P(n). Có các thuật toán, định nghĩa hàm, dãy, tập hợp và các cấu trúc khác đệ qui. Các hàm định nghĩa đệ qui Recursively Defined Functions T/h đơn giản nhất: Một cách đ/n hàm f:NS (với tập S bất kỳ) hoặc dãy an=f(n) như sau: Định nghĩa f(0). Với n>0, định nghĩa f(n) thông qua f(0),…,f(n−1). VD: Định nghĩa dãy an :≡ 2n đệ qui: G/s a0 :≡ 1. Với n>0, đặt an :≡ 2an-1. Ví dụ khác - Another Example G/s ta định nghĩa f(n) đối với mọi nN đệ qui như sau: G/s f(0)=3 Với mọi nN, cho f(n+1)=2f(n)+3 Các giá trị sau đây bằng bao nhiêu? f(1)= f(2)= f(3)= f(4)= 9 21 45 93 Định nghĩa giai thừa đệ qui Recursive definition of Factorial Cho định nghĩa qui nạp (đệ qui) của hàm giai thừa như sau, F(n) :≡ n! :≡ ∏1≤i≤n i = 12…n. T/h cơ sở: F(0) :≡ 1 Phần đệ qui: F(n) :≡ n  F(n−1). F(1)=1 F(2)=2 F(3)=6 Một sô ví dụ đơn giản Viết định nghĩa đệ qui cho: i+n (i nguyên, n tự nhiên) chỉ sử dụng s(i) = i+1. a·n (a thực, n tự nhiên) chỉ sử dụng cộng an (a thực, n tự nhiên) chỉ sử dụng nhân ∑0≤i≤n ai (cho dãy sô bất kỳ {ai}) ∏0≤i≤n ai (cho dãy số bất kỳ {ai}) ∩0≤i≤n Si (cho dãy tập hợp bất kỳ {Si}) Dãy Fibonacci The Fibonacci Series Dãy Fibonacci fn≥0 là dãy nổi tiếng được định nghĩa như sau: f0 :≡ 0, f1 :≡ 1, fn≥2 :≡ fn−1 + fn−2 Leonardo Fibonacci 1170-1250 0 1 1 2 3 5 8 13 C/m qui nạp về dãy Fibonacci Định lý: fn αn−2, trong đó α = (1+51/2)/2 ≈ 1.61803. C/m. (Sử dụng qui nạp mạnh.) G/s P(n) = (fn > αn−2). T/h cơ sở: với n=3, nhận thấy α αk−3 và fk > αk−2. Vậy, fk+1 = fk + fk−1 > αk−2 + αk−3 = αk−1. Suy ra P(k+1). ■ Lamé’s Theorem Định lý: a,bN, a≥b>0, số bước của thuật toán Euclid tìm ước số chung lớn nhất gcd(a,b) ≤ 5k, trong đó k = log10 b+1 là số các chữ số thập phân của b. Như vậy thuật toán Euclid là tuyến tính với số các chữ số của b. Chứng minh: Sử dụng dãy Fibinacci! Xem 2 trang tiếp theo. Gabriel Lamé 1795-1870 Proof of Lamé’s Theorem Xét dãy các phép chia sử dụng trong thuật toán Euclid: r0 = r1q1 + r2 with 0 ≤ r2 r2 > … > rn, mỗi thương qi ≡ ri−1/ri ≥ 1. Vì rn−1 = rnqn và rn−1 > rn, qn ≥ 2. Nên ta có các quan hệ sau giữa r và f: rn ≥ 1 = f2 rn−1 ≥ 2rn ≥ 2f2 = f3 rn−2 ≥ rn−1 + rn ≥ f2 + f3 = f4 … r2 ≥ r3 + r4 ≥ fn−1 + fn−2 = fn b = r1 ≥ r2 + r3 ≥ fn + fn−1 = fn+1. Vậy, nếu n>2 phép chia được sử dụng, thì b ≥ fn+1 > αn−1. Do đó, log10 b > log10(αn−1) = (n−1)log10 α ≈ (n−1)0.208 > (n−1)/5. Nếu b có k chữ số thập phân, thì log10 b b N) {Returns bn mod m.} if n=0 then return 1 else return (b·mpower(b,n−1,m)) mod m Nhận thấy thuật toán dùng Θ(n) bước! Thuật toán lũy thừa #2 Sử dụng công thức b2k = bk·2 = (bk)2. procedure mpower(b,n,m) {same signature} if n=0 then return 1 else if 2|n then return mpower(b,n/2,m)2 mod m else return (mpower(b,n−1,m)·b) mod m Độ phức tạp thời gian là bao nhiêu? Θ(log n) steps Phương án khác một chút A Slight Variation Gần giống nhưng dùng Θ(n) thời gian! procedure mpower(b,n,m) {same signature} if n=0 then return 1 else if 2|n then return (mpower(b,n/2,m)· mpower(b,n/2,m)) mod m else return (mpower(b,n−1,m)·b) mod m The number of recursive calls made is critical! ầ Thuật toán Euclide đệ qui Recursive Euclid’s Algorithm procedure gcd(a,bN) if a = 0 then return b else return gcd(b mod a, a) Nhận thấy thuật toán đệ qui thường đơn giản hưn thuật toán lặp… Tuy nhiên, chúng thường dùng nhiều ngăn xếp hơn, nếu chương trình dịch của chúng ta không đủ thông minh. Tìm kiếm tuyến tính đệ qui Recursive Linear Search Nhận thấy không có cải tiến thực sự khi sử dụng đệ qui ở đây so với vòng lặp for loc := i to j… procedure search(a: series; i, j: integer; x: item to be found) {Find x in series a at a location ≥i and 1, theo giả thiết qui nạp mạnh, fibonacci(n−1) và fibonacci(n−2) thực hiện fn−1 và fn−1−1 phép cộng tương ứng, và fibonacci(n) cộng thêm 1 nữa, tổng cộng là fn−1+ fn−1−1+1 = fn+fn−1+1 = fn+1+1. ■ Thuật toán hiệu quả hơn A more efficient algorithm procedure findFib(a,b,m,n) {Given a=fm−1, b=fm, and m≤n, return fn} if m=n return b return findFib(b, a+b, m+1, n) procedure fastFib(n) {Find fn in Θ(n) steps.} if n=0 return 0 return findFib(0,1,1,n) Sắp xếp trộn Sắp xếp trộn đệ qui Recursive Merge Sort procedure sort(L = 1,…, n) if n>1 then m := n/2 {this is rough ½-way point} L := merge(sort(1,…, m), sort(m+1,…, n)) return L Thuật toán trộn (trang tiếp) dùng Θ(n) bước, và sắp xếp trộn dùng Θ(n log n). Phương pháp trộn đệ qui Recursive Merge Method procedure merge(A,B: sorted lists) {Given two sorted lists A=(a1,…,a|A|), B=(b1,…,b|B|), return a sorted list of all.} if A = () return B {If A is empty, it’s B.} if B = () return A {If B is empty, it’s A.} if a1<b1 return (a1,merge((a2,…a|A|),B)) return (b1,merge(A,(b2,…,b|B|))) Chương trình trộn Merge Routine procedure merge(A, B: sorted lists) L = empty list i:=0, j:=0, k:=0 while i<|A|  j<|B| {|A| is length of A} if i=|A| then Lk := Bj; j := j + 1 else if j=|B| then Lk := Ai; i := i + 1 else if Ai < Bj then Lk := Ai; i := i + 1 else Lk := Bj; j := j + 1 k := k+1 return L Takes Θ(|A|+|B|) time Towers of Hanoi Towers of Hanoi Ở điểm này, chuyển đĩa lớn nhất. Tôi sẽ bắt đầu công việc. Thuật toán đệ qui Towers of Hanoi Time: T(1) = 1, T(n) = ≈ 2(2T(n-2)) ≈ 4(2T(n-3)) ≈ 2T(n-1) ≈ 4T(n-2) ≈ 8T(n-3) ≈ 2i T(n-i) ≈ 2n 1 + 2T(n-1)

Các file đính kèm theo tài liệu này:

  • pptbai_16_recursion_858.ppt
Tài liệu liên quan