Thiết kế và Phân tích giải thuật, Giải thuật đệ qui

1. Thiết kế thuật toán:

Giả sử chúng ta học lập trình java có một bài toán như thế này: quản lý điểm sinh viên toàn trường, phân loại học lực từng sinh viên.
Với một bài toán như vậy chúng ta cần phải hình dung được cụ thể đầu vào đầu ra của bài toán.

input: 

Thông tin cá nhân của mỗi sinh viên như họ tên, lớp, mã sinh viên, điểm các môn học...

output:

Tìm kiếm thông tin và in ra mỗi khi người dùng yêu cầu.
Up date thông tin sinh viên nếu cần.

Phân loại học lực sinh viên

Chúng ta giải quyết bài toán theo hướng phân tích tổng quát vấn đê dựa trên các dữ kiện và mục tiêu được đề ra, xét các công việc chính cần phải làm và bắt đầu đi dần vào giải quyết các phần một cách chi tiết cụ thể hơn.
Vậy chương trình viết ra phải đọc được các tệp, bản ghi rồi phải xử lý chúng vào cuối cùng phải lưu trữ. Trong mỗi thao tác xử lý đọc tệp thì lại có nhiều thao tác khác, xử lý tệp cũng vậy.. Giải thuật này gọi là chia để trị và cách thiết kế theo kiểu top down là nền tảng cho lập trình hướng cấu trúc. Để phản ánh đúng bản chất của thiết kế theo kiểu top down ta sẽ thiết kế giải thuật tinh chỉnh từng bước:

Dùng ngôn ngữ đời thường diễn đạt bài toán cần giải quyết

Cụ thể các bước tương ứng với các công việc nhỏ hơn và hướng về phía ngôn ngũ lập trình các bạn đã chọn: java, c++, c#...
Thay thế các lời lẽ xử lý công việc bằng các câu lệnh, nó sẽ trộn lẫn ngôn ngữ đời thường với ngôn ngữ bạn chọn.( người ta gọi là giả ngôn ngữ hay giả mã, mình không nhớ tiếng anh nó là gì, như mình ở đây mình sẽ trộn ngôn ngũ pascal với đời thường)

Ví dụ: Tạo chương trình sắp xép dãy số n số nguyên theo thứ tự tăng dần:
Giải thuật chung cho bài này mình sẽ đề cập đến trong phần tìm kiếm và sắp xếp, ở đây mình chỉ áp dụng phương pháp tinh chỉnh để giải quyết bài toán này:

Chọn số nhỏ nhất đặt vào đầu dãy, và cứ thế đến hết dãy.
ĐỂ thực hiện các bước trên thì so sánh các số đứng cạnh nhau số nào nhỏ hơn thì đặt về sau
và mình định hướng chương trình theo Pascal, đc 1 chương trình với mã lẫn lộn: For i=1 to nXét từ ai đến an đổi ai với aj end
viết chương trình đầy đủ với mã pascal

2. Phân tích thuật toán:

Chủ yếu là về thời gian thực hiện giải thuật, bạn nào muốn tìm hiểu thêm có thể google nhé Thời gian thực hiện giải thuật quan trọng trong việc thiết kế giải thuật, các bạn nên tìm hiểu.

3 Giải Thuật Đệ Qui:

Khái niệm: nôm na cái khái niệm về 1 đối tượng đệ qui là nó bao gồm chính nó
cho bạn dễ hình dung khi bạn để hai cái gương đối diện nhau bạn sẽ thấy trong gương có một cái gương khác giống chính nó, rồi cứ lặp lại mãi.
Ví dụ n!=n*(n-1)!
trong n! lại có (n-1)! mà về cơ bản n và n-1 giống nhau về mọi mặt, chỉ có ở phương diện giá trị n-1 <n vậy trong đệ qui cũng vậy đối trượng trong đối tượng xét về khí cạnh nào đó nó sẽ nhỏ dần và cuối cùng dẫn đến trường hợp suy biến.
Hàm n! và dãy Fibonacci cũng thuộc dạng đệ qui.
Chú ý:

Bên cạnh lời giải đệ quy thì có các lời giải lặp khá hiệu quả.
Đệ qui và qui nạp toán học liên quan tới nhau .

Bài toán tháp hà nội: Có N đĩa sắp xép xuyên qua 1 cọc to dưới nhỏ trên, chuyển đĩa từ cọc A sang cọc C với điều kiện, mỗi lần chỉ chuyển 1 đĩa, và đĩa to không được đặt trên đĩa bé, có thể sử dụng một cọc trung gian B.(Bài toán này nổi tiếng lắm, dành cho người học lập trình, mà mình cũng chẳng hiểu sao tác giả không đặt tên là tháp của các nước khác mà lại là tháp hà nội)
Lời giả bài toán này theo định nghĩa đệ qui nếu mới là khá khó hiểu, nhưng tập trung cũng dễ hiểu
Đầu tiên ta xét các trường hợp đơn giản, mà các trường hợp này dẽ là các trường hợp suy biến của bài toán

Khi có 1 đĩa thì ta chỉ việc chuyển sang cột C
Khi có 2 đĩa chuyển 1 đĩa trên sang B, đĩa tiếp theo sang C và Cuối cùng chuyển đĩa từ cọc B sang cọc C
Khi n>2: Chuyển n-1 đĩa từ A sang B rồi chuyển đĩa thứ n sang C cuối cùng chuyển n-1 đĩa từ B sang C Để chuyển n-1 đĩa từ A sang B thì ta lấy C làm cọc trung gian, Chuyển n-2 đĩa từ A sang C và chuyển đĩa thứ n-1 từ A sang B Cứ tiếp tục đến trường hợp suy biến thì thôi.

Ta có thể viết hàmthủ tục với phương pháp đệ qui:
Procedure(thủ tục): HANOITOWER(n,A,B,C) (ý trong ngoặc là chuyển n đĩa từ A sang C với B là trugn gian
if n=1 then chuyển đĩa từ A sang C
else
call HANOITOWER(n-1,A,C,B) (chuyển n-1đĩa từ A sang B lấy C làm cột trung gian)
call HANOITOWER(1,A,B,C)
call HANOITOWER(n-1,B,A,C)
end
(khi gọi hàm HANOITOWER(n-1,A,C,B) thì bài toán sẽ được lặp lại với n=n-1. Đệ quy ở đây :

lời gọi chình nó nằm trong các hàm HANOITOWER(n-1,A,C,B)
n giảm dần qua mỗi lần gọi có nghĩ là kich thước hàm đang giảm dần)

Các bạn có thểm tham khảo thêm bài toán tám hậu đi tuần với giải thuật back tracking, giải thuật quay lui.
Bạn có thể tham khảo cách dùng đệ quy giải bài toán n! với ngôn ngữ C