Tailieumoi.vn giới thiệu giải Chuyên đề Tin học lớp 11 Bài 1: Ý tưởng chia để trị sách Cánh diều hay, chi tiết giúp học sinh xem và so sánh lời giải từ đó biết cách làm Chuyên đề học tập Tin học 11. Mời các bạn đón xem:
Giải Chuyên đề Tin học 11 Bài 1: Ý tưởng chia để trị
4 7 8 20 21 22 36 77 81
Số 21 ở vị trí chính giữa của dãy, các số bên trái của số 21 luôn nhỏ hơn 21 và các số bên phải của số 21 luôn lớn hơn 21. Do đó, nếu muốn tìm một số x nhỏ hơn 21 thì chỉ cần thu hẹp phạm vi tìm kiếm vào một nửa của dãy, theo em đó là nửa dãy bên trái hay nửa dãy bên phải của số 21?
Lời giải:
Nếu muốn tìm một số x nhỏ hơn 21 thì chỉ cần thu hẹp phạm vi tìm kiếm vào một nửa của dãy, theo em đó là số 21 thuộc về vị trí chính giữa.
1. Ý tưởng kĩ thuật chia để trị
Lời giải:
Cách giải quyết bài toán trên thể hiện ý tưởng chia đề trị, bao gồm 3 bước:
1. Chia: Chia bài toán bạn đầu (phức tạp) thành hai hoặc nhiều bài toán con (đơn gián hơn). Tiếp tục chia mỗi bài toán con thành các bài toán con đơn gian hơn nữa và cứ như thể cho đến khi đạt được các bài toán con đủ đơn giản mà chúng được giải quyết một cách dễ dàng
2 Trị: Giải quyết các bài toán cơn (một cách đệ quy). kết quả là các lời giải cua các bài toán con.
3. Kết hợp: Kết hợp eắc lời giải của các bài toán con để có được lời giải của bài toán ban đầu.
Lời giải:
Giải quyết bài toán nhỏ bằng cách tiếp tục thu hẹp không gian tìm kiếm bài toán để đưa về bài toán nhỏ hơn cho đến khi đạt được kết quả cần tìm.
Thu hẹp dần phạm vi tìm kiếm là một kĩ thuật của chia để trị. Kĩ thuật này được áp dụng trong các bài toán có thể loại bỏ đi những phần không gian tìm kiếm mà chắc chắn nghiệm của bài toán không nằm trong đó để giảm bớt độ phức tạp tính toán của thuật toán.
2. Thuật toán Tìm kiếm nhị phân
Lời giải:
Do tính chất mảng đã sắp xếp, công việc tìm kiếm phần tử x có thể triển khai như sau:
1. Xét đoạn mảng arr[left…right] cần tìm kiếm phần tử x. Ta so sánh x với phần tử ở vị trí giữa của mảng(mid = (left + right)/2). Nếu:
2. Nếu phần tử arr[mid] = x. Kết luận và thoát chương trình.
3. Nếu arr[mid] < x. Chỉ thực hiện tìm kiếm trên đoạn arr[mid+1…right].
4. Nếu arr[mid] > x. Chỉ thực hiện tìm kiếm trên đoạn arr[left…mid-1].
A.2 B4
C.5 D8
Lời giải:
Câu trả lời đúng là ý: C.5
Lời giải:
Hai công thức tính chỉ số i trong hai chương trình của Hình 5 và Hình 6 có khác nhau. Hai chương trình này có cùng kết quả tìm kiếm.
Xem thêm lời giải bài tập Chuyên đề học tập Tin học lớp 11 Cánh diều hay, chi tiết khác:
Bài 4: Thực hành tổng hợp thiết kế thuật toán đệ quy
Bài 2: Kĩ thuật đệ quy trong chia để trị
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 4: Kĩ thuật chia để trị trong thuật toán sắp xếp trộn