Bài toán đệ quy
Để xây dựng giải thuật giải một bài toán có tính đệ quy bằng phương pháp đệ quy ta cần thực hiện tuần tự 3 nội dung sau : Thông số hóa bài toán . Tìm các trường hợp neo cùng giải thuật giải tương ứng . Tìm giải ...
Để xây dựng giải thuật giải một bài toán có tính đệ quy bằng phương pháp đệ quy ta cần thực hiện tuần tự 3 nội dung sau :
- Thông số hóa bài toán .
- Tìm các trường hợp neo cùng giải thuật giải tương ứng .
- Tìm giải thuật giải trong trường hợp tổng quát bằng phân rã bài toán theo kiểu đệ quy.
Thông số hoá bài toán.
Tổng quát hóa bài toán cụ thể cần giải thành bài toán tổng quát (một họ các bài toán chứa bài toán cần giải ),tìm ra các thông số cho bài toán tổng quát đặc biệt là nhóm các thông số biểu thị kích thước của bài toán - các thông số điều khiển ( các thông số mà độ lớn của chúng đặc trưng cho độ phức tạp của bài toán , và giảm đi qua mỗi lần gọi đệ qui ) .
n trong hàm FAC(n) ; a , b trong hàm USCLN(a,b) .
Phát hiện các trường hợp suy biến (neo) và tìm giải thuật cho các trường hợp này.
Đây là các trường hợp suy biến của bài toán tổng quát , là các trương hợp tương ứng với các gía trị biên của các biến điều khiển (trường hợp kích thước bài toán nhỏ nhất), mà giải thuật giải không đệ qui (thường rất đơn giản).
FAC(1) =1 , USCLN(a,0) = a , SM(a[x:x] ≡∅ ,TSUM(a[m:m]) = a[m]
Phân rã bài toán tổng quát theo phương thức đệ quy.
Tìm phương án (giải thuật ) giải bài toán trong trường hợp tổng quát bằng cách phân chia nó thành các thành phần mà hoặc có giải thuật không đệ quy hoặc là bài toán trên nhưng có kích thước nhỏ hơn.
FAC(n) = n * FAC(n -1) .
Tmax(a[1:n]) = max(Tmax(a[1:(n-1)]) , a[n] )
Bài toán tháp Hà Nội .
Truyền thuyết kể rằng : Một nhà toán học Pháp sang thăm Đông Dương đến một ngôi chùa cổ ở Hà Nội thấy các vị sư đang chuyển một chồng đĩa qúy gồm 64 đĩa với kích
thước khác nhau từ cột A sang cột C theo cách :
- Mỗi lần chỉ chuyển 1 đĩa .
- Khi chuyển có thể dùng cột trung gian B .
- Trong suốt qúa trình chuyển các chồng đĩa ở các cột luôn được xếp đúng (đĩa có kích thước bé được đặt trên đĩa có kích thước lớn ) .
Khi được hỏi các vị sư cho biết khi chuyển xong chồng đĩa thì đến ngày tận thế !.
Như sẽ chỉ ra sau này với chồng gồm n đĩa cần 2 n - 1 lần chuyển cơ bản (chuyển 1
đĩa ).
Giả sử thời gian để chuyển 1 đỉa là t giây thì thời gian để chuyển xong chồng 64 đĩa sẽ là :
T = ( 2 64 − ) * t S = 1.84* 1019 *t S
Với t = 1/100 s thì T = 5.8*109 năm = 5.8 tỷ năm .
Ta có thể tìm thấy giải thuật (dãy các thao tác cơ bản ) cho bài toán một cách dễ dàng ứng với trường hợp chồng đĩa gồm 0, 1, 2, 3 đĩa . Với chồng 4 đĩa giải thuật bài
toán đã trở nên phức tạp . Tuy nhiên giải thuật của bài toán lại được tìm thấy rất dễ dàng nhanh chóng khi ta khái quát số đĩa là n bất kỳ và nhìn bài toán bằng quan niệm đệ quy .
Thông số hóa bài toán .
Xét bài toán ở mức tổng quát nhất : chuyển n (n>=0) đĩa từ cột X sang cột Z
lấy cột Y làm trung gian
Ta gọi giải thuật giải bài toán ở mức tổng quát là thủ tục THN(n ,X ,Y,Z) chứa 4 thông số n,X,Y,Z ; n thuộc tập số tự nhiên N (kiểu nguyên không dấu ); X ,Y,Z thuộc tập các ký tự (kiểu ký tự ).
Bài toán cổ ở trên sẻ được thực hiện bằng lời gọi THN(64,A,B,C) .
Dễ thấy rằng : trong 4 thông số của bài toán thì thông số n là thông số quyết định độ phức tạp của bài toán ( n càng lớn thì số thao tác chuyển đỉa càng nhiều và thứ tự thực hiện chúng càng khó hình dung ) , n là thông số điều khiển .
Trường hợp suy biến và cách giải .
Với n =1 bài toán tổng quát suy biến thành bài toán đơn giản THN (1,X,Y,Z) : tìm
dãy thao tác để chuyển chồng 1 đĩa từ cột X sang cột Z lấy cột Y làm trung gian . Giải thuật giải bài toán THN (1,X,Y,Z) là thực hiện chỉ 1 thao tác cơ bản : Chuyển 1 đĩa từ
X sang Z ( ký hiệu là Move (X , Z) ) .
THN(1,X,Y,Z) ≡ { Move( X, Z ) }
Chú ý : Hoàn toàn tương tự ta cũng có thể quan niện trường hợp suy biến là trường hợp n= 0 tương ứng với bài toán THN(0,X,Y,Z) : chuyển 0 đĩa từ X sang Z lấy Y làm
trung gian mà giải thuật tương ứng là không làm gì cả ( thực hiện thao tác rỗng ) .
THN(0,X,Y,Z) ≡ {
- 1 Các chỉ tiêu phản ánh chất lượng tín dụng trung dài hạn ngân hàng
- 2 Mục tiêu, chức năng và nguyên tắc hoạt động của WTO
- 3 Lợi thế tuyệt đối
- 4 Nội dung của truyền thuyết
- 5 Xã hội hóa
- 6 Vũng Tàu
- 7 Cạnh tranh không hoàn hảo
- 8 Giới thiệu về thẻ tín dụng
- 9 Nguồn vốn đầu tư của doanh nghiệp bảo hiểm nhân thọ
- 10 Nhóm nhân tố ảnh hưởng đến khả năng cạnh tranh của ngành dệt may Việt Nam