Bài tập thực hành: Giải thuật đệ quy trong Cấu trúc dữ liệu và Giải thuật (ĐHSPKT Hưng Yên)

Bài tập thực hành cấu trúc dữ liệu & giải thuật: Bài 9 hướng dẫn cài đặt giải thuật đệ quy. Nắm vững kiến thức & kỹ năng lập trình đệ quy hiệu quả.

• Trường học: Trường Đại Học Sư Phạm Kỹ Thuật Hưng Yên
• Chuyên ngành: Cấu trúc dữ liệu và giải thuật
• Đề tài: Đệ Quy: Bài Tập Cấu Trúc Dữ Liệu & Giải Thuật
• Loại tài liệu: Bài tập thực hành
• Năm xuất bản: 2021
• Địa điểm: Hưng Yên

Mục lục chi tiết

• MỤC LỤC
• 9. Bài 9: Thực hành cài đặt giải thuật đệ quy
• 10. Bài 10: Thực hành cài đặt danh sách bằng mảng
• 11. Bài 11: Thực hành cài đặt danh sách bằng danh sách liên kết đơn
• 12. Bài 12: Thực hành cài đặt danh sách Stack, Queue
• 13. Bài 13: Thực hành cài đặt cây nhị phân
• 14. Bài 14: Thực hành cài đặt các giải thuật sắp xếp - tìm kiếm

Tóm tắt

I. Đệ Quy Là Gì Tổng Quan Ứng Dụng Trong Cấu Trúc Dữ Liệu

Đệ quy, hay recursion, là một khái niệm nền tảng trong khoa học máy tính và lập trình. Nó cho phép một hàm tự gọi chính nó để giải quyết các bài toán phức tạp bằng cách chia nhỏ chúng thành các bài toán con nhỏ hơn, tương tự. Bản chất của đệ quy nằm ở việc định nghĩa một bài toán bằng chính nó, với một hoặc nhiều trường hợp cơ sở (base case) để ngăn chặn việc tự gọi vô hạn. Khi một hàm đệ quy được gọi, một bản sao mới của hàm được tạo ra trong bộ nhớ, và các tham số và biến cục bộ của bản sao này được lưu trữ trong một cấu trúc dữ liệu gọi là call stack. Khi một bản sao của hàm hoàn thành việc thực thi, nó trả về kết quả cho bản sao gọi nó, và bản sao đó được giải phóng khỏi bộ nhớ.

Ứng dụng của đệ quy rất rộng rãi, từ việc duyệt các cấu trúc dữ liệu như cây (tree traversal recursion), đồ thị (depth-first search recursion), đến việc giải các bài toán như tính giai thừa (factorial recursion), dãy Fibonacci (fibonacci recursion), hay các thuật toán sắp xếp như Merge Sort (merge sort recursion) và Quick Sort (quick sort recursion). Đệ quy cũng đóng vai trò quan trọng trong các kỹ thuật lập trình như divide and conquer, dynamic programming, và backtracking. Ưu điểm của đệ quy bao gồm tính ngắn gọn, dễ hiểu và khả năng giải quyết các bài toán phức tạp một cách tự nhiên. Tuy nhiên, đệ quy cũng có nhược điểm là có thể gây ra stack overflow nếu không được thiết kế cẩn thận, và có thể kém hiệu quả hơn so với các giải pháp lặp (iterative vs recursive solutions) trong một số trường hợp.

1.1. Khái niệm hàm đệ quy recursive function và vai trò

Hàm đệ quy là hàm tự gọi chính nó trong định nghĩa của nó. Điều này cho phép hàm giải quyết các bài toán phức tạp bằng cách chia nhỏ chúng thành các bài toán con tương tự. Vai trò của hàm đệ quy là tạo ra các giải pháp ngắn gọn, dễ hiểu và tự nhiên cho các bài toán có thể được định nghĩa bằng chính nó. Ví dụ, hàm tính giai thừa có thể được định nghĩa đệ quy như sau: factorial(n) = n * factorial(n-1) với trường hợp cơ sở factorial(0) = 1. Hàm đệ quy giúp đơn giản hóa việc lập trình và giảm thiểu mã lặp đi lặp lại.

1.2. Phân biệt Base Case trường hợp cơ sở và Recursive Step bước đệ quy

Một hàm đệ quy cần có hai thành phần chính: base case và recursive step. Base case là trường hợp đơn giản nhất của bài toán mà có thể giải quyết trực tiếp mà không cần gọi đệ quy. Nó đóng vai trò là điểm dừng cho quá trình đệ quy, ngăn chặn việc tự gọi vô hạn. Recursive step là phần của hàm mà gọi chính nó với một phiên bản nhỏ hơn của bài toán. Trong recursive step, bài toán được chia nhỏ thành các bài toán con tương tự, và hàm đệ quy được gọi để giải quyết các bài toán con này. Ví dụ, trong hàm tính giai thừa, base case là n = 0 và recursive step là n > 0 với factorial(n) = n * factorial(n-1).

1.3. Ưu điểm và nhược điểm của đệ quy advantages of recursion

Đệ quy có nhiều ưu điểm, bao gồm tính ngắn gọn, dễ hiểu, và khả năng giải quyết các bài toán phức tạp một cách tự nhiên. Nó cũng cho phép lập trình viên tập trung vào logic của bài toán hơn là các chi tiết triển khai. Tuy nhiên, đệ quy cũng có nhược điểm là có thể gây ra stack overflow nếu không được thiết kế cẩn thận, và có thể kém hiệu quả hơn so với các giải pháp lặp trong một số trường hợp. Việc sử dụng call stack để lưu trữ các bản sao của hàm đệ quy có thể tốn kém về mặt bộ nhớ, đặc biệt là đối với các bài toán có độ sâu đệ quy lớn. Trong một số trường hợp, việc sử dụng các kỹ thuật như tail recursion và memoization có thể giúp cải thiện hiệu suất của hàm đệ quy.

II. Vượt Qua Thách Thức Ngăn Chặn Stack Overflow Khi Dùng Đệ Quy

Một trong những thách thức lớn nhất khi sử dụng đệ quy là nguy cơ gây ra stack overflow. Điều này xảy ra khi độ sâu đệ quy quá lớn, dẫn đến việc call stack tràn bộ nhớ. Để ngăn chặn stack overflow, cần đảm bảo rằng hàm đệ quy có một base case rõ ràng và rằng mỗi lần gọi đệ quy đều tiến gần hơn đến base case. Cũng cần xem xét giới hạn độ sâu đệ quy của hệ thống và thiết kế thuật toán sao cho không vượt quá giới hạn này.

Một số kỹ thuật có thể giúp giảm thiểu nguy cơ stack overflow bao gồm tail recursion và memoization. Tail recursion là một hình thức đệ quy mà lời gọi đệ quy là thao tác cuối cùng được thực hiện trong hàm. Trong một số ngôn ngữ, trình biên dịch có thể tối ưu hóa tail recursion thành vòng lặp, giúp giảm thiểu việc sử dụng bộ nhớ. Memoization là một kỹ thuật lưu trữ kết quả của các lời gọi hàm đệ quy để tránh việc tính toán lại các giá trị đã biết. Kỹ thuật này có thể giúp cải thiện hiệu suất của hàm đệ quy, đặc biệt là đối với các bài toán có nhiều lời gọi đệ quy trùng lặp.

2.1. Tìm hiểu nguyên nhân gây ra lỗi Stack Overflow khi sử dụng đệ quy

Lỗi stack overflow xảy ra khi chương trình cố gắng sử dụng nhiều bộ nhớ hơn mức cho phép trên call stack. Khi một hàm đệ quy được gọi, một bản sao mới của hàm được tạo ra trên call stack, cùng với các tham số và biến cục bộ của bản sao đó. Nếu hàm đệ quy gọi chính nó quá nhiều lần mà không đạt đến base case, call stack sẽ tiếp tục tăng kích thước cho đến khi nó tràn bộ nhớ. Nguyên nhân chính gây ra lỗi stack overflow là do thiết kế hàm đệ quy không cẩn thận, dẫn đến việc tự gọi vô hạn hoặc độ sâu đệ quy quá lớn.

2.2. Kỹ thuật Tail Recursion đệ quy đuôi và cách tối ưu hóa

Tail recursion là một hình thức đệ quy mà lời gọi đệ quy là thao tác cuối cùng được thực hiện trong hàm. Điều này cho phép trình biên dịch tối ưu hóa hàm đệ quy thành vòng lặp, giúp giảm thiểu việc sử dụng bộ nhớ trên call stack. Để chuyển đổi một hàm đệ quy thông thường thành tail recursion, cần đảm bảo rằng lời gọi đệ quy là thao tác cuối cùng được thực hiện, và kết quả của lời gọi đệ quy được trả về trực tiếp mà không cần thực hiện thêm bất kỳ thao tác nào. Ví dụ, hàm tính giai thừa có thể được chuyển đổi thành tail recursion bằng cách sử dụng một tham số tích lũy để lưu trữ kết quả trung gian.

2.3. Memoization Lưu trữ kết quả để tránh tính toán lặp lại

Memoization là một kỹ thuật lưu trữ kết quả của các lời gọi hàm đệ quy để tránh việc tính toán lại các giá trị đã biết. Khi một hàm đệ quy được gọi với một bộ tham số cụ thể, kết quả được lưu trữ trong một bảng tra cứu (lookup table). Nếu hàm đệ quy được gọi lại với cùng bộ tham số đó, kết quả được lấy từ bảng tra cứu thay vì tính toán lại. Memoization có thể giúp cải thiện hiệu suất của hàm đệ quy, đặc biệt là đối với các bài toán có nhiều lời gọi đệ quy trùng lặp, như tính dãy Fibonacci.

III. Ứng Dụng Đệ Quy Giải Quyết Bài Toán Cấu Trúc Dữ Liệu Hiệu Quả

Đệ quy là một công cụ mạnh mẽ để giải quyết các bài toán liên quan đến cấu trúc dữ liệu. Nó đặc biệt hữu ích trong việc duyệt và xử lý các cấu trúc dữ liệu có tính chất đệ quy, chẳng hạn như cây (tree traversal recursion), đồ thị (depth-first search recursion), và danh sách liên kết (linked list recursion). Với cây, đệ quy có thể được sử dụng để duyệt cây theo thứ tự trước, giữa, sau, hoặc theo chiều rộng. Với đồ thị, đệ quy có thể được sử dụng để tìm đường đi, kiểm tra tính liên thông, hoặc tìm chu trình. Với danh sách liên kết, đệ quy có thể được sử dụng để đảo ngược danh sách, tìm phần tử, hoặc xóa phần tử.

Việc sử dụng đệ quy trong các bài toán cấu trúc dữ liệu giúp tạo ra các giải pháp ngắn gọn, dễ hiểu và dễ bảo trì. Tuy nhiên, cũng cần lưu ý đến các vấn đề liên quan đến hiệu suất và stack overflow, và xem xét các giải pháp lặp nếu cần thiết.

3.1. Đệ quy trên cây nhị phân binary search recursion Duyệt và tìm kiếm

Đệ quy là phương pháp tự nhiên để duyệt và tìm kiếm trên cây nhị phân. Các thuật toán duyệt cây nhị phân như duyệt trước (preorder), duyệt giữa (inorder), và duyệt sau (postorder) đều có thể được triển khai một cách dễ dàng bằng đệ quy. Đối với tìm kiếm trên cây nhị phân tìm kiếm (binary search recursion), đệ quy cho phép tìm kiếm phần tử một cách hiệu quả bằng cách so sánh giá trị cần tìm với giá trị của nút hiện tại và tiếp tục tìm kiếm trên cây con trái hoặc cây con phải tùy thuộc vào kết quả so sánh.

3.2. Đệ quy trên danh sách liên kết linked list recursion Thao tác cơ bản

Đệ quy cũng có thể được sử dụng để thực hiện các thao tác cơ bản trên danh sách liên kết. Ví dụ, hàm đảo ngược danh sách liên kết có thể được triển khai đệ quy bằng cách đảo ngược phần còn lại của danh sách và sau đó thêm phần tử đầu tiên vào cuối danh sách đã đảo ngược. Các thao tác khác như tìm phần tử, xóa phần tử, hoặc chèn phần tử cũng có thể được triển khai đệ quy, mặc dù các giải pháp lặp thường hiệu quả hơn.

3.3. Ứng dụng thuật toán Depth First Search DFS bằng đệ quy

Depth-First Search (DFS) là một thuật toán duyệt đồ thị quan trọng có thể được triển khai một cách tự nhiên bằng đệ quy. DFS bắt đầu từ một đỉnh và duyệt sâu vào đồ thị cho đến khi không còn đỉnh nào chưa được thăm. Sau đó, nó quay lui và tiếp tục duyệt các nhánh khác của đồ thị. Đệ quy cho phép dễ dàng theo dõi trạng thái của các đỉnh đã được thăm và đảm bảo rằng tất cả các đỉnh trong đồ thị đều được duyệt qua.

IV. Đệ Quy Trong Sắp Xếp Tìm Kiếm Giải Thuật Nhanh và Hiệu Quả

Đệ quy đóng vai trò quan trọng trong nhiều thuật toán sắp xếp và tìm kiếm hiệu quả. Các thuật toán sắp xếp như Merge Sort (merge sort recursion) và Quick Sort (quick sort recursion) sử dụng divide and conquer, một kỹ thuật dựa trên đệ quy, để chia nhỏ bài toán sắp xếp thành các bài toán con nhỏ hơn, sắp xếp các bài toán con này, và sau đó kết hợp kết quả để tạo ra dãy đã sắp xếp.

Đối với tìm kiếm, binary search recursion là một thuật toán tìm kiếm hiệu quả trên dãy đã sắp xếp, sử dụng đệ quy để chia đôi không gian tìm kiếm mỗi lần, giúp giảm đáng kể thời gian tìm kiếm. Việc sử dụng đệ quy trong các thuật toán sắp xếp và tìm kiếm giúp tạo ra các giải pháp hiệu quả và dễ hiểu, mặc dù cũng cần lưu ý đến các vấn đề liên quan đến hiệu suất và stack overflow.

4.1. Phân tích giải thuật Merge Sort sắp xếp trộn đệ quy

Merge Sort là một thuật toán sắp xếp divide and conquer sử dụng đệ quy để chia dãy cần sắp xếp thành các dãy con nhỏ hơn, sắp xếp các dãy con này, và sau đó trộn các dãy con đã sắp xếp để tạo ra dãy đã sắp xếp. Hàm Merge Sort đệ quy chia dãy thành hai nửa, gọi đệ quy để sắp xếp hai nửa này, và sau đó trộn hai nửa đã sắp xếp. Độ phức tạp thời gian của Merge Sort là O(n log n), làm cho nó trở thành một thuật toán sắp xếp hiệu quả cho các dãy lớn.

4.2. Phân tích giải thuật Quick Sort sắp xếp nhanh đệ quy

Quick Sort là một thuật toán sắp xếp divide and conquer khác sử dụng đệ quy. Nó chọn một phần tử pivot từ dãy và chia dãy thành hai phần: các phần tử nhỏ hơn pivot và các phần tử lớn hơn pivot. Sau đó, nó gọi đệ quy để sắp xếp hai phần này. Hiệu suất của Quick Sort phụ thuộc vào việc chọn pivot tốt. Trong trường hợp tốt nhất và trung bình, độ phức tạp thời gian của Quick Sort là O(n log n), nhưng trong trường hợp xấu nhất, nó có thể là O(n^2). Tuy nhiên, Quick Sort thường nhanh hơn Merge Sort trong thực tế do ít tốn chi phí hơn.

4.3. Cài đặt tìm kiếm nhị phân binary search sử dụng đệ quy

Tìm kiếm nhị phân (binary search) là một thuật toán tìm kiếm hiệu quả trên dãy đã sắp xếp. Nó sử dụng đệ quy để chia đôi không gian tìm kiếm mỗi lần. Hàm tìm kiếm nhị phân đệ quy so sánh giá trị cần tìm với giá trị của phần tử ở giữa dãy. Nếu giá trị cần tìm nhỏ hơn giá trị ở giữa, nó tiếp tục tìm kiếm trên nửa đầu của dãy; nếu lớn hơn, nó tiếp tục tìm kiếm trên nửa sau của dãy. Nếu bằng, nó trả về vị trí của phần tử. Độ phức tạp thời gian của tìm kiếm nhị phân là O(log n), làm cho nó trở thành một thuật toán tìm kiếm rất hiệu quả cho các dãy lớn đã sắp xếp.

V. Đệ Quy Bài Toán Kinh Điển Tháp Hà Nội Giai Thừa Fibonacci

Đệ quy thường được sử dụng để giải quyết các bài toán kinh điển trong khoa học máy tính, chẳng hạn như Tháp Hà Nội (tower of hanoi), tính giai thừa (factorial recursion), và tính dãy Fibonacci (fibonacci recursion). Tháp Hà Nội là một bài toán về di chuyển các đĩa từ một cột sang một cột khác, tuân theo một số quy tắc. Giải pháp đệ quy cho bài toán này rất ngắn gọn và dễ hiểu. Tính giai thừa và dãy Fibonacci là các ví dụ khác về các bài toán có thể được giải quyết một cách tự nhiên bằng đệ quy. Tuy nhiên, cần lưu ý rằng giải pháp đệ quy cho bài toán Fibonacci có thể kém hiệu quả do nhiều lời gọi đệ quy trùng lặp, và nên sử dụng memoization hoặc giải pháp lặp để cải thiện hiệu suất.

5.1. Giải bài toán Tháp Hà Nội tower of hanoi bằng đệ quy

Bài toán Tháp Hà Nội là một bài toán kinh điển về di chuyển các đĩa từ một cột sang một cột khác, tuân theo các quy tắc: chỉ được di chuyển một đĩa tại một thời điểm, và không được đặt một đĩa lớn hơn lên trên một đĩa nhỏ hơn. Giải pháp đệ quy cho bài toán này rất ngắn gọn và dễ hiểu. Nó bao gồm ba bước: di chuyển n-1 đĩa từ cột nguồn sang cột trung gian, di chuyển đĩa lớn nhất từ cột nguồn sang cột đích, và di chuyển n-1 đĩa từ cột trung gian sang cột đích.

5.2. Cài đặt hàm đệ quy tính giai thừa factorial

Hàm tính giai thừa có thể được cài đặt đệ quy như sau: factorial(n) = n * factorial(n-1) với trường hợp cơ sở factorial(0) = 1. Hàm này gọi chính nó với một giá trị nhỏ hơn của n cho đến khi đạt đến trường hợp cơ sở, tại đó nó trả về giá trị 1. Giải pháp đệ quy cho bài toán này rất ngắn gọn và dễ hiểu, nhưng cần lưu ý rằng nó có thể gây ra stack overflow nếu n quá lớn.

5.3. Cài đặt hàm đệ quy tính số Fibonacci fibonacci

Hàm tính số Fibonacci có thể được cài đặt đệ quy như sau: fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) với các trường hợp cơ sở fibonacci(0) = 0 và fibonacci(1) = 1. Hàm này gọi chính nó với hai giá trị nhỏ hơn của n cho đến khi đạt đến các trường hợp cơ sở, tại đó nó trả về giá trị 0 hoặc 1. Giải pháp đệ quy cho bài toán này rất dễ hiểu, nhưng nó kém hiệu quả do nhiều lời gọi đệ quy trùng lặp. Để cải thiện hiệu suất, có thể sử dụng memoization hoặc giải pháp lặp.

VI. Đệ Quy Trong Thực Tế Ngôn Ngữ Lập Trình Lời Khuyên

Đệ quy được hỗ trợ rộng rãi trong nhiều ngôn ngữ lập trình, bao gồm C++, Python, Java, và JavaScript. Mỗi ngôn ngữ có cú pháp và quy tắc riêng để sử dụng đệ quy. Trong C++, đệ quy được sử dụng tương tự như trong C. Trong Python, đệ quy được hỗ trợ tốt, nhưng có giới hạn độ sâu đệ quy mặc định để ngăn chặn stack overflow. Trong Java, đệ quy được sử dụng rộng rãi trong các bài toán cấu trúc dữ liệu và thuật toán. Trong JavaScript, đệ quy được sử dụng trong cả lập trình phía máy chủ và phía máy khách.

Khi sử dụng đệ quy trong thực tế, cần lưu ý đến các vấn đề liên quan đến hiệu suất và stack overflow. Nên sử dụng tail recursion và memoization khi có thể để cải thiện hiệu suất. Cũng nên xem xét các giải pháp lặp nếu đệ quy không phải là lựa chọn tốt nhất.

6.1. Đệ quy trong C Đệ quy trong C Cú pháp và ví dụ

Trong C++, đệ quy được sử dụng tương tự như trong C. Hàm đệ quy được định nghĩa bằng cách gọi chính nó trong thân hàm. Cần đảm bảo rằng hàm có một trường hợp cơ sở để ngăn chặn việc tự gọi vô hạn. Ví dụ, hàm tính giai thừa có thể được cài đặt đệ quy trong C++ như sau:

int factorial(int n) {
 if (n == 0) {
 return 1;
 } else {
 return n * factorial(n-1);
 }
}

6.2. Đệ quy trong Python Đệ quy trong Python Giới hạn và cách khắc phục

Trong Python, đệ quy được hỗ trợ tốt, nhưng có giới hạn độ sâu đệ quy mặc định để ngăn chặn stack overflow. Giới hạn này có thể được thay đổi bằng cách sử dụng hàm sys.setrecursionlimit(), nhưng cần cẩn thận để không đặt giới hạn quá cao, vì điều này có thể dẫn đến stack overflow. Ví dụ, hàm tính giai thừa có thể được cài đặt đệ quy trong Python như sau:

def factorial(n):
 if n == 0:
 return 1
 else:
 return n * factorial(n-1)

6.3. Đệ quy trong Java Đệ quy trong Java Ứng dụng và lời khuyên

Trong Java, đệ quy được sử dụng rộng rãi trong các bài toán cấu trúc dữ liệu và thuật toán. Ví dụ, hàm tính giai thừa có thể được cài đặt đệ quy trong Java như sau:

public static int factorial(int n) {
 if (n == 0) {
 return 1;
 } else {
 return n * factorial(n-1);
 }
}

Khi sử dụng đệ quy trong Java, cần lưu ý đến các vấn đề liên quan đến hiệu suất và stack overflow. Nên sử dụng tail recursion và memoization khi có thể để cải thiện hiệu suất. Cũng nên xem xét các giải pháp lặp nếu đệ quy không phải là lựa chọn tốt nhất.

Trích đoạn nội dung tài liệu

TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT HƯNG YÊN KHOA CÔNG NGHỆ THÔNG TIN BÀI TẬP THỰC HÀNH HỌC PHẦN: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Trình độ đào tạo : Đại học chính quy Ngành đào tạo : CNTT, KTPM, KHMT Hưng Yên, năm 2021 MỤC LỤC Bài 9: Thực hành cài đặt giải thuật đệ quy. 3 Bài 10: Thực hành cài đặt danh sách bằng mảng. 10 Bài 11: Thực hành cài đặt danh sách bằng danh sách liên kết đơn. 17 Bài 12: Thực hành cài đặt danh sách Stack, Queue.

23 Bài 13: Thực hành cài đặt cây nhị phân. 33 Bài 14: Thực hành cài đặt các giải thuật sắp xếp - tìm kiếm. 35 Bài tập thực hành môn CTDL&GT Trang 2 Bài 9: Thực hành cài đặt giải thuật đệ quy Mục tiêu: Sau khi học xong bài này người học có khả năng: - Cài đặt được giải thuật đệ qui theo yêu cầu của các bài toán. - Giải thích được trình tự máy tính thực hiện khi thực thi các chương trình đệ qui.

- Rèn luyện kỹ năng lập trình, tư duy logic Bài tập mẫu Bài 1: Hãy viết giải thuật đệ quy tính số fibonaci thứ n; biết rằng f(n)=1 nếu n=1, f(n)=0 nếu n=0, f(n) = f(n-1)+ f(n-2) nếu n>1 Phân tích Từ công thức tính số fibonaci thứ n mà bài toán đặt rat a nhận thấy. - Trường hợp suy biến của bài toán xảy ra khi n<2 ta có f(n) =n - Trường hợp đệ quy xảy ra khi n>1: F(n) = F(n-1) + F(n-2) Giải thuật đệ quy để tính số fibonaci thứ n: int F(n){ if(n<2) return n; else return F(n-1) + F(n-2); } Lời giải mẫu using System; class Exam{ // Hàm đệ qui tính số fibonaci thứ n public static int f(int n){ if(n<2) return n; else return f(n-1)+f(n-2); } // Chương trình chính public static void main() { Console.ReadKey(); } Nhận xét Khi viết giải thuật đệ quy cần xác định được lời giải của giải thuật ứng với 2 trường hợp: suy biến và trường hợp đệ qui Kết quả thực hiện chương trình Bài tập thực hành môn CTDL&GT Trang 3 Bài 2: Viết chương trình thực hiện in ra tất cả các xâu nhị phân có độ dài N. Phân tích Ta có thuật toán tổng quát cho bài toán quay lui đệ quy. PROCEDURE TÌM(K:INTEGER); KHAI BÁO CÁC BIẾN NẾU CẦN; BEGIN NẾU LÀ BƯỚC SAU BƯỚC CUỐI CÙNG THÌ HIỆN NGHIỆM NGƯỢC LẠI VÒNG LẶP CHẠY CÁC TRƯỜNG HỢP CÓ THỂ LẤY LÀM PHẦN TỬ CỦA NGHIỆM BEGIN THỬ CHỌN MỘT ĐỀ CỬ TRONG CÁC BƯỚC TÌM PHẦN TỬ CỦA NGHIỆM; NẾU ĐỀ CỬ THỎA MÃN THÌ BEGIN LƯU PHẦN TỬ VÀO NGHIỆM; GHI NHẬN TRẠNG THÁI MỚI CỦA BÀI TOÁN; TÌM(K+1); TRẢ LẠI TRẠNG THÁI CỦ CỦA BÀI TOÁN TRƯỚC LÚC CHỌN ĐỀ CỬ; END; END; END; Theo yêu cầu của bài toán ta có thuật giải cho bài toán : - Mảng luu để lưu giá trị của chuỗi nhị phân - Đầu tiên ta sẽ tìm giá trị gán cho bít k=1 của chuỗi (là 0 or 1), sau đó gọi đệ quy tìm giá trị gán cho bít k=2, ….

- Lời gọi đệ quy kết thúc khi k== n+1 (nghĩa là ta đã thực hiện gán được giá trị cho n bít) khi đó sẽ hiển thị ra kết quả của chuỗi nhị phân Bài tập thực hành môn CTDL&GT Trang 4 Lời giải mẫu using System; namespace VDDeQui { class DeQui { static int n, d = 0; static int[] luu; // Hien thi ket qua ra man hinh static void Xuat(int[] luu) { for (int i = 0; i < n; i++) Console.0/n Bài 4: Tính S(x, n) = xn Gợi ý: Ta xây dựng hàm LuyThua(X, N) để tính XN với N dương. - Ta nhận thấy trường hợp suy biến: N=0 khi đó hàm nhận giá trị là 1 - Trường hợp đệ qui: N > 0 khi đó ta có LuyThua(X, N) = LuyThua(X, N- 1)*X Hàm S(x, n) sẽ được định nghĩa như sau: double S(x, n){ Bài tập thực hành môn CTDL&GT Trang 6 if(n<0) return 1.0/LuyThua(x, -n); else return LuyThua(x, n); } Bài 5: Tìm ước số lẻ lớn nhất của số nguyên dương n. Ví dụ : n = 100 ước lẻ lớn nhất của 100 là 25 Gợi ý: - Ta nhận thấy trường hợp suy biến: Nếu n%2==1 khi đó UocLeMax(n)= n - Trường hợp đệ qui: Ngược lại ta có UocLeMax(n) = UocLeMax(n/2) Bài 6: Tìm ước chung lớn nhất của 2 số nguyên dương a,b Gợi ý: Theo thuật toán Euclid: - Ta nhận thấy trường hợp suy biến: Nếu a%b ==0 thì UCLN(a, b) =b - Trường hợp đệ qui: ngược lại thì UCLN(a, b)= UCLN(b, a%b) Bài 7: Đếm số chữ số của số nguyên dương n Gợi ý: - Ta nhận thấy trường hợp suy biến: Nếu n==0 thì SoChuSo(n) =0 - Trường hợp đệ qui: ngược lại thì SoChuSo(n) = SoChuSo(n/10) +1 √ Bài 8: Tính S(n) = 1 + √2 + √3 + √4 + ⋯ … + √𝑛 − 1 + √𝑛 Gợi ý: Ta có giải thuật tính tổng căn như sau: float Can(int i, int n){ if(i==n) return sqrt(n) ; else return sqrt(i + Can(i+1, n)); } float S(int n){ return Can(1, n); } Bài tập thực hành môn CTDL&GT Trang 7 Bài 9: Hãy viết giải thuật cho bài toán: phân tích số N thành tổng các số tự nhiên. Viết chương trình hiển thị ra tất cả các cách có thể để phân tích số N thành tổng các số tự nhiên.

Gợi ý 5 = 1+4; =2+3=0+5 Theo yêu cầu của bài toán ta có thuật giải cho bài toán : - Mảng luu để lưu giá trị của các các số hạng được phân tích; tối đa có Số N được phân tích thành tổng có tối đa N số hạng, và ta cần 1 phần tử đầu tiên của mảng làm cờ; do đó Ta cần tạo luu là mảng có N+1 phần tử và được khởi gán giá trị ban đầu là 0. - Giả sử t là giá trị số được phân tích tính đến bước hiện tại, t ban đầu được khởi gán bằng 0. - Đầu tiên ta sẽ tìm giá trị gán cho số hạng đầu tiên (k=1), rồi gọi đệ quy tìm giá trị cho số hạng k = 2,. quá trình đệ qui kết thúc khi t == N(nghĩa là ta đã thực hiện tìm được lời giải) khi đó sẽ hiển thị ra kết quả của phép phân tích.

Giải thuật để phân tích số n thành tổng các số tự nhiên // k là số lượng số hạng được phân tích của tổng void Tao(int k) { int i,j; if (t == n) { d = d+1; // Tăng số nghiệm tìm thấy lên 1 // Hiển thị cách phân tích số N ra màn hình Console.WriteLine(luu[k-1]); } else for (j=1; j<=n; j++) if ((t+j<=n) && (j>= luu[k-1]) ) { luu[k]=j; t=t+j; Tao(k+1); t =t-j; luu[k]=0; } } Bài tập thực hành môn CTDL&GT Trang 8 Bài 10: Cho dãy số nguyên a1, a2, a3,. an; và một số nguyên. Phân tích số m thành tổng các phần tử của dãy không dùng lặp lại và đưa ra cách phân tích có ít số hạng nhất. Gợi ý - Mảng Kt để đánh dấu phần tử của mảng a đa được sử dụng, kt[i] = false nghĩa là a[i] đã được sử dụng, không thể dùng được nữa.

- Mảng luu để lưu nghiệm hiện tại - Mảng mluu để lưu nghiệm tối ưu thỏa mãn yêu cầu bài toán - Min để lưu số lượng phần tử ít nhất dùng để phân tích số m, min được khởi gán bởi giá trị min = 0 Thuật toán đệ qui tìm nghiệm tối ưu Thuật toán hiển thị kết quả nghiệm tối ưu của bài toán static void Tao(int k) { static void Xuat(){ int i,j; if (t == m) if(min==0) { if (min > k-1|| min==0) { Console.Write("Khong co cach phan tich thoa min=k-1; man yeu cau bai toan"); for (i=0 ;i< k-1; i=i+1) { mluu[i]=luu[i]; else{ } Console.WriteLine(mluu[min]); kt[j] = false; Tao(k+1); } t = t - a[j]; kt[j] = true; } luu[k]=0; } } Bài 11: Viết giải thuật đệ qui tìm USCLN của 2 số nguyên, áp dụng viết chương trình thực hiện nhập 2 số nguyên từ bàn phím, hiển thị ra màn hình USCLN, BSCNN của 2 số nguyên đó. Bài tập thực hành môn CTDL&GT Trang 9 Bài 10: Thực hành cài đặt danh sách bằng mảng Mục tiêu: - Hệ thống lại các kiến thức về mảng như: cách khai báo, cách thức tổ chức dữ liệu trên mảng, các thao tác trên mảng - Áp dụng các kiến thức về mảng để cài đặt được bài toán lưu trữ danh sách và thực hiện các thao tác trên mảng - Có khả năng nhận xét các ưu, nhược điểm khi cài đặt danh sách bằng mảng. Bài tập mẫu: Bài 1: Cho n số nguyên dương a0,a1,a2,.Chèn phần tử x vào vị trí k của dãy.Xóa tất cả các số nguyên tố trong dãy.Khởi tạo một mảng trung gian tmp có độ dài là (a.Length+1) sau đó gán các giá trị : tmp[i]=a[i] với i từ 0 ->k-1 (k-1 là vị trí trước vị trí cần chèn) tmp[k]=giá trị cần chèn tmp[i+1]=a[i] với i từ k->a.Length-1 Cuối cùng gán mảng a=tmp.Thực hiện duyệt các phần tử trong mảng kiểm tra xem phần tử đó có phải là số nguyên tố hay không (số nguyến tố là số chỉ chia hết cho 1 và chính nó) : + Nếu là số nguyên tố: Duyệt mảng từ trái sang phải.Từ vị trí số nguyên tố đó tiến hành dời các phần tử về phía trước cho đến khi kết thúc mảng, sau đó giảm kích thước mảng +Ngược lại, chuyển sang kiểm tra phần tử kế tiếp Lời giải mẫu using System; class VD { static int[] a; //Mảng a chứa các phần tử số nguyên static void Nhap() { int n; Bài tập thực hành môn CTDL&GT Trang 10 Console.ReadLine()); a = new int[n]; //Cấp phát cho mảng a số phần tử là n for (int i = 0; i < a.ReadLine()); } } static void Chen(int x, int k) //Chèn phần tử có giá trị x vào vị trí k trong mảng a { if (k >= 0 && k <= a.Length - 1) //Kiểm tra xem vị trí k có trong mảng không { int[] tmp = new int[a.Length + 1]; //Sau khi chèn mảng mới tmp sẽ thêm 1 phần tử for (int i = 0; i < k; ++i) tmp[i] = a[i]; tmp[k] = x; for (int i = k; i < a.Length; ++i) tmp[i + 1] = a[i]; a = tmp; } else Console.Length; for (int i = 0; i < n; ) if (ngto(a[i])) // Xóa số là nguyên tố { for (int j = i; j < a.Length - 1; ++j) //dồn các phần tử từ vị trí I đến cuối a[j] = a[j + 1]; n = n - 1; //sau khi xóa số phần tử trong mảng giảm đi 1 đơn vị } else ++i; int[] tmp = new int[n]; //mảng sau khi xóa có kích thước bằng n mới for (int i = 0; i < n; ++i) tmp[i] = a[i]; a = tmp; } static void Hien() { for (int i = 0; i < a.