Giáo trình Cấu trúc dữ liệu và giải thuật

THIẾT KẾ VÀ PHÂN TÍCH GIẢI THUẬT

Từ bài toán đến chương trình

2.1.1 Mô - đun hoá và việc giải quyết bài toán

Các bài toán trên máy tính điện tử ngày càng đa dạng và phức tạp, đòi hỏi các giải thuật và chương trình ngày càng lớn và khó khăn hơn trong việc thiết lập và nghiên cứu.

Để giải quyết bài toán lớn một cách hiệu quả, chúng ta nên chia nó thành các bài toán nhỏ hơn Cụ thể, bài toán chính có thể được phân chia thành các mô-đun con, và tiếp tục chia nhỏ từng mô-đun cho đến khi đạt được các phần việc cơ bản mà ta đã biết cách giải quyết Nhờ đó, tổ chức lời giải sẽ được thể hiện theo một cấu trúc phân cấp rõ ràng.

Chiến thuật giải quyết bài toán theo tinh thần như vậy chính là chiến thuật

Chiến thuật "chia để trị" được thể hiện qua phương pháp thiết kế "đỉnh- xuống" (top-down design), nơi người ta phân tích tổng quát vấn đề từ dữ kiện và mục tiêu đã đặt ra Phương pháp này bắt đầu từ những công việc chủ yếu trước khi đi sâu vào các phần cụ thể một cách chi tiết Ví dụ, khi nhận được yêu cầu từ chủ tịch hội đồng xét cấp học bổng, chúng ta sẽ áp dụng cách thiết kế từ khái quát đến chi tiết để giải quyết vấn đề hiệu quả hơn.

Sử dụng máy tính điện tử để quản lý và bảo trì hồ sơ học bổng cho sinh viên được tài trợ, đồng thời cần định kỳ lập báo cáo tổng kết để gửi lên bộ.

Để giải quyết bài toán, trước tiên cần hình dung rõ ràng về đầu vào và đầu ra Ta có thể xem xét một tập hồ sơ, hay còn gọi là tệp file, chứa các bản ghi thông tin liên quan đến học bổng của sinh viên.

Hệ thống quản lý học bổng cần xử lý các tệp thông tin bao gồm số hiệu sinh viên, điểm trung bình theo học kỳ, điểm đạo đức và khoản tiền tài trợ Chương trình này phải hỗ trợ người dùng trong việc đáp ứng các yêu cầu liên quan đến quản lý học bổng một cách hiệu quả.

1 Tìm lại và hiển thị được bản ghi của bất kỳ sinh viên nào tại thiết bị cuối (terminal) của người dùng.

2 Cập nhập (update) được bản ghi của một sinh viên cho trước bằng cách thay đổi điểm trung bình, điểm đạo đức, khoản tiền tài trợ, nếu cần.

3 In bản tổng kết chứa những thông tin hiện thời ( đã được cập nhập mỗi khi có thay đổi) gồm số liệu, điểm trung bình, điểm đạo đức, khoản tiền tài trợ.

Xuất phát từ những nhận định nêu trên, giải thuật xử lý sẽ phải giải quyết ba nhiệm vụ chính như sau:

1 Những thông tin về sinh viên được học bổng, lưu trữ trên đĩa phải được đọc vào bộ nhớ trong để có thể xử lý ( ta gọi là nhiệm vụ “đọc tệp”).

2 Xử lý các thông tin này để tạo ra kết quả mong muốn (nhiệm vụ ”xử lý tệp”).

3 Sao chép những thông tin đã được cập nhập vào tệp trên đĩa để lưu trữ cho việc xử lý sau này (nhiệm vụ ”ghi tệp”)

Có thể hình dung, cách thiết kế này theo sơ đồ cấu trúc ở hình 2.2.

Các nhiệm vụ ở mức đầu thường phức tạp và cần được chia thành các nhiệm vụ con Ví dụ, nhiệm vụ "xử lý tệp" có thể được phân chia thành ba phần, tương ứng với ba yêu cầu chính đã được đề cập.

1) Tìm lại bản ghi của một sinh viên cho trước

2) Cập nhập thông tin trong bản ghi sinh viên

3) In bản tổng kết những thông tin về các sinh viên được học bổng.

Những nhiệm vụ con này cũng có thể được chia thành những nhiệm vụ nhỏ hơn Có thể hình dung theo sơ đồ cấu trúc như sau:

Tìm bản ghi Cập nhật bản ghi In bản tổng

Tìm kiếm Hiển thị bản ghi Tìm kiếm Cập nhật

Thiết kế giải thuật theo kiểu top-down giúp định hướng rõ ràng trong việc giải quyết bài toán, tránh việc sa đà vào các chi tiết không cần thiết Phương pháp này cũng là nền tảng cho lập trình có cấu trúc, tạo điều kiện thuận lợi cho việc phát triển và bảo trì mã nguồn.

Trong các bài toán lớn, việc giải quyết thường cần sự hợp tác của nhiều người Phương pháp mô-đun hóa giúp tách bài toán thành các phần độc lập, cho phép các nhóm làm việc mà không ảnh hưởng đến nhau Nhờ vào việc xây dựng chương trình dựa trên các giải thuật mô-đun, việc tìm hiểu, sửa chữa và chỉnh lý trở nên dễ dàng hơn.

Việc chia nhỏ bài toán thành các bài toán con không hề đơn giản, và đôi khi quá trình phân tích cũng như thiết kế giải thuật có thể tốn nhiều thời gian và công sức hơn cả việc lập trình.

2.1.2 Phương pháp tinh chỉnh từng bước

Tinh chỉnh từng bước là phương pháp thiết kế giải thuật gắn liền với lập trình

Nó phản ánh tinh thần của quá trình mô-đun hoá bài toán thiết kế kiểu top-down

Chương trình bắt đầu bằng việc trình bày giải thuật dưới dạng ngôn ngữ tự nhiên, phản ánh rõ ràng ý chính của công việc cần thực hiện Qua từng bước, các ý tưởng sẽ được chi tiết hóa dần, tương ứng với các công việc nhỏ hơn cần hoàn thành.

Các bước tinh chỉnh sẽ được thực hiện theo ngôn ngữ lập trình đã chọn Ở các bước sau, các mô tả công việc sẽ dần được thay thế bằng các câu lệnh của ngôn ngữ lập trình Trong các giai đoạn trung gian, thường sử dụng sự kết hợp giữa ngôn ngữ tự nhiên và ngôn ngữ lập trình, được gọi là giả ngôn ngữ.

Quá trình thiết kế giải thuật và phát triển chương trình bắt đầu từ ngôn ngữ tự nhiên, sau đó chuyển sang giả ngôn ngữ và cuối cùng là ngôn ngữ lập trình Điều này giúp người lập trình hiểu rõ từ bản chất của vấn đề đến cách thực hiện, đồng thời các chức năng cũng được thể hiện ngày càng chính xác với các câu lệnh trong ngôn ngữ lập trình đã chọn Trong suốt quá trình này, dữ liệu được tinh chế từ cấu trúc ban đầu đến dạng lưu trữ cụ thể.

Giả sử ta muốn lập một chương trình sắp xếp một dãy n số nguyên khác nhau theo thứ tự tăng dần.

Phân tích giải thuật

Khi xây dựng giải thuật và chương trình tương ứng, việc phân tích tính đúng đắn của giải thuật là rất quan trọng để đảm bảo nó giải quyết chính xác bài toán Thông thường, người ta cài đặt chương trình trên máy và thử nghiệm với các bộ dữ liệu, sau đó so sánh kết quả với kết quả đã biết Tuy nhiên, phương pháp này chỉ giúp phát hiện sai sót mà không đảm bảo tính đúng của giải thuật Ngoài ra, sử dụng công cụ toán học để chứng minh tính đúng đắn của giải thuật cũng là một công việc khó khăn và phức tạp.

Yêu cầu về tính đơn giản của giải thuật thường được đề cao, vì nó giúp dễ hiểu, dễ lập trình và dễ chỉnh sửa Tuy nhiên, giải thuật đơn giản không phải lúc nào cũng là giải pháp tốt nhất, vì có thể gây tốn kém thời gian và bộ nhớ Đối với những chương trình chỉ sử dụng một vài lần, tính đơn giản là quan trọng do công sức và thời gian đầu tư lớn Ngược lại, với các chương trình sử dụng nhiều lần, đặc biệt là khi xử lý dữ liệu lớn, tốc độ thực hiện và tiết kiệm bộ nhớ trở nên quan trọng hơn Tuy nhiên, việc cân bằng giữa yêu cầu về thời gian và bộ nhớ thường không dễ dàng đạt được.

Trong bài viết này, chúng ta sẽ tập trung vào việc phân tích thời gian thực hiện của giải thuật, một trong những tiêu chí quan trọng để đánh giá hiệu quả của giải thuật.

2.2.2 Phân tích thời gian thực hiện giải thuật

Trong giải quyết một bài toán, có nhiều giải thuật khác nhau có thể áp dụng Việc lựa chọn một giải thuật hiệu quả và nhanh chóng là điều cần thiết Tuy nhiên, để xác định được giải thuật nào nhanh hơn, cần có những tiêu chí và căn cứ rõ ràng để so sánh hiệu suất của chúng.

Thời gian thực hiện một giải thuật phụ thuộc vào nhiều yếu tố, trong đó kích thước dữ liệu đầu vào là yếu tố quan trọng nhất Ví dụ, thời gian sắp xếp một dãy số chịu ảnh hưởng bởi số lượng các số trong dãy Nếu ký hiệu n là số lượng này, thì thời gian thực hiện T của một giải thuật có thể được biểu diễn dưới dạng hàm của n: T(n).

Các kiểu lệnh, tốc độ xử lý của máy tính, ngôn ngữ lập trình và chương trình dịch ảnh hưởng đến thời gian thực hiện, nhưng không đồng đều trên mọi loại máy Do đó, không thể xác định T(n) dựa vào chúng, và T(n) không thể biểu diễn bằng đơn vị thời gian cụ thể Tuy nhiên, vẫn có thể so sánh tốc độ của các thuật toán Nếu thời gian thực hiện của một thuật toán là T1(n) = cn² và thuật toán khác là T2(n) = kn (với c và k là hằng số), thì khi n lớn, T2 sẽ nhanh hơn T1 Điều này cho thấy thời gian thực hiện T(n) tỷ lệ với n² hoặc n có thể giúp đánh giá tốc độ của thuật toán khi n lớn, trong khi với n nhỏ, T(n) không có ý nghĩa Cách đánh giá này dẫn đến khái niệm về "cấp độ lớn của thời gian thực hiện thuật toán" hay "độ phức tạp tính toán của thuật toán".

1) Độ phức tạp tính toán của giải thuật

Nếu thời gian thực hiện của một giải thuật được biểu diễn bằng T(n) = cn² (với c là hằng số), thì độ phức tạp tính toán của giải thuật này được xác định là cấp n² Điều này có nghĩa là mức độ lớn của thời gian thực hiện giải thuật tương ứng với n².

Hàm f(n) được xác định là O(g(n)) nếu tồn tại các hằng số c và n0 sao cho f(n) ≤ cg(n) khi n ≥ n0, nghĩa là f(n) bị chặn trên bởi một hằng số nhân với g(n) cho mọi giá trị n lớn hơn hoặc bằng n0 Các hàm này thường biểu thị độ phức tạp tính toán của thuật toán, với các dạng phổ biến như: log2n, n, nlog2n, n², n³, 2^n, n!, và n^n.

Sau đây là đồ thị và bảng giá trị của một số hàm đó

Các hàm như 2^n, n!, n^n được gọi là hàm loại mũ, và thuật toán có thời gian thực hiện thuộc loại hàm này thường rất chậm Ngược lại, các hàm như n^3, n^2, n log2 n, n, và log2 n được xem là hàm loại đa thức, và thuật toán có thời gian thực hiện thuộc loại đa thức thường được chấp nhận và hiệu quả hơn.

2) Các quy tắc xác định độ phức tạp tính toán của giải thuật

Xác định độ phức tạp tính toán của một thuật toán có thể dẫn đến những bài toán phức tạp Tuy nhiên, trong thực tế, một số thuật toán có thể được phân tích dễ dàng bằng các quy tắc đơn giản.

* Quy tắc tổng : Giả sử T1(n) và T 2 (n) là thời gian thực hiện của hai đoạn chương trình P1 và P 2 mà T 1 (n) = O(f(n)); T 2 (n) = O(g(n)) thì thời gian thực hiện

P 1 và P 2 tiếp theo sẽ là: T1(n) + T 2 (n) = O(max (f(n),g(n))

Trong một chương trình có ba bước thực hiện với thời gian tương ứng là O(n²), O(n³) và O(n log² n), thời gian thực hiện cho hai bước đầu tiên sẽ là O(max(n², n³)) = O(n³) Do đó, thời gian thực hiện tổng thể của chương trình sẽ là O(max(n³, n log² n)) = O(n³).

Một vài ứng dụng khác của quy tắc này đó là nếu g(n) ≤ f(n) với mọi n ≥ n0 thì O(f(n)+g(n)) cũng là O(f(n)) Chẳng hạn: O(n 4 +n 2 ) = O(n 4 ) và O(n + log2n) O(n)

* Quy tắc nhân: Giả sử T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1 và P2 mà T1(n) = O(f(n)); T2(n) = O(g(n)) thì thời gian thực hiện

P1 và P2 lồng nhau sẽ là: T1(n).T2(n) = O(f(n).g(n))

Ví dụ: Câu lệnh gán : x := x+1 có thời gian thực hiện bằng c (hằng số) nên được đánh giá là O(1)

Câu lệnh: for i:= 1 to n do x :=x+1;

Có thời gian thực hiện O(n.1) = O(n)

Câu lệnh : for i := 1 to n do for j := 1 to n do x :=x+1; có thời gian thực hiện được đánh giá là: O(n.n)=O(n 2 )

Cũng có thể thấy O(cf(n)) = O(f(n))

(phần chứng minh hai quy tắc trên xin dành cho độc giả)

Khi đánh giá thời gian thực hiện giải thuật, chúng ta cần chú ý đến các bước tương tự với phép toán tích cực (active operation), là những phép toán có thời gian thực hiện không ít hơn các phép toán khác Điều này có nghĩa là số lần thực hiện phép toán tích cực không được thấp hơn so với các phép toán khác, và không chỉ có một loại phép toán tích cực duy nhất.

Bây giờ ta xét tới một giải thuật cụ thể:

Giải thuật tính giá trị của e x theo công thức gần đúng: e x = 1 + x/1! +x 2 /2! + …+ x n /n! với x và n cho trước

{tính từng số hạng rồi cộng lại}

2 for i:=1 to n do begin p : =1; for j:= 1 to n do p:=p*x/j;

Ta có thể coi phép toán tích cực ở đây là phép: p := p*x/j

Ta thấy nó được thực hiện:

1 +2+…+ n = n(n+1)/2 lần Vậy thời gian thực hiện giải thuật này được đánh giá là T(n) = O(n 2 )

Ta có thể viết giải thuật theo một cách khác

Bây giờ thời gian thực hiện lại là: T(n) = O(n) Vì phép gán p:=p*x/i chỉ thực hiện n lần.

Thời gian thực hiện của thuật toán không chỉ phụ thuộc vào kích thước dữ liệu đầu vào mà còn bị ảnh hưởng bởi tình trạng của dữ liệu đó.

Khi sắp xếp một dãy số theo thứ tự tăng dần, việc phân tích thời gian thực hiện thuật toán cần xem xét cả các trường hợp khác nhau: khi dãy số đã được sắp xếp đúng, khi chưa sắp xếp hoặc khi sắp xếp ngược lại Đối với mọi dữ liệu đầu vào có kích thước n, ta cần xác định T(n) trong trường hợp thuận lợi nhất, trường hợp xấu nhất, và T(n) trung bình Tuy nhiên, việc xác định T(n) trung bình thường gặp khó khăn do cần sử dụng các công cụ toán học đặc biệt và có nhiều cách tiếp cận khác nhau Do đó, trong trường hợp khó xác định T(n) trung bình, người ta thường đánh giá thuật toán dựa trên giá trị xấu nhất của T(n) Thuật toán dưới đây sẽ minh họa rõ hơn về vấn đề này.

{cho vectơ V có n phần tử, giải thuật này thực hiện tìm trong V một phần tử có giá trị bằng X cho trước}

1 Found := false; {found là biến logic để báo hiệu việc ngừng tìm khi đã thấy} i :=1;

2 while i X[j+1] then begin temp := X[j];

Function Euclid (m, n : integer) :integer; var r : integer ; begin r := m mod n; (1) while r 0 do (2) begin m := n; (3) n :=r; (4) r := m mod n; (5) end;

10 Để tính giá trị của đa thức Pn(x) khi cho x có hai thuật giải:

Cách 1 Tính từng số hạng của đa thức rồi cộng lại.

Cách 2 Dùng phương pháp Horne

Để tính thời gian thực hiện của hai giải thuật, ta cần phân tích độ phức tạp của chúng Bên cạnh đó, để tìm đồng thời giá trị cực đại và cực tiểu của dãy n phần tử mà không sử dụng quá 3n/2 phép so sánh, ta có thể xây dựng một giải thuật hiệu quả, tối ưu hóa số phép so sánh cần thiết.

11 Cho mảng A chứa n- 1 số nguyên khác nhau trong khoảng từ [0, n-1], nghĩa là có một số nguyên trong khoảng trên không nằm trong A Tìm thuật giải với thời gian O(n) để tìm ra số này mà chỉ dùng thêm O(1) không gian nhớ ngoài mảng A.

12 Mảng 2 chiều Anxnmỗi phần tử là một bít 0 hoặc 1 Giả sử trong mọi dòng của A, tất cả các bít 1 đều đi trước tất cả các bít 0 trong hàng Viết giải thuật với thời gian O(n) để tìm ra dòng chứa nhiều bít 1 nhất.

ĐỆ QUY VÀ GIẢI THUẬT ĐỆ QUY

Khái niệm về đệ quy

Đệ quy là công cụ quan trọng trong khoa học máy tính và toán học, giúp giải quyết nhiều vấn đề phức tạp Trong khoa học máy tính, đệ quy được áp dụng trong lý thuyết, giải thuật và định nghĩa cú pháp của các ngôn ngữ lập trình như Pascal và C Ngoài ra, đệ quy cũng được sử dụng để giải quyết các vấn đề trong lý thuyết trò chơi và trong các giải thuật trên cấu trúc dữ liệu Trong toán học, đệ quy có vai trò quan trọng trong các bài toán tổ hợp và xác suất.

Một đối tượng hoặc vấn đề được coi là đệ quy khi nó chứa chính nó như một phần của cấu trúc hoặc khi nó được định nghĩa thông qua chính nó.

Trên truyền hình, đôi khi ta bắt gặp hình ảnh đệ quy, như khi phát thanh viên ngồi bên máy vô tuyến và hình ảnh của họ cũng xuất hiện trên màn hình Tương tự, trong toán học, các định nghĩa đệ quy cũng thường xuyên xuất hiện.

1) Số tự nhiên: a) 1 là một số tự nhiên. b) x là số tự nhiên nếu x-1 là số tự nhiên

2) Hàm n giai thừa: a) 0! =1 b) Nếu n > 0 thì n! = n(n-1)!

3.2 GIẢI THUẬT ĐỆ QUY VÀ CHƯƠNG TRÌNH CON ĐỆ QUY

Lời giải của bài toán T nếu được thực hiện thông qua lời giải của bài toán T' với cấu trúc tương tự, thì được gọi là lời giải đệ quy Giải thuật tương ứng với loại lời giải này được gọi là giải thuật đệ quy.

Thoạt nghe thì có vẻ hơi lạ, nhưng điểm mấu chốt cần lưu ý là: T‟ tuy có dạng giống như T, nhưng theo một nghĩa nào đó, nó phải “nhỏ” hơn T.

Một bài toán giải theo phương pháp đệ quy cần hai điều kiện thiết yếu để đảm bảo tính đệ quy và tránh tình trạng đệ quy vô hạn.

- Có thể biểu diễn bài toán cần giải thông qua bài toán cùng dạng, đơn giản hơn ( điều kiện tồn tại tính đệ quy)

- Có điều kiện dừng( để không bị gọi bất tận)

Tìm từ trong từ điển

Tìm từ trong từ điển nửa trước Tìm từ trong từ điển nửa sau

Hãy xét bài toán tìm một từ trong một quyển từ điển Có thể nêu giải thuật như sau:

If từ điển là một trang Then tìm từ trong trang này.

Mở từ điển vào trang “giữa”;

Xác định xem nửa nào của từ điển chứa từ cần tìm;

If từ đó nằm ở nửa trước của từ điển Then tìm từ đó trong nửa trước. Else tìm từ đó trong nửa sau.

Tất nhiên giải thuật trên mới chỉ được nêu dưới dạng thô, còn nhiều chỗ chưa cụ thể, chẳng hạn như:

- Tìm từ trong một trang thì làm thế nào?

- Thế nào là mở từ điển vào trang giữa?

- Làm thế nào để biết từ đó nằm ở nửa nào của từ điển? v.v

Trả lời rõ những câu hỏi trên không phải là khó, nhưng ta sẽ không sa vào các chi tiết này mà muốn tập trung vào việc xét.

Hình 3.1 Chiến thuật của lời giải: Có thể hình dung chiến thuật của tìm kiếm này một cách khái quát như hình 3.1.

Trong quá trình tách từ điển, có hai điểm quan trọng cần lưu ý: Thứ nhất, sau mỗi lần tách, nửa từ điển còn lại sẽ được tìm kiếm bằng chiến thuật tương tự như trước đó Thứ hai, có một trường hợp đặc biệt, gọi là trường hợp suy biến, xảy ra khi từ điển chỉ còn một trang Khi đó, việc tách đôi ngừng lại và bài toán trở nên đủ nhỏ để giải quyết trực tiếp, chẳng hạn bằng cách tìm tuần tự trên trang đó Chiến thuật này tương tự như phương pháp “chia để trị”, trong đó bài toán lớn được chia thành các bài toán nhỏ hơn và được giải quyết cho đến khi gặp trường hợp suy biến.

Bây giờ ta hãy thể hiện chiến thuật tìm kiếm này dưới dạng một thủ tục. Procedure SEARCH (dict, word)

{dict được coi là đầu mối để truy nhập được vào từ điển đang xét, word chỉ từ cần tìm}

1 if từ điểnchỉ còn một trang then tìm từ word trong một trang này.

2 Mở từ điển vào trang “giữa”

Xác định xem nửa nào của từ điển chứa từ trong word;

If word nằm ở nửa trước của từ điển Then call SEARCH (dict 1, word) Else call SEARCH (dict 2, word)

{dict 1, dict 2 là đầu mối để truy nhập được vào nửa trước và nửa sau của từ điển}

Thủ tục đệ quy là một phương pháp lập trình trong đó một thủ tục gọi chính nó, như ví dụ trong thủ tục SEARCH Mỗi lần gọi lại, kích thước bài toán sẽ giảm đi, ví dụ như kích thước từ điển giảm xuống còn một nửa Có trường hợp đặc biệt gọi là suy biến, khi từ điển chỉ còn một trang, lúc này bài toán sẽ được giải quyết theo cách khác và quá trình đệ quy sẽ kết thúc Nhiều ngôn ngữ lập trình cao cấp như ALGOL, PL/1, và PASCAL hỗ trợ việc viết thủ tục đệ quy Nếu thủ tục gọi chính nó, như SEARCH, thì được gọi là đệ quy trực tiếp; còn nếu thủ tục này gọi một thủ tục khác mà lại gọi về nó, thì gọi là đệ quy gián tiếp.

Thiết kế giải thuật đệ quy

3.3.1 Hàm N ! Định nghĩa đệ quy của n! như sau:

Giải thuật đệ quy được viết dưới dạng hàm:

1- if n=0 then FACTORIAL := 1 else FACTORIAL := n*FACTORIAL(n-1)

2- return Đối chiếu với 3 đặc điểm của thủ tục đệ quy ở trên ta thấy:

- Lời gọi tới chính nó ở đây nằm trong câu lệnh gán đứng sau else.

- Ở mỗi lần gọi đệ quy đến FACTORIAL, thì giá trị của n giảm đi 1, Ví dụ FACTORIAL(4) FACTORIAL(3) FACTORIAL(2)

3.3.2 Bài toán Tháp Hà Nội Đây là một bài toán mang tính chất một trò chơi, nội dung như sau:

Có một bộ đĩa với kích thước nhỏ dần, mỗi đĩa có lỗ ở giữa giống như đĩa hát Các đĩa này có thể được xếp chồng lên nhau qua một cọc, với đĩa lớn ở dưới và đĩa nhỏ ở trên, tạo thành một hình tháp đẹp mắt.

Hình 3.2 Chuyển chồng đĩa từ cọc A sang cọc khác, chẳng hạn sang cọc C theo những điều kiện:

1- Mỗi lần chỉ được chuyển một đĩa.

2- Không khi nào có tình huống đĩa to ở trên đĩa nhỏ (dù là tạm thời)

3- Được phép sử dụng một cọc trung gian, chẳng hạn cọc B dùng để đặt tạm đĩa. Để đi tới cách giải tổng quát, trước hết xét vài trường hợp đơn giản.

*Trường hợp một đĩa: Chuyển từ cọc A sang cọc C

*Trường hợp chuyển hai đĩa:

- Chuyển đĩa thứ nhất từ cọc A sang cọc B

- Chuyển đĩa thứ hai từ cọc A sang cọc C

- Chuyển đĩa thứ nhất từ cọc B sang cọc C

Trong trường hợp có n đĩa (n>2), nếu xem (n-1) đĩa ở trên như là đĩa thứ nhất, ta có thể áp dụng quy trình xử lý tương tự như khi chỉ có 2 đĩa.

- Chuyển (n-1) đĩa trên từ A sang B

- Chuyển đĩa thứ n từ A sang C

Lược đồ thể hiện 3 bước này như sau:

Bài toán "tháp Hà Nội" tổng quát với n đĩa có thể được giảm bớt thành bài toán tương tự với kích thước nhỏ hơn Cụ thể, để chuyển n đĩa từ cọc A sang cọc C, ta cần thực hiện bước chuyển (n-1) đĩa từ cọc A sang cọc B trước.

- Chuyển (n-2) đĩa từ cọc A sang cọc C

- Chuyển 1 đĩa từ cọc A sang cọc B

- Chuyển (n-2) đĩa từ cọc C sang cọc B

Và cứ như thế cho tới khi trường hợp suy biến xảy ra, đó là trường hợp ứng với bài toán chuyển 1 đĩa thôi.

Các đặc điểm của đệ quy trong giải thuật đã được xác định, cho phép chúng ta xây dựng giải thuật đệ quy cho bài toán “Tháp Hà Nội”.

1- if n=1 then chuyển đĩa từ A sang C

2- else begin call HANOI (n-1, A, C, B); call HANOI (1, A, B, C); call HANOI (n-1, B, A, C); end

3-return 3.3.3 Bài toán 8 quân hậu và giải thuật quay lui

Bàn cờ quốc tế là một bảng hình vuông với 8 hàng và 8 cột Quân hậu có khả năng ăn bất kỳ quân nào nằm trên cùng hàng, cột hoặc đường chéo Bài toán đặt ra là sắp xếp 8 quân hậu trên bàn cờ sao cho không quân nào có thể ăn quân nào, tức là mỗi hàng, mỗi cột và mỗi đường chéo chỉ được phép có một quân hậu.

Thay vì xem xét từng trường hợp của 8 quân hậu trên bàn cờ, chúng ta có thể áp dụng phương pháp "thử từng bước" để tìm ra tất cả các cách sắp xếp mà không có quân hậu nào có thể ăn nhau Phương pháp này không chỉ thực tế mà còn hiệu quả, giúp xác định được tổng cộng 92 cách sắp xếp hợp lệ.

Phương pháp giải bài toán 8 quân hậu dựa trên nguyên tắc thử và sai, trong đó mỗi bước đi tới lời giải đều được thử nghiệm Nếu một lựa chọn được chấp nhận, các thông tin liên quan sẽ được ghi nhớ để tiếp tục bước thử tiếp theo Ngược lại, nếu không có lựa chọn nào phù hợp, ta sẽ quay lại bước trước, xóa bỏ các ghi nhớ và tiếp tục thử với các lựa chọn còn lại Hành động này được gọi là quay lui, và các giải thuật áp dụng phương pháp này được gọi là giải thuật quay lui Đối với bài toán 8 quân hậu, mỗi cột chỉ có thể chứa một quân hậu, do đó việc chọn quân hậu thứ j trong cột j cần đảm bảo không cùng hàng hoặc cùng đường chéo với các quân hậu đã được đặt trước đó Để tìm ra các lời giải, ta cần thử tất cả các vị trí của quân hậu đầu tiên ở cột 1, và với mỗi vị trí như vậy, ta sẽ giải quyết bài toán 7 quân hậu cho phần còn lại của bàn cờ, thể hiện tính chất đệ quy của bài toán.

1 Khởi phát cho việc chọn vị trí cho quân hậu thứ j

2 repeat thực hiện phép chọn tiếp theo; if an toàn then begin đặt quân hậu; if j 0 chỉ thị đứng sau else

Sẽ được thực hiện Vậy với n = k+1 thì giá trị cho ra là

(k+1)* FACTORIAL(k) nghĩa là (k+1)*k(k-1)*…*2*1 và việc chứng minh đã hoàn tất

2 Đánh giá giải thuật tháp HANOI

Khi có n đĩa, số lần di chuyển đĩa trong thuật toán này sẽ được tính toán dựa trên quy tắc di chuyển tích cực.

Giả sử ta gọi Moves(n) là số đó, ta có Moves (1) = 1.

Khi n >1 thì Moves (n) không thể tính trực tiếp như vậy nhưng ta biết rằng : nếu biết Moves (n-1) thì ta sẽ tính được Moves(n):

Moves(n) = Moves(n-1) + Moves(1) + Moves(n-1) (dựa vào giải thuật )

Vậy ta xác định được mối quan hệ truy hồi của cách tính:

Moves (n) = 2* Moves (n-1) +1 nếu n>1 ví dụ: Moves (3) =2* Moves(2) +1

Tuy nhiên công thức truy hồi này không cho ta tính trực tiếp theo n được Nếu để ý ta thấy: Moves(1) = 1= 2 1 -1

Vậy phải chăng: Moves (n) = 2 n -1 với n là số tự nhiên bất kỳ?

Ta sẽ chứng minh công thức tính này đúng bằng qui nạp toán học

Với n= 1, Moves (1) = 2 1 -1=1 công thức đã đúng.

Giả sử công thức đã đúng với n=k, nghĩa là:

Với n = k+1 theo công thức tính truy hồi

Công thức đã được xác nhận đúng với k+1, do đó nó cũng đúng với mọi giá trị n Một công cụ phổ biến trong việc phân tích giải thuật đệ quy là cây đệ quy, giúp đánh giá sự chiếm dụng bộ nhớ và thời gian chạy của giải thuật.

Sự chiếm dụng bộ nhớ trong thuật toán đệ quy tỷ lệ thuận với cấp độ đệ quy, tức là tỷ lệ với chiều sâu của cây đệ quy, và không phụ thuộc vào số lượng nút có trong cây đó.

Thời gian chạy của giải thuật thường được xác định bằng phương pháp đếm số tác vụ cần thực hiện trên cây đệ quy Chẳng hạn, trong bài toán tháp Hà Nội, cây đệ quy sẽ có cấu trúc nhất định để tính toán số bước cần thiết.

Sự chiếm dụng bộ nhớ: Tỉ lệ với chiều sâu (cao) của cây: O(n), với n là số đĩa cần chuyển.

Sự chiếm dụng thời gian: Tỉ lệ với số lần thực hiện t ác vụ chuyển một đĩa:

Tác vụ chuyển một đĩa

Bài tập

3.1 Xét định nghĩa đệ quy:

Hàm này được gọi là hàm Ackermann Nó có đặc điểm là giá trị của nó tăng rất nhanh, ứng với giá trị nguyên của m và n

- Viết một thủ tục đệ quy thực hiện tính giá trị hàm này.

3.2 Giải thuật tính ước số chung lớn nhất của hai số nguyên dương p và q (p > q) được mô tả như sau:

Gọi r là số dư trong phép chia p cho q

- Nếu r= 0 thì q là ướcsố chung lớn nhất

Để xây dựng hàm USCLN (q, p) theo định nghĩa đệ quy, ta thực hiện như sau: nếu r khác 0, gán p bằng giá trị của q, gán q bằng giá trị của r và lặp lại quá trình Giải thuật đệ quy và giải thuật lặp sẽ thể hiện hàm này bằng cách sử dụng các điều kiện tương ứng để tính USCLN Đặc điểm của giải thuật đệ quy trong trường hợp này là sự lặp lại của các bước tính toán cho đến khi đạt được điều kiện dừng Để xử lý trường hợp q lớn hơn p, trong giải thuật cần phải hoán đổi giá trị của q và p trước khi thực hiện các bước tiếp theo.

3.3 Hàm C(n,k) với n, k là các giá trị nguyên không âm và k  n , được định nghĩa:

C(n, k) = C(n-1, k-1)+C(n-1, k) nếu 0 < k < n a) Viết một thủ tục đệ quy thực hiện tính giá trị C(n, k) khi biết n, k b) Chứng minh rằng thủ tục này cho ra đúng giá trị

3.4 Hãy nêu rõ các bước thực hiện khi có lời gọi call HANOI (4, A, B, C)

3.5 Viết một thủ tục đệ quy thực hiện in ngược một dòng ký tự cho trước, ví dụ cho dòng “PASCAL” thì in ra “LACSAP”

3.6 Viết một thủ tục đệ quy nhằm in ra tất cả các hoán vị của n phần tử của một dãy số a= {a 1 , a 2 ,…,an} Ví dụ n=3, a1=1, a2=2, a3=3 thì in ra: 1 2 3; 1 3 2; 2 1 3; 2 3 1; 3 1 2; 3 2 1;

(Gợi ý Hãy để ý nhận xét: 123 132 231

) , ker( n m khi n m Ac m Ac n khi m

3.7 Viết giải thuật đệ quy xác định chiều dài của một xâu kí tự

3.8 Viết giải thuật đệ quy đổi một số nguyên dương n từ hệ thập phân sang hệ đếm cơ số a.

3.9 Viết giải thuật đệ quy tìm số lớn nhất của một dãy số: a1, a2, , an

3.10 Viết giải thuật đệ quy kiểm tra một xâu kí tự có phải là xâu xuôi ngược (palindrome) không

3.11 Hãy viết giải thuật đệ quy tính tổng n số nguyên dương đầu tiên

3.12 Hãy viết giải thuật đệ quy tính tổng n số nguyên dương lẻ đầu tiên

3.13 Hãy viết lời giải và giải thuật đệ quy tính wi trong đó i là một số nguyên không âm và wi biểu diễn phép ghép i bản sao của xâu w.

3.14 Trên bàn cờ 8x8 hãy viết giải thuật đi con mã 64 nước sao cho mỗi ô chỉ đi qua một lần (xuất phát từ một ô bất kỳ) Ví dụ một lời giải:

3.15 Viết giải thuật đệ quy:

- Liệt kê các xâu nhi phân có độ dài n.

- Liệt kê các tập con m phần tử của tập n phần tử

- Liệt kê hoán vị của n phần tử.

MẢNG VÀ DANH SÁCH

DANH SÁCH MÓC NỐI

CÂY

SẮP XẾP

TÌM KIẾM