Bài toán tìm vùng chỉ số của dãy đã sắp xếp
Bài toán tìm vùng chỉ số của dãy đã sắp xếp
Giải Chuyên đề Tin 11 Bài 7: Thiết kế thuật toán theo kĩ thuật chia để trị - Kết nối tri thức
Vận dụng 2 trang 36 Chuyên đề Tin học 11: Bài toán tìm vùng chỉ số của dãy đã sắp xếp
Thiết lập thuật toán chia để trị để giải bài toán sau: Cho trước dãy A gồm n phần tử đã được sắp xếp theo thứ tự tăng dần, ví dụ:
A= [1, 2, 3, 3, 4, 4, 4, 5, 6, 6]
Cho trước giá trị K, cần tìm ra vùng chỉ số gồm các phần tử bằng K. Chương trình cần trả về hai chỉ số start, end là vị trí bắt đầu và kết thúc gồm toàn các giá trị K. Nếu không tìm thấy K thì phải trả về -1, -1.
Trong ví dụ trên, nếu K = 4 thì cần trả về hai chỉ số 4, 6.
Lời giải:
Thực hiện các bước sau:
1. Tìm phần tử giữa của dãy.
2. Nếu giá trị ở vị trí giữa lớn hơn K, ta tiếp tục tìm kiếm trong nửa đầu của dãy (bên trái phần tử giữa).
3. Nếu giá trị ở vị trí giữa nhỏ hơn K, ta tiếp tục tìm kiếm trong nửa sau của dãy (bên phải phần tử giữa).
4. Nếu giá trị ở vị trí giữa bằng K, ta tiến hành tìm vị trí bắt đầu và kết thúc của đoạn chứa các phần tử bằng K bằng cách tiến hành tìm kiếm vị trí bắt đầu và kết thúc của các phần tử liên tiếp bằng K từ phải sang trái và từ trái sang phải. Khi tìm được hai vị trí này, ta sẽ trả về start và end.
5. Nếu không tìm thấy K trong dãy, ta trả về -1, -1.
Ví dụ:
Thu được kết quả như sau:
Lời giải bài tập Chuyên đề Tin 11 Bài 7: Thiết kế thuật toán theo kĩ thuật chia để trị hay, chi tiết khác:
Câu hỏi 1 trang 34 Chuyên đề Tin học 11: Mô tả các bước tính bằng tay phép tính luỹ thừa ....
Câu hỏi 2 trang 34 Chuyên đề Tin học 11: Phép tính a^21 sẽ cần dùng bao nhiêu phép nhân? ....
Hoạt động 2 trang 34 Chuyên đề Tin học 11: Xây dựng thuật toán cho bài toán sau: ....
Câu hỏi 1 trang 36 Chuyên đề Tin học 11: Hãy giải thích kĩ hơn chương trình 2 ....
Câu hỏi 2 trang 36 Chuyên đề Tin học 11: Nêu những điểm khác biệt của chương trình trên ....
Luyện tập 1 trang 36 Chuyên đề Tin học 11: Viết chương trình không đệ quy cho bài toán ....
Luyện tập 1 trang 36 Chuyên đề Tin học 11: Viết chương trình đo thời gian thực chạy để ....
Vận dụng 1 trang 36 Chuyên đề Tin học 11: Tìm cách thiết lập thuật toán tính ....
Vận dụng 2 trang 36 Chuyên đề Tin học 11: Bài toán tìm vùng chỉ số của ....