Tìm kiế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

Trang trước Trang sau

Giải Chuyên đề Tin học 11 Bài 3: Thực hành ứng dụng thuật toán tìm kiếm nhị phân bằng đệ quy - Cánh diều

Bài toán trang 35 Chuyên đề Tin học 11: Tìm kiế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.

Quảng cáo

Yêu cầu: 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 số lần so sánh là ít nhất.

Lưu ý: Ak là phần tử có giá trị lớn nhất của dãy A.

Lời giải:

Để giải quyết bài toán trên, hãy thực hiện lần lượt các bài thực hành sau.

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: Các bước bao gồm:

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 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 đó. 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ị 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.

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.

Kiểm thử chương trình:

Em hãy chạy kiểm thử chương trình của phần thực hành với các dữ liệu kiểm thử trong Bảng 1.

Nếu chương trình cho kết quả sai với một bộ dữ liệu kiểm thử thì thêm vào các lệnh để in ra giá trị của các biến; sau đó, chạy lại chương trình với bộ dữ liệu kiểm thử này, theo dõi sự thay đổi giá trị của các biến và phát hiện lệnh nào tính toán sai.

Tìm kiế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

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 của 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ự.

Hướng dẫn:

Các bước bao gồm:

Bước 1. Viết chương trình tìm kiếm tuần tự dùng vòng lặp để tìm phần tử Ak. Sử dụng một biến đếm để đếm số lần lặp.

Bước 2. Sử dụng một biến đếm để đếm số lần thực hiện hàm đệ quy của phần Thực hành 2.

Quảng cáo

Lời giải Chuyên đề Tin 11 Bài 3: Thực hành ứng dụng thuật toán tìm kiếm nhị phân bằng đệ quy hay, ngắn gọn khác:

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 11 Cánh diều hay, ngắn gọn khác:

Săn SALE shopee Tết:

ĐỀ THI, GIÁO ÁN, SÁCH LUYỆN THI DÀNH CHO GIÁO VIÊN VÀ PHỤ HUYNH LỚP 11

Bộ giáo án, bài giảng powerpoint, đề thi, sách dành cho giáo viên và gia sư dành cho phụ huynh tại https://tailieugiaovien.com.vn/ . Hỗ trợ zalo VietJack Official

Tổng đài hỗ trợ đăng ký : 084 283 45 85

Giáo án, bài giảng powerpoint Văn, Toán, Lí, Hóa....

4.5 (243)

799,000đs

199,000 VNĐ

Đề thi, chuyên đề Cánh diều, Kết nối tri thức, Chân trời sáng tạo...

4.5 (243)

799,000đ

99,000 VNĐ

Gia sư 1:1 bởi các thầy cô VietJack

4.5 (243)

299,000đ

199,000 VNĐ

xem tất cả

Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.

Theo dõi chúng tôi miễn phí trên mạng xã hội facebook và youtube:

Nếu thấy hay, hãy động viên và chia sẻ nhé! Các bình luận không phù hợp với nội quy bình luận trang web sẽ bị cấm bình luận vĩnh viễn.

Trang trước Trang sau
Giải bài tập lớp 11 sách mới các môn học
Học cùng VietJack
Tài liệu giáo viên