Trang bìa
Trang bìa
Ảnh
BÀI 3 THỰC HÀNH ỨNG DỤNG THUẬT TOÁN TÌM KIẾM NHỊ PHÂN BẰNG ĐỆ QUY
CHUYÊN ĐỀ 2 THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT CHIA ĐỂ TRỊ
Khái niệm
Yêu cầu
Hình vẽ
Học xong bài này. em sẽ: * Áp dụng được phương pháp tìm kiếm nhị phân vào bài toán tìm phân tử lớn nhất trong bảng có phần đầu sắp xếp tăng dần và tuần sau sắp xếp giảm dần. * Viết được chương trình để giải một bài toán dùng kỹ thuật chia để trị bằng cách thu hẹp phạm vi tìm kiếm.
Tìm phần tử lớn nhất
Bài toá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 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 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à ít sử dụng phép so sánh nhất.
Bài toán
Ảnh
Hình 1. Minh họa hai lớp xếp hàng.
Yêu cầu
Ảnh
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. Hướng dẫn: - Bước 1: Chia Xác định vị trí k ở chính giữa dãy A. - Bước 2: (Trị). Xác định dãy bên trái hay dãy bên phải chứa phần tử có giá trị lớn nhất trong dãy, quay trở lại Bước 1 tìm trên dãy mới đó quá trình kết thúc khi xác định được phần tử 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ị latex(A_0, A_1, ...A_(n-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 Hướng dẫn: Em hãy dựa vào cách viết chương trình tìm kiếm nhị phân để viết chương trình cho bài toán này.
Chạy kiểm thử
Em hãy chạy chương trình của phần thực hành với các dữ liệu kiểm thử ở Bảng 1
Ảnh
Bảng 1. Một số bộ dữ liệu thử nghiệm cho Thực hành 2
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 so với phương pháp tìm kiếm tuần tự.
Hướng dẫn
Bước 1. Viết chương trình tìm kiếm tuần tự dùng vòng lặp để tìm kiếm phần tử latex(A_k). Bước 2. Sử dụng một biến đếm để đếm số lần thực hiện hàm lệ quy của phần Thực hành 2
Bài tập
Ứng dụng Xem lại dấu lơn, bằng
Hình vẽ
Cho dãy a gồm n phần tử latex(A_0, A_1,...A_(n-1)) sao cho tồn tại k(0 Ảnh
Ứng dụng
Ảnh
Bảng 2 một bộ dữ liệu thử nghiệm cho bài toán Vận dụng
Cảm ơn
Thank You
Ảnh