Giải SGK Chuyên đề Tin học 11 Bài 10. Thực hành giải toán bằng kĩ thuật chia để trị
24 người thi tuần này 4.6 804 lượt thi 4 câu hỏi
Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Dành cho bạn Hot
Danh sách câu hỏi:
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Để xác định dãy số đã được sắp xếp theo thứ tự tăng dần hoặc giảm dần, ta có thể sử dụng thuật toán kiểm tra sự sắp xếp. Các bước thực hiện như sau:
1. Duyệt qua từng phần tử của dãy số, bắt đầu từ phần tử thứ 2.
2. Kiểm tra xem phần tử hiện tại có lớn hơn (nếu kiểm tra tăng dần) hoặc nhỏ hơn (nếu kiểm tra giảm dần) phần tử trước đó không.
3. Nếu có ít nhất một phần tử không đúng thứ tự, tức là dãy số không được sắp xếp theo thứ tự tăng dần (giảm dần).
4. Nếu tất cả các phần tử đều đúng thứ tự, dãy số đã được sắp xếp theo thứ tự tăng dần (giảm dần).
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Để giải quyết bài toán đếm số cặp nghịch đảo của dãy số, ta có thể sử dụng một thuật toán đơn giản như sau:
- Duyệt qua từng phần tử của dãy và đối chiếu với các phần tử sau nó để tìm các cặp nghịch đảo.
- Nếu phần tử tại vị trí i lớn hơn phần tử tại vị trí j, ta tăng biến đếm số cặp nghịch đảo lên 1 và lưu cặp chỉ số (i, j) vào danh sách các cặp nghịch đảo.
- Trả về giá trị biến đếm số cặp nghịch đảo và danh sách các cặp chỉ số nghịch đảo.
- Kết quả như sau:
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Để tìm phần tử xuất hiện nhiều lần nhất trong dãy, ta có thể sử dụng phương pháp chia để trị (divide and conquer) bằng cách chia dãy thành hai phần và tìm phần tử xuất hiện nhiều lần nhất trong mỗi phần, sau đó so sánh và lấy phần tử xuất hiện nhiều lần nhất trong cả hai phần.
Ví dụ:
Kết quả: “Phần tử xuất hiện nhiều nhất là 5, số lần xuất hiện là 3”
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Em có thể áp dụng kỹ thuật chia để trị như sau:
1. Chia dãy số ban đầu thành hai dãy con bằng cách chia nó ở giữa.
2. Giải quyết hai dãy con bằng cách đệ quy áp dụng cùng thuật toán.
3. Tìm tổng con lớn nhất chứa phần tử ở giữa của dãy số ban đầu. Ta thực hiện điều này bằng cách tính tổng của phần tử đó cùng các phần tử liền trước và liền sau nó, rồi lưu lại tổng lớn nhất tìm được.
4. Tìm tổng con lớn nhất nằm hoàn toàn trong một trong hai dãy con đã giải quyết ở bước 5. Ta thực hiện điều này bằng cách đệ quy áp dụng lại thuật toán trên hai dãy con đó.
6. Tìm tổng con lớn nhất giữa phần tử ở giữa dãy con trái và phần tử ở giữa dãy con phải. Ta thực hiện điều này bằng cách tính tổng của phần tử giữa dãy con trái và phần tử giữa dãy con phải, rồi lưu lại tổng lớn nhất tìm được.
Đăng ký để học cùng Vietjack. Hoàn toàn miễn phí!
Bằng việc đăng ký, bạn đồng ý với Điều khoản sử dụng và Chính sách bảo mật của Vietjack.
Nhắn tin Zalo
Hỏi bài tập