Trang bìa
Trang bìa
Ảnh
BÀI 2 KĨ THUẬT ĐỆ QUY TRONG CHIA ĐỂ TRỊ
CHUYÊN ĐỀ 2 THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT CHIA ĐỂ TRỊ
Khái niệm
Ứng dụng
Hình vẽ
Học xong bài này, em sẽ: * Nêu được ý tưởng kỹ thuật để quy xong bài toán tìm kiếm nhị phân và tính latex(a^n). * Biết được một số bài toán sử dụng kỹ thuật để quy trong chia để trị. * Cài đặt được thuật toán tìm kiếm nhị phân bằng kỹ thuật đệ quy . * Hiểu và mô tả được thuật toán giải bài toán tính latex(a^n).
Câu hỏi
Hình vẽ
Trong bài 1, em đã biết thuật toán tìm kiếm nhị phân bằng vòng lặp việc loại bỏ đi một nửa dãy sau mỗi bước và tìm kiếm phần tử trên một nửa dãy còn lại cũng phù hợp với việc cài đặt đệ quy do các bước làm chỉ khác nhau ở phạm vi tìm kiếm. Em hãy mô tả lại từng bước thu hẹp phạm vi tìm kiếm trên một ví dụ trongHhình 4 của Bài 1 để thấy sự lặp lại thuật toán trên bài toán con so với bài toán cha
Ảnh
Cài đặt thuật toán tìm kiếm nhị phân bằng đệ quy
Các bước thực hiện
- Bước 1. So sánh x với phần tử nằm ở vị trí giữa dãy số, gọi là phần tử giữa. - Bước 2. Nếu x bằng với giá trị phần tử giữa, đưa ra vị trí phần tử tìm được. - Bước 3. Nếu x lớn hơn giá trị phần tử giữa giá trị x chỉ có thể nằm ở nửa bên phải phần tử của phần tử giữa của dãy số (nửa có giá trị lớn hơn). Quay lại Bước 1, tiếp tục áp dụng thuật toán đối với nửa dãy số bên phải này. - Bước 4. Nếu x nhỏ hơn giá trị phần tử giữa, giá trị x chỉ có thể nằm ở nửa bên trái phần tử giữa của dãy số (nửa có giá trị nhỏ hơn). Quay lại Bước 1 tiếp tục áp dụng thuật toán đối với nửa dãy số bên này.
Yêu cầu 1
Hình vẽ
Tìm hiểu Bước 3 và Bước 4 trong thuật toán tìm kiếm nhị phân để rút ra kỹ thuật đệ quy cài đặt thuật toán này. Hai bước trên có thể cài đặt bởi lời gọi đệ quy đến hàm tìm kiếm nhị phân tổng quát với tham số đầu vào là khoảng cần tìm kiếm trong dãy số. Em hãy đọc hiểu chương trình Python mẫu trong Hình 1 và chạy thử nghiệm trên các bộ dữ liệu đầu vào khác nhau.
Ảnh
Nhận xét
Lưu ý: Trong trường hợp phạm vi tìm kiếm là rỗng nghĩa là (t > p trong chương trình ở Hình 1), chương trình cần thông báo không tồn tại từ phía cần tìm.
Nhận xét
Ảnh
Hình 1 chương trình đệ quy Tìm kiếm nhị phân trên dãy số không giảm cho bài thực hành và màn hình kết quả chạy một số bộ dữ liệu thử nghiệm
Bài toán tính
Bài toán
Trong giờ học môn Toán, thầy giáo ra câu hỏi cho cả lớp xem ai tính nhanh nhất giá trị của 3 mũ 10. Thanh An nghĩ rằng nếu cứ nhân lần lượt 10 số 3 với nhau thì sẽ phải mất 9 phép nhân . Do đó mới học chuyên đề khoa học máy tính phần chia để chị Thanh An nghĩ cách để giảm bớt số phép nhân .Thanh An thấy rằng Hình 2 nên chỉ cần một lần tính latex(3^5) và bình phương giá trị đó lên thì số phép nhân phải sử dụng giảm đi đáng kể tuy nhiên với thì Thanh An lại chưa nghĩ ra được cách chia đôi để giảm bớt phép nhân do năm là số lẻ khi về nhà Thanh An muốn lập trình giải quyết bài toán tổng quát tính với A và N là hai số nguyên dương
Bài toán
Ảnh
Hình 2. Cách tính dùng chia để trị
Yêu cầu 2
Em hãy giúp Thanh An mô tả chi tiết các bước tính giá trị với số phép tính nhân phải sử dụng là ít nhất.
Hình 3. Cách tính latex(3^10 = 3^5 x 3^5) dùng chia để trị
Ảnh
Thực hành viết lại
Hướng dẫn: Có hai trường hợp: 1) latex(a^n = a^(n/2) x a^(n/2)) nếu n chẵn 2, latex(a^n = a x a^(n - 1)) nếu n lẻ và n > 1
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 bộ dữ liệu kiểm thử trong Bảng 1. Chạy chương trình nếu kết quả sai, sẽ thêm các lệnh để in ra giá trị của các biến và 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.
Kiểm thử chương trình
Ảnh
Bảng 1. Một số dữ liêu thử nghiệm cho bài toán latex(a^n)
Bài tập
Ứng dụng
Hình vẽ
Em hãy viết hàm để quy để tìm kiếm nhị phân giá trị x trong dãy a không giảm có n phần tử latex(A_0,(A_1), ...(A_(n-1)) các phần tử có thể trùng nhau. Nếu tìm thấy thì hàm này trả về chỉ số i nhỏ nhất mà latex(A_i) =x. Nếu không tìm thấy thì hàng này trả về -1
Ảnh
Câu hỏi
Hình vẽ
Câu 1. Trong những câu sau đây ,câu nào đúng với việc giải bài toán tính latex(a^n) bằng phương pháp chia để trị? 1) Xét trường hợp n chẵn và n lẻ riêng. 2) n chẵn hay n lẻ đều giải quyết như nhau. Câu 2. Em hãy cho biết, nếu sử dụng phương pháp chia để trị để tính latex(4^12) thì ít nhất cần bao nhiêu phép tính nhân. A4 B5 C6 D7
Ảnh
Tóm tắt bài học
Hình vẽ
Tóm tắt bài học. Thuật toán tìm kiếm nhị phân phù hợp để cài đặt bằng kỹ thuật đệ quy do việc học lại chức năng thuật toán của các bài toán con. * Bài toán tính latex(a^n) được giải quyết bằng kỹ thuật đệ quy trong các phương pháp chia để trị nhờ việc xét trường hợpn chẵn và n lẻ.
Cảm ơn
Thank You
Ảnh