Một số phương pháp thiết kế thuật giải

Nội dung của chương này là một số chiến lược thiết kế thuật giải như chia để trị,vét cạn, tham lam, quy hoạch động...
Nội dung trích xuất từ tài liệu:
Một số phương pháp thiết kế thuật giảiMột số phương pháp thiết kế thuật giảiNội dung của chương này là một số chiến lược thiết kế thuật giải như chia đ ể trị,vét cạn, tham lam, quy hoạch động... Mặc dù đó là các chiến lược tổng quát, tuynhiên mỗi phương pháp chỉ áp dụng cho những lớp bài toán phù hợp. Nội dung củachương, ngoài phần trình bày về các phương pháp còn có những ví dụ cụ thể, cảthuật giải và cài đặt, để người đọc có một cái nhìn chi tiết về việc từ thuật toánđến chương trình.8.1. Chia để trị (Divide and Conquer)Chia để trị là một tư tưởng rất phổ biến trong cuộc sống và được áp dụng rất hiệuquả trong Tin học. Tư tưởng cơ bản của phương pháp chia đ ể trị là chia một bàitoán lớn, khó giải thành các bài toán tương tự, có kích thước nhỏ h ơn và d ễgiải hơn sao cho ta có thể phối hợp kết quả của các bài toán con đó để có k ết qu ảcủa bài toán lớn.Rất nhiều thuật toán ta gặp ở chương trước đều mang tư tưởng chia để trị:thuật toán sắp xếp nhanh Quick sort, thuật toán sắp xếp trộn Merge sort, thuật toántìm kiếm nhị phân,… Chúng ta sẽ nghiên cứu bài toán Tháp Hà n ội, là m ột bài toánđiển hình được giải bằng phương pháp chia để trị.8.1.1. Bài toán Tháp Hà NộiCó N đĩa có đường kính khác nhau được đặt chồng lên nhau theo th ứ t ự gi ảm d ầncủa đường kính tính từ dưới lên. Có ba vị trí có th ể đặt các đĩa đánh s ố 1, 2, 3.Chồng đĩa ban đầu được đặt ở vị trí 1: 1 2 3Cần chuyển cả chồng đĩa từ vị trí 1 sang vị trí 2, theo những quy tắc sau:• Khi di chuyển một đĩa, phải đặt nó vào một trong ba vị trí đã cho.• Mỗi lần chỉ có thể chuyển một đĩa và phải là đĩa ở trên cùng.• Tại một vị trí, đĩa nào mới chuyển đến sẽ phải đặt lên trên cùng. Đĩa lớn h ơn không bao giờ được phép đặt lên trên đĩa nhỏ hơn (hay nói cách khác: một đĩa chỉ được đặt trên mặt đất hoặc đặt trên một đĩa lớn hơn)Bài toán này có nguồn gốc là một truy ền thuy ết c ủa Ấn đ ộ r ằng có m ột nhóm caotăng Ấn độ giáo được giao trọng trách chuyển dần 64 đĩa vàng gi ữa 3 c ọc kimcương theo các điều kiện đã nói ở phần trên. Khi nào hoàn tất công việc, t ức là khichuyển xong toàn bộ 64 đĩa từ vị trí ban đầu sang vị trí kết thúc thì cũng là th ờiđiểm tận thế.Chúng ta giải bài toán bằng cách chia bài toán chuyển N đĩa, t ừ v ị trí 1 sang v ị trí 2thành ba bài toán đơn giản hơn như sau: 1. Chuyển N-1 đĩa trên cùng từ vị trí 1 sang vị trí 3, dùng vị trí 2 làm trung gian. 2. Chuyển đĩa thứ N từ vị trí 1 sang vị trí 2. 3. Chuyển N-1 đĩa từ vị trí 3 sang vị trí 2, dùng vị trí 1 làm trung gian.Chú ý rằng bài toán 1 và 3 tương tự như bài toán ban đầu, chỉ khác là kích th ướcnhỏ hơn. Chúng cũng sẽ được giải bằng phương pháp “chia đ ể trị” gi ống nh ư bàitoán ban đầu. Dễ dàng kiểm tra là khi giải như vậy chúng vẫn thoả mãn các đi ềukiện. Bài toán 2 thì được giải rất đơn giản.Thuật toán được viết dưới dạng giả mã như sau:Procedure Hanoi;begin Move(n,1,2,3);end;Procedure Move(n,a,b,c);{chuyển n đĩa, từ vị trí a sang vị trí b, dùng vị trí c làm trung gian }begin if n=0 then exit; Move(n-1,a,c,b); writeln(Chuyển đĩa ,n, từ vị trí ,a, sang vi tri ,b); Move(n-1,c,b,a);end;Chúng ta hãy dừng lại một chút để phân tích độ phức t ạp tính toán. G ọi T(n) là s ốthao tác chuyển đĩa cần thiết để chuyển xong n đĩa. Theo thuật toán trên ta có: T(n) = T(n-1) + 1 + T(n-1).Bằng các phương pháp giải công thức truy hồi ta có được T(n) = 2 n-1. Áp dụng kếtquả này với giả thiết rằng mỗi cao tăng phải mất 1 giây để chuy ển xong một đĩatừ cọc này sang cọc kia, ta thấy thời gian để chuyển toàn bộ 64 đĩa vàng làT(64)=216-1=18446744073709551615 giây. Như vậy ngày tận thế (nếu có) theotruyền thuyết phải 600 tỉ năm nữa mới đến.Chúng ta sẽ phân tích một thuật toán nữa để thấy được sự hiệu quả của ph ươngpháp chia để trị. Bài toán được chọn để phân tích tiếp theo là bài toán nhân 2 s ốlớn.8.1.2. Bài toán nhân hai số lớnRất nhiều ứng dụng trong thực tế đòi hỏi phải xử lí các số rất lớn, n ằm ngoàikhoảng biểu diễn của các kiểu cơ sở của ngôn ngữ lập trình (ch ẳng h ạn vi ệc tìmcác số nguyên tố rất lớn trong mã hoá RSA). Để giải quy ết các yêu c ầu đó, chúngta phải xây dựng các kiểu số rất lớn và xây dựng các phép toán t ương ứng. Trongphần này ta chỉ xét phép toán nhân đối với hai số rất lớn. Gi ả thi ết c ả hai đ ều có nchữ số và được biểu diễn bằng mảng. Bài toán nhân 2 số lớn phát biểu như sau:Input. A,B là 2 số nguyên có n chữ số: A=A1A2….An và B=B1B2….Bn.Output. C=A.BThuật toán tự nhiên (brute-force) của bài toán nhân 2 số lớn là giải thuật nhân tayta vẫn thực hiện: lần lượt nhân từng chữ số của số thứ hai với số thứ nh ất, dịchkết quả theo vị trí và cộng các kết quả trung gian lại.Chẳng hạn để nhân A=1981 và B=1234 ta tiến hành như sau: 1981× 1234------- 7924+ 5943 39621981-------2444554Thuật toán nhân 2 số lớn kiểu ...