Câu hỏi:
11/05/2023 221
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.
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.
Quảng cáo
Trả lời:
Giải bởi Vietjack
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.
Nhà sách vietjack
Hot: 500+ Đề thi thử tốt nghiệp THPT các môn, ĐGNL các trường ĐH... file word có đáp án (2025). Tải ngay
- Trọng tâm Sử, Địa, GD KTPL 11 cho cả 3 bộ Kết nối, Chân trời, Cánh diều VietJack - Sách 2025 ( 38.000₫ )
- Trọng tâm Hóa học 11 dùng cho cả 3 bộ sách Kết nối, Cánh diều, Chân trời sáng tạo VietJack - Sách 2025 ( 58.000₫ )
- Sách lớp 11 - Trọng tâm Toán, Lý, Hóa, Sử, Địa lớp 11 3 bộ sách KNTT, CTST, CD VietJack ( 52.000₫ )
- Sách lớp 10 - Combo Trọng tâm Toán, Văn, Anh và Lí, Hóa, Sinh cho cả 3 bộ KNTT, CD, CTST VietJack ( 75.000₫ )
Bình luận
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 2:
Mô tả các bước tính bằng tay phép tính luỹ thừa 
theo hai chương trình trên. Cách nào nhanh hơn?
Mô tả các bước tính bằng tay phép tính luỹ thừa theo hai chương trình trên. Cách nào nhanh hơn?
Xem đáp án »
12/07/2024
444
Câu 3:
Tìm cách thiết lập thuật toán tính theo phương pháp chia để trị nhưng không sử dụng đệ quy.
Tìm cách thiết lập thuật toán tính theo phương pháp chia để trị nhưng không sử dụng đệ quy.
Xem đáp án »
11/05/2023
381
Câu 4:
Viết chương trình đo thời gian thực chạy để so sánh hai phương án của bài toán.
Viết chương trình đo thời gian thực chạy để so sánh hai phương án của bài toán.
Xem đáp án »
12/07/2024
364
Câu 5:
Xây dựng thuật toán cho bài toán sau: Cho trước dãy các số đã được sắp xếp tăng dần. Với giá trị K cho trước cần tìm phần tử của dãy gốc có giá trị gần với K nhất.
Xây dựng thuật toán cho bài toán sau: Cho trước dãy các số đã được sắp xếp tăng dần. Với giá trị K cho trước cần tìm phần tử của dãy gốc có giá trị gần với K nhất.
Xem đáp án »
11/05/2023
299
Câu 6:
Trong bài học này em sẽ thiết kế lời giải cho hai bài toán sau:
1. Bài toán tính luỹ thừa exp(a, n) = với a là số bất kì (khác 0), n là số nguyên không âm, ở đây được hiểu là tích của n lần giá trị a an = a × a × ... × a (n lần).
2. Ban giám hiệu nhà trường cần tìm một bạn lớp em có chiều cao đúng bằng 1,7 m hoặc gần với chiều cao đó nhất để tham gia tập đội hình thể thao.
Với hai bài toán trên em sẽ thực hiện như thế nào?
Trong bài học này em sẽ thiết kế lời giải cho hai bài toán sau:
1. Bài toán tính luỹ thừa exp(a, n) = với a là số bất kì (khác 0), n là số nguyên không âm, ở đây được hiểu là tích của n lần giá trị a an = a × a × ... × a (n lần).
2. Ban giám hiệu nhà trường cần tìm một bạn lớp em có chiều cao đúng bằng 1,7 m hoặc gần với chiều cao đó nhất để tham gia tập đội hình thể thao.
Với hai bài toán trên em sẽ thực hiện như thế nào?
Xem đáp án »
11/05/2023
264
Câu 7:
Viết chương trình không đệ quy cho bài toán tìm kiếm nhị phần mở rộng trên.
Viết chương trình không đệ quy cho bài toán tìm kiếm nhị phần mở rộng trên.
Xem đáp án »
12/07/2024
264
🔥 Đề thi HOT:
-
Bộ 4 đề thi giữa học kì 2 Tin 11 Kết nối tri thức có đáp án (Đề 1)
-
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 17 có đáp án
-
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 21 có đáp án
-
15 câu Trắc nghiệm Tin học 11 Cánh diều Bài 1: Làm quen với Microsoft Access có đáp án
-
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 26 có đáp án
-
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 19 có đáp án
-
Bộ 4 đề thi giữa học kì 2 Tin 11 Kết nối tri thức có đáp án (Đề 2)
-
Bộ 4 đề thi giữa học kì 2 Tin 11 Kết nối tri thức có đáp án (Đề 3)
Hãy Đăng nhập hoặc Tạo tài khoản để gửi bình luận
-
-
Bình luận