Câu hỏi:

12/07/2024 382

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?

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

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ả.

Bình luận


Bình luận

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1:

Viết chương trình tổng S=1!+2!+...+n! theo hai cách:

a) Không sử dụng đệ quy

b) Có sử dụng kĩ thuật đệ quy

Xem đáp án » 12/07/2024 1,012

Câu 2:

Viết chương trình theo kĩ thuật đệ quy để tính hàm SL(n) là tổng các số tự nhiên lẻ nhỏ hơn hoặc bằng n

Xem đáp án » 12/07/2024 894

Câu 3:

Cho trước dãy A. Viết chương trình đệ quy để in dãy A theo thứ tự ngược lại.

Xem đáp án » 12/07/2024 693

Câu 4:

Bạn An đã nghĩ ra thuật toán tìm kiếm nhị phân bằng đệ quy theo cách khác như sau:

Bạn An đã nghĩ ra thuật toán tìm kiếm nhị phân bằng đệ quy theo cách khác như sau: (ảnh 1)

a) Chương trình của bạn An có đúng không?

b) Trong chương trình trên, phần cơ sở là những lệnh nào?

Xem đáp án » 12/07/2024 459

Câu 5:

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

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:   (ảnh 1)

Hãy thiết kế lại chương trình trên sử dụng kĩ thuật đệ quy

Xem đáp án » 12/07/2024 428

Câu 6:

Hãy chỉ ra phần cơ sở và phần đệ quy của các chương trình trên.

Xem đáp án » 12/07/2024 345
Vietjack official store
Đăng ký gói thi VIP

VIP +1 - Luyện thi tất cả các đề có trên Website trong 1 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +3 - Luyện thi tất cả các đề có trên Website trong 3 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +6 - Luyện thi tất cả các đề có trên Website trong 6 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +12 - Luyện thi tất cả các đề có trên Website trong 12 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay