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.

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.

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?

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.

Nêu những điểm khác biệt của chương trình trên với chương trình tìm kiếm nhị phân đã biết

Hãy thiết lập thuật toán và chương trình tính luỹ thừa $a^n$ với a là số bất kì khác 0, n là số nguyên không âm.

Hãy giải thích kĩ hơn chương trình 2 trên tại các dòng 2 và 4.

Phép tính $a^{21}$ sẽ cần dùng bao nhiêu phép nhân?

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) = $a^n$ với a là số bất kì (khác 0), n là số nguyên không âm, ở đây $a^n$ đượ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?

Tìm cách thiết lập thuật toán tính $a^n$ theo phương pháp chia để trị nhưng không sử dụng đệ quy.

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.