Với giải Vận dụng 2 trang 39 Chuyên đề Tin học 11 Kết nối tri thức chi tiết trong Bài 8: Thực hành thiết thuật toán tìm kiếm theo kĩ thuật chia để trị giúp học sinh dễ dàng xem và so sánh lời giải từ đó biết cách làm bài tập Chuyên đề Tin học 11. Mời các bạn đón xem:

Giải Chuyên đề Tin học 11 Bài 8: Thực hành thiết thuật toán tìm kiếm theo kĩ thuật chia để trị

Vận dụng 2 trang 39 Chuyên đề Tin học 11: Cho một dãy số nguyên được sắp xếp theo thứ tự tăng dần, hãy tìm một vị trí thứ i trong dãy sao cho phần tử thứ i có giá trị bằng i.

Lời giải:

Để tìm vị trí thứ i trong dãy số sao cho phần tử thứ i có giá trị bằng i, ta có thể sử dụng phương pháp chia để trị như sau:

1. Tìm giá trị trung bình của left và right: mid = (left + right) // 2

2. Nếu giá trị tại vị trí mid bằng mid, tức là A[mid] == mid, thì trả về mid

3. Nếu giá trị tại vị trí mid lớn hơn mid, tức là A[mid] > mid, thì tiếp tục tìm vị trí thích hợp trong đoạn từ left đến mid-1

4. Nếu giá trị tại vị trí mid nhỏ hơn mid, tức là A[mid] < mid, thì tiếp tục tìm vị trí thích hợp trong đoạn từ mid+1 đến right

5. Nếu không tìm được vị trí thích hợp nào, tức là left > right, thì trả về -1

Ví dụ:

Kết quả sẽ là "Vị trí thích hợp là: 3", tức là phần tử thứ 3 trong dãy A có giá trị bằng 3.