Bài tập thuật toán nhánh cận có lời giải năm 2024
Trong cuộc sống, chúng ta đôi khi bắt gặp những hình ảnh về một vật mà chứa bên trong nó là một vật khác giống hệt nó, như búp bê Matryoska, cửa sổ OBS khi bạn cố dùng nó để quay màn hình của chính nó, sách giáo khoa Toán lớp 3 cũ, link này, … Tương tự như vậy, trong khoa học máy tính và lập trình, chúng ta xây dựng khái niệm về đệ quy. Show Đệ quy và giải thuật đệ quyKhái niệmTa gọi một đối tượng là đệ quy (recursion) nếu nó được định nghĩa qua chính nó hoặc một đối tượng cùng dạng với chính nó bằng quy nạp. Ví dụ:
Nếu một bài toán $P$ có lời giải được thực hiện bằng một bài toán con $P'$ có dạng giống $P$ thì đó là một giải thuật đệ quy. Ở đây, $P'$ cần là một bài toán đơn giản hơn $P$ (có kích cỡ dữ liệu nhỏ hơn, hoặc độ phức tạp nhỏ hơn, …), và đương nhiên không cần đến $P$ để giải nó. Về cơ bản thì ta có thể gọi một hàm là đệ quy nếu hàm đó tự gọi chính nó, với các biến đầu vào có thể khác. Một bài toán đệ quy có lời giải gồm 2 phần:
Nếu ta đem so sánh với con Matryoska, thì trường hợp cơ sở là con bé nhất ở trong cùng, còn đệ quy chính là thực hiện việc mở một con to liên tục đến lúc nào không thể mở được nữa. Lý thuyết suông thì quá khó hiểu, hãy cùng xem một số ví dụ: Tính giai thừaBài toán: Cho số tự nhiên $n$ ($n \leq 15$). Tính $n!$ Phân tích: Ở phần trên, chúng ta đã tìm được công thức đệ quy của bài toán này: $n! = (n - 1)! \times n$. Khi lập trình đệ quy, cơ bản thuật toán sẽ hoạt động như sau với $n = 2$: để tính $2!$, chúng ta phải tính nó qua $1!$; để tính $1!$ chúng ta phải tính $0!$. Lúc này, ta có hai lựa chọn:
Lựa chọn thứ nhất có vẻ không khả thi, phần vì $(-1)!$ không xác định, mặt khác nếu thay tiếp thì chúng ta cũng chẳng biết dừng ở đâu cả. Với $0! = 1$, ta có thể thay vào để tính $1!$ rồi. Có $1!$ ta lại thay nó vào tiếp để tính $2!$, và chúng ta có thứ chúng ta cần. Phân tích thì dài dòng vậy thôi, còn cài đặt thì rất đơn giản:
Nếu bạn chưa quen với cú pháp đệ quy như vậy thì có thể hiểu hàm trên tương đương với hàm
2 trong đoạn code sau với $n = 2$:
Tính số FibonacciDãy Fibonacci là dãy số được định nghĩa theo công thức truy hồi sau:$f_n = \begin{cases} 0 & \text{với } n = 0\\ 1 & \text{với } n = 1\\ f_{n - 2} + f_{n - 1} & \text{với } n > 1 \end{cases}$Văn vẻ hơn thì trong dãy này, mỗi số hạng bằng tổng của hai số hạng liền trước nó. Các giá trị $f_0$, $f_1$ có thể khác một chút tuỳ tài liệu. Bài toán: Tìm số Fibonacci thứ $n$ ($n \leq 20$). Dựa vào công thức truy hồi đã cho và lập luận kiểu "để tính $f$ này thì ta cần có $f$ kia" như trên, chúng ta có thể cài đặt như sau:
Cần chú ý rằng ở chương trình này cần có tới 2 trường hợp cơ sở, vì đó cũng là hai trường hợp không thể áp dụng công thức truy hồi. Mở rộng: Hãy thử sử dụng phương pháp này để cài đặt một chương trình đệ quy tính ƯCLN dựa vào công thức ở ví dụ phía trên. Đương nhiên, không phải bài toán đệ quy nào cũng để chúng ta nhìn thấy một công thức đệ quy đơn giản như vậy. Thậm chí, đôi khi chúng ta còn chẳng có một công thức cụ thể, mà chỉ đơn thuần là công việc được thực hiện sau đó có điểm tương đồng với phần trước thôi. Lúc này, ta cần giải đáp những câu hỏi:
Thuật toán quay luiKhái niệmThuật toán quay lui (backtracking) dùng để giải bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựng bằng cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách thử tất cả các khả năng. Tóm gọn lại, chúng ta đang xây dựng một danh sách gồm tất cả các tập hợp (hay dãy, …), mà mỗi phần tử được xét tất cả các trường hợp có thể của nó. Phương pháp này cũng gọi là duyệt vét cạn. Để cho khỏi "lú", trong bài viết này chúng ta thống nhất sẽ dùng cụm từ danh sách các tập hợp/dãy/xâu. Ví dụ: khi tìm danh sách các dãy nhị phân (các dãy gồm toàn các ký tự $0$, $1$ như dãy $0001011$) độ dài $3$, ta sẽ:
Trên phương diện quy nạp, nếu cần dựng danh sách các tập hợp mà mỗi tập có dạng ${x_1, x_2, …, x_n}$, ta xét mọi giá trị của $x_1$, rồi sau đó duyệt tiếp ${x_2, x_3, …, x_n}$, tiếp tục xét mọi giá trị $x_2$, rồi lại duyệt ${x_3, x_4, …, x_n}$, …, cho đến khi nào tất cả các giá trị đều đã xác định. Lúc này, ta lưu tập vừa tạo lại vào danh sách và tiếp tục chuyển sang tập khác từ các giá trị khác của các $x_i$
|