Hãy tìm tới thiết kế mới của thuật toán tìm kiếm nhị phân trên các dãy phần tử đã sắp xếp theo kĩ thuật đệ quy

Giải Chuyên đề Tin 11 Bài 2: Thiết kế thuật toán đệ quy - Kết nối tri thức

Hoạt động 2 trang 12 Chuyên đề Tin học 11: Chúng ta đã biết thuật toán tìm kiếm nhị phân trên các dãy phần tử đã sắp xếp. Hãy tìm tới thiết kế mới của thuật toán này theo kĩ thuật đệ quy. Trao đổi, thảo luận và trả lời các câu hỏi sau:

1. Nêu ý tưởng chính của giải thuật tìm kiếm nhị phân sử dụng đệ quy

2. Vị trí nào trong thuật toán có thể gợi ý cho kĩ thuật đệ quy?

3. Phần cơ sở của thiết kế đệ quy nằm ở bước nào?

Lời giải:

1. Ý tưởng chính của giải thuật tìm kiếm nhị phân sử dụng đệ quy là phân chia dãy phần tử đã sắp xếp thành hai nửa bằng nhau, tìm kiếm phần tử cần tìm trong nửa phù hợp và tiếp tục phân chia và tìm kiếm đệ quy cho đến khi tìm thấy phần tử hoặc không tìm thấy. 2. Vị trí trong thuật toán có thể gợi ý cho kĩ thuật đệ quy là phần phân chia dãy phần tử thành hai nửa bằng nhau, tìm kiếm trong nửa phù hợp và tiếp tục phân chia và tìm kiếm đệ quy cho đến khi tìm thấy phần tử hoặc không tìm thấy. Đây là một bài toán con nhỏ hơn của bài toán ban đầu và có thể được giải quyết bằng cùng một thuật toán đệ quy. 3. Phần cơ sở của thiết kế đệ quy nằm ở bước cuối cùng của thuật toán, khi không còn cách nào để phân chia dãy phần tử nữa và ta chỉ còn lại một phần tử hoặc không có phần tử nào để tìm kiếm. Khi đó, ta kết luận bài toán đệ quy đã được giải quyết và trả về kết quả.

Lời giải bài tập Chuyên đề Tin 11 Bài 2: Thiết kế thuật toán đệ quy hay, chi tiết khác:

• Khởi động trang 11 Chuyên đề Tin học 11: An được giao tìm một thiết kế mới cho bài toán tính tổng ....

• Hoạt động 1 trang 11 Chuyên đề Tin học 11: Trao đổi, thảo luận và tìm hiểu ý tưởng thực hiện các tính toán sau bằng kĩ thuật đệ quy ....

• Câu hỏi 1 trang 12 Chuyên đề Tin học 11: Hãy chỉ ra phần cơ sở và phần đệ quy của các chương trình trên ....

• Câu hỏi 2 trang 12 Chuyên đề Tin học 11: Vì sao trong ý tưởng trên, yêu cầu từ bài toán với kích thước lớn cần phải đưa về kích thước nhỏ hơn? ....

• Câu hỏi 1 trang 14 Chuyên đề Tin học 11: Trong chương trình trên lệnh nào đóng vai trò là phần cơ sở của đệ quy? ....

• Câu hỏi 2 trang 14 Chuyên đề Tin học 11: Giả sử A = [1, 3, 7, 9] và K = 10. Nếu áp dụng chương trình trên thì ....

• Luyện tập 1 trang 14 Chuyên đề Tin học 11: Viết chương trình theo kĩ thuật đệ quy để tính hàm SL(n) ....

• Luyện tập 2 trang 14 Chuyên đề Tin học 11: Cho trước dãy A. Viết chương trình đệ quy để in dãy A ....

• Vận dụng 1 trang 15 Chuyên đề Tin học 11: Viết chương trình tổng S= 1!+2!+...+n! theo hai cách ....

• Vận dụng 2 trang 15 Chuyên đề Tin học 11: Chúng ta đã biết thuật toán sắp xếp chèn trên dãy A cho trước theo hàm sau ....

• Vận dụng 3 trang 15 Chuyên đề Tin học 11: Bạn An đã nghĩ ra thuật toán tìm kiếm nhị phân bằng đệ quy theo cách ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 11 Kết nối tri thức hay, chi tiết khác:

• Chuyên đề Tin học 11 Bài 3: Thực hành giải toán theo kĩ thuật đệ quy

• Chuyên đề Tin học 11 Bài 4: Tháp Hà Nội

• Chuyên đề Tin học 11 Bài 5: Thực hành thiết kế thuật toán theo kĩ thuật đệ quy

• Chuyên đề Tin học 11 Bài 6: Ý tưởng và kĩ thuật chia để trị

• Chuyên đề Tin học 11 Bài 7: Thiết kế thuật toán theo kĩ thuật chia để trị

Xem thêm các tài liệu học tốt lớp 11 hay khác:

• Giải Chuyên đề Tin học 11 Kết nối tri thức
• Giải Chuyên đề Tin học 11 Chân trời sáng tạo
• Giải Chuyên đề Tin học 11 Cánh diều
• Giải lớp 11 Kết nối tri thức (các môn học)
• Giải lớp 11 Chân trời sáng tạo (các môn học)
• Giải lớp 11 Cánh diều (các môn học)

Săn SALE shopee Tết:

• Mỹ phẩm SACE LADY giảm tới 200k
• SRM Simple tặng tẩy trang 50k
• Combo Dầu Gội, Dầu Xả TRESEMME 80k

---