Học ngay
Học ngay
Học ngay
Học ngay
Học ngay
Học ngay
Học ngay
Học ngay
Học ngay
Học ngay
Học ngay
Học ngay
Bài 7: Thiết kế thuật toán theo kĩ thuật chia để trị - Chuyên đề Tin học 11 Kết nối tri thứcTrong bài học này em sẽ thiết kế lời giải cho hai bài toán sau 1. Bài toán tính luỹ thừa exp(a, n) = anvới a là số bất kì (khác 0), n là số nguyên không âm, ở đây anđược hiểu là tích của n lần giá trị a an = a × a × ... × a (n lần).Tổng hợp đề thi học kì 2ﷺ lớp 11 🐼tất cả các môn - Kết nối tri thức Toán - Văn - Anh - Lí - Hóa - SinhQuảng cáo
Lựa chọn câu để xem lời giải nhanh hơn
Câu 1 Trả lời câu hỏi khởi động trang 33 Chuyên đề Tin học 11 Kết nối tri thức Lời giải chi tiết: 1. Để tính luỹ thừa của một số a với một số nguyên không âm n, em có thể sử dụng thuật toán đệ quy như sau:
Câu 2 Trả lời câu hỏi hoạt động 1 trang 33 Chuyên đề Tin học 11 Kết nối tri thức Lời giải chi tiết: Để tính luỹ thừa an, bạn có thể sử dụng kỹ thuật đệ quy. Dưới đây là một cách thiết lập thuật toán và cài đặt chương trình tính luỹ thừa bằng kỹ thuật đệ quy: 1.Nếu n bằng 0, trả về 1 vì a0= 1. 2.Nếu n bằng 1, trả về a vì a1= a. 3.Nếu n lẻ, tính giá trị của an//2 bằng cách gọi đệ quy với tham số a và n//2, sau đó trả về kết quả nhân với chính nó: an=an//2 * an//2 * a. 4.Nếu n chẵn, tính giá trị của an//2 bằng cách gọi đệ quy với tham số a và n//2, sau đó trả về kết quả nhân với chính nó:an =an//2 *an//2
Câu 3 Trả lời câu hỏi 1 trang 34 Chuyên đề Tin học 11 Kết nối tri thức Lời giải chi tiết: Vì a^n = a x a^(n -1) 1. Tính bình thường:- Để tính bằng phương pháp bình thường, ta sẽ lặp lại việc nhân 2 với chính nó 21 lần (tức là 2* 2*...*2, lặp lại 21 lần). Tuy nhiên, việc tính toán này sẽ rất tốn thời gian và không hiệu quả khi giá trị của số mũ lớn hơn. 2. Chia để trị: Bước 1: Chia bài toán thành các bài toán con Chia 11 cho 2, ta được kết quả là 5 và số dư là 1: 11 = 2 * 5 + 1 Bước 2: Giải quyết các bài toán con Ta cần tính 2^5 để giải quyết bài toán con này. Tiếp tục áp dụng phương pháp chia để trị trên bài toán con này: Chia 5 cho 2, ta được kết quả là 2 và số dư là 1: 5 = 2 * 2 + 1 Tiếp tục giải bài toán con tiếp theo: Chia 2 cho 2, ta được kết quả là 1 và số dư là 0: 2 = 2 * 1 + 0 Bây giờ ta đã giải quyết được tất cả các bài toán con. Bước 3: Tính toán kết quả Từ bài toán con cuối cùng, ta có được: 2^1 = 2 Từ bài toán con thứ hai, ta có được: 2^2 = (2^1)^2 = 2^2 = 4 Từ bài toán con đầu tiên, ta có được: 2^5 = (2^2)^2 * 2 = 4^2 * 2 = 16 * 2 = 32 Vậy: 2^11 = 2^5 * 2^5 * 2 = 32 * 32 * 2 = 1024 Do đó, 2^11 = 1024.Câu 4 Trả lời câu hỏi 2 trang 34 Chuyên đề Tin học 11 Kết nối tri thức Lời giải chi tiết: Ta có công thức tổng quát sau: T(n) = T(n/2) + O(1) và T(0) = 1, O(1) =1 Với n = 21, T(21) = T(21/2) + 1 = T(10) + 1 = (T(5) + 1) + 1 =((T(2) + 1) + 1)+ 1 = T(1) + 1 + 3 = T(0) + 1 + 4 = 1 + 5 = 6Câu 5 Trả lời câu hỏi 2 trang 34 Chuyên đề Tin học 11 Kết nối tri thức Lời giải chi tiết: - Để tìm ra các phần tử của dãy gần K nhất chúng ta cần thêm các tính toán phụ tại dòng 10.
- Chúng ta thiết kế thuật toán thứ hai dựa trên tìm kiếm nhị phân. Hàm đệ quy chính sẽ được thiết kế theo dạng valueClosest(A, left, right, K) sẽ tìm phần tử gần K nhất trong khoảng chỉ số từ left đến right. Trước tiên có một số nhận xét cho các trường hợp đặc biệt.
Câu 6 Trả lời câu hỏi 1 trang 36 Chuyên đề Tin học 11 Kết nối tri thức Lời giải chi tiết: Giải thích kĩ hơn chương trình 2 trên tại các dòng 2 và 4: - Dòng 2: nếu left == right tức là mảng có 1 phần tử - Dòng 4: Nếu left == right - 1 tức là mảng có 2 phần tửCâu 7 Trả lời câu hỏi 2 trang 36 Chuyên đề Tin học 11 Kết nối tri thức Lời giải chi tiết: Điểm khác biệt: 1. Mục đích sử dụng: - Chương trình tìm kiếm nhị phân: Sử dụng để tìm kiếm một phần tử duy nhất trong một dãy số đã được sắp xếp. - Chương trình tìm ra các phần tử của dãy gần K nhất: Sử dụng để tìm các phần tử trong dãy số gần giá trị K nhất. 2. Phương pháp tìm kiếm: - Chương trình tìm kiếm nhị phân: Sử dụng phương pháp chia để trị và tìm kiếm trên nửa dãy con. - Chương trình tìm ra các phần tử của dãy gần K nhất: Sử dụng phương pháp tìm kiếm tuyến tính để tìm các phần tử gần giá trị K nhất. 4. Thời gian thực thi: - Chương trình tìm kiếm nhị phân có thời gian thực thi nhanh hơn chương trình tìm ra các phần tử của dãy gần K nhấtLuyện tập Câu 1 Trả lời câu hỏi Luyện tập 1 trang 36 Chuyên đề Tin học 11 Kết nối tri thức Lời giải chi tiết: Chương trình như sau:
Luyện tập Câu 2 Trả lời câu hỏi Luyện tập 1 trang 36 Chuyên đề Tin học 11 Kết nối tri thức Lời giải chi tiết: Để đo thời gian thực chạy của hai phương án tìm kiếm nhị phân tìm số gần nhất của dãy theo phương pháp đệ quy và không đệ quy, ta có thể sử dụng module time trong Python. Phương án tìm kiếm nhị phân mở rộng đệ quy:
Vận dụng Câu 1 Trả lời câu hỏi Vận dụng 1 trang 36 Chuyên đề Tin học 11 Kết nối tri thức Lời giải chi tiết: Tìm cách thiết lập thuật toán tính a^n theo phương pháp chia để trị nhưng không sử dụng đệ quy
Vận dụng Câu 2 Trả lời câu hỏi Vận dụng 2 trang 36 Chuyên đề Tin học 11 Kết nối tri thức Lời giải chi tiết: Thực hiện các bước sau: 1. Tìm phần tử giữa của dãy. 2. Nếu giá trị ở vị trí giữa lớn hơn K, ta tiếp tục tìm kiếm trong nửa đầu của dãy (bên trái phần tử giữa). 3. Nếu giá trị ở vị trí giữa nhỏ hơn K, ta tiếp tục tìm kiếm trong nửa sau của dãy (bên phải phần tử giữa). 4. Nếu giá trị ở vị trí giữa bằng K, ta tiến hành tìm vị trí bắt đầu và kết thúc của đoạn chứa các phần tử bằng K bằng cách tiến hành tìm kiếm vị trí bắt đầu và kết thúc của các phần tử liên tiếp bằng K từ phải sang trái và từ trái sang phải. Khi tìm được hai vị trí này, ta sẽ trả về start và end. 5. Nếu không tìm thấy K trong dãy, ta trả về -1, -1.
Thu được kết quả như sau:
 Chia sẻ Bình luận
Quảng cáo
Tham Gia Group Dành Cho Lớp 11 Chia Sẻ, Trao Đổi Tài Liệu Miễn Phí |
Bài khác
