Giáo án điện tử chuyên đề Khoa học máy tính 11 cánh diều Bài 3: Thực hành ứng dụng thuật toán tìm kiếm nhị phân bằng đệ quy

MỜI CÁC EM

ĐẾN VỚI TIẾT HỌC!

KHỞI ĐỘNG

Em hãy nhắc lại các bước trong mô tả thuật toán tìm kiếm nhị phân.

BÀI 3: THỰC HÀNH

ỨNG DỤNG THUẬT TOÁN TÌM KIẾM NHỊ PHÂN BẰNG ĐỆ QUY

Bài toán:

Tìm phần tử lớn nhất trong mảng có phần đầu sắp xếp tăng dần và phần sau sắp xếp giảm dần

Sau giờ chào cờ, trường của Thanh An tổ chức hoạt động kết nối ở sân trường. Lớp của Thanh An được xếp thành một hàng theo chiều cao tăng dần. Lớp của Hải Bình được xếp thành một hàng theo chiều cao giảm dần. Sau đó, nhập hai lớp này thành một hàng bằng cách bạn đầu tiên của lớp Hải Bình đứng vào sau bạn cuối cùng của lớp Thanh An và tạo thành một hàng như Hình 1. Thầy giáo phụ trách yêu cầu đưa ra được cách tìm bạn có chiều cao lớn nhất trong hàng mà sử dụng ít phép so sánh nhất.

Bài toán

MÔ PHỎNG BÀI TOÁN

10 học sinh tham gia xếp thành hàng:

• 4 học sinh đầu xếp thành hàng theo chiều cao tăng dần.
• 6 học sinh còn lại xếp thành hàng nối tiếp 4 học sinh đầu nhưng theo chiều cao giảm dần.

Gọi chiều cao 10 bạn là A0, A1,…,A9.

HƯỚNG DẪN THỰC HIỆN

1

Lấy bạn ở giữa dãy có chiều cao A4, so sánh chiều cao A4 > A5, do đó bạn cao nhất sẽ nằm bên trái bạn thứ 5.

2

Lấy bạn ở giữa dãy hiện tại có chiều cao A2, so sánh chiều cao A2 < A3, do đó bạn cao nhất sẽ nằm bên phải bạn thứ 2.

3

So sánh chiều cao hai bạn còn lại A3 và A4, bạn nào có chiều cao lớn hơn thì bạn đó là bạn có chiều cao lớn nhất trong dãy cần tìm.

Cho dãy A gồm n phần tử có giá trị đôi một khác nhau A0, A1,…,An-1 sao cho tồn tại k(0 < k < n – 1) để A0 < A1 < … < Ak và Ak > Ak+1 >…> An-1. Em hãy viết chương trình tìm phần tử số k sao cho lần so sánh là ít nhất.

Thực hành 1:

Mô tả chi tiết cách giải bài toán trên dùng phương pháp tìm kiếm nhị phân.

Thực hành 1

Phần tử lớn nhất là phần tử tại vị trí j thỏa mãn một trong ba điều kiện sau:

j = 0 và A[0] > A[i]

j = n – 1 và A[n – 2] < A[n – 1]

j > 1 và A[j – 1] < A[j] < A[j + 1]

Hướng dẫn: Đưa việc xét điều kiện 1 và 2 ở trên vào đầu chương trình. Nếu 2 điều kiện đầu không xảy ra, áp dụng chia để trị để xác định điều kiện 3 theo các bước sau:

1

(Chia): Xác định vị trí k ở giữa.

2

(Trị): Xác định dãy bên trái hay bên phải của Ak chứa phần tử có giá trị lớn nhất trong dãy, quay trở lại Bước 1 tiếp tục tìm trên dãy mới đó.

 Chương trình kết thúc khi xác định được giá trị lớn nhất.

Thực hành 2:

Viết chương trình dùng đệ quy: Nhập vào giá trị n và n giá trị A0, A1,…,An-1 có dạng phần đầu giá trị tăng dần và phần sau giá trị giảm dần, hãy hiển thị phần tử có giá trị lớn nhất của dãy A.

Thực hành 2

Gợi ý:

Học sinh tự lập trình giải bài toán dựa vào chương trình tìm kiếm nhị phân bằng đệ quy, thay đổi các điều kiện so sánh cho phù hợp với bài toán này.

Thực hành 3:

Viết chương trình tìm kiếm tuần tự cho bài toán trên. Với mỗi bộ dữ liệu thử nghiệm, em hãy so sánh số lần lặp của chương trình tìm kiếm tuần tự (dùng vòng lặp) với số lần gọi đệ quy của chương trình ở phần Thực hành 2 (dùng đệ quy). Từ đó, với nhiều bộ dữ liệu thử nghiệm, em sẽ nhận thấy phương pháp tìm kiếm nhị phân có số lần lặp ít hơn nhiều so với phương pháp tìm kiếm tuần tự.

Thực hành 3

Chương trình tìm kiếm tuần tự

Sử dụng vòng lặp tuần tự duyệt qua các phần tử của mảng A để tìm ra phần tử có giá trị lớn nhất.

Dùng một biến đếm đặt trong vòng lặp để đếm số lần lặp.

Chương trình tìm kiếm nhị phân bằng đệ quy: Sử dụng một biến đếm đặt đầu hàm đệ quy để đếm số lần gọi hàm này.

So sánh kết quả của hai biến đếm sau khi thực hiện hai chương trình

Đưa ra nhận xét

LUYỆN TẬP

Câu 1: So sánh phần tử k với phần tử k + 1, nếu Ak > Ak+1 thì phần tử lớn nhất nằm ở đâu?

A. Trong khoảng từ đầu dãy đến phần tử thứ k.

B. Trong khoảng từ phần tử thứ k đến cuối dãy.

C. Trong khoảng từ đầu dãy đến phần tử thứ k + 1.

D. Trong khoảng từ phần tử thứ k + 1 đến cuối dãy.

A. Trong khoảng từ đầu dãy đến phần tử thứ k.

Câu 2: Lời gọi đệ quy chính của hàm sau là

A. findRange(A,0,len(A) – 1,K).

B. findRange(A,left,mid – 1,K).

C. findRange(A,mid + 1, right, K).

D. findRange(A,left,right,K).

A. findRange(A,0,len(A) – 1,K).

Câu 3: Một bộ số dữ liệu vào như sau, kết quả ra là

A. Phần tử lớn nhất có giá trị 91 ở vị trí số 4.

B. Phần tử lớn nhất có giá trị 91 ở vị trí số 12.

C. Phần tử lớn nhất có giá trị 91 ở vị trí số 8.

D. Phần tử lớn nhất có giá trị 91 ở vị trí số 0.

C. Phần tử lớn nhất có giá trị 91 ở vị trí số 8.

Câu 4: Ở bước Trị, khi xác định dãy bên trái hay bên phải của Ak chứa phần tử có giá trí lớn nhất trong dãy, thuật toán sẽ

A. xác định vị trí k ở chính giữa dãy A.

B. quay trở lại Bước 1 và tiếp tục tìm trên dãy mới đó.

C. xác định vị trí bên trái hoặc bên phải là giá trị cần tìm.

D. không xác định và quá trình kết thúc.

B. quay trở lại Bước 1 và tiếp tục tìm trên dãy mới đó.

Câu 5: Chương trình tìm kiếm nhị phân bằng đệ quy là gì?

--------------- Còn tiếp ---------------