Trang bìa
Trang bìa
Ảnh
BÀI 2 THUẬT TOÁN ĐỆ QUY
CHUYÊN ĐỀ1. THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT ĐỆ QUY
Khái niệm
Ứng dụng
Hình vẽ
Học xong bài nay, em sẽ: * Làm quen với hàm đệ quy. * Biết được các bước cần thực hiện khi giải bài toán băng thuật toán đệ quy. * Đọc hiểu được một vài chương trình toán đơn giản sử dụng thuật toán đệ quy.
Khái niệm
Yêu cầu
Hình vẽ
Định nghĩa . latex(a^n = a x a x ...x a) ( n số a) Em hãy đưa ra mô tả đệ quy cho hàm F(n) để tính latex(a^n)
Ảnh
Khái niệm đệ quy
Yêu cầu 1
Hình vẽ
Hai chương trình trong Hình 1 yêu cầu người sử dụng nhập hai giá trị nguyên a và từ n bàn phím (n>0) rồi gọi hàm power1 (a,n) và power2 (a,n) tương ứng để in ra màn hình giá trị latex(a^n) . Em hãy đọc cả hai chương trình này và: a) Cho biết kết quả thu được của hai chương trình khi giá trị của cặp(a,n) nhập vào lần lượt bằng (2,4) và (3,6) b) Nhận xét về sự khác nhau giữa hai hàm power1 (a,n) và power2 (a,n).
Ảnh
Yêu cầu 1
Ảnh
Ảnh
Thuật toán đệ quy
Khái niệm
Hhi cài đặt các thuật toán đệ quy, người ta từng xây dựng các hàm để quy. Thuật toán đệ quy thường có mô hình như ở Hình 2.
Ảnh
Hình 2 mô hình của thuật toán đệ quy
Yêu cầu 2
Hình vẽ
Em hãy: a) Đọc chương trình ở Hình 3 và cho biết dấu (?) trong hàm h(n) cần được thay thế bằng gì để tính được số lượng cái bắt tay diễn ra trong phòng họp có n người b) Chạy chương trình để tính số cái bắt tay khi n = 5 và n = 10.
Ảnh
Hình 3. Chương trình đệ quy giải bài toán về tính số cái bắt tay
Ảnh
Yêu cầu 2
Hàm h(n) ở Hình 3 là một ví dụ về đệ quy. Hình 4 liệt kê lần lượt 5 bước chương trình sẽ thực hiện khi lời gọi đến h(3) được thực thi.
Ảnh
Hình 4. Sơ đồ phân tích trình tự hoạt động của chương trình khi thực thi
Bài tập ứng dụng
Câu 1. Em hãy đọc chương trình ở Hình 5 và cho biết kết quả nhận được khi chạy chương trình .
Ảnh
Hình 5. Chương trình sử dụng ngôn ngữ lập trình Python
Bài tập ứng dụng
Hình vẽ
Câu 2. Dãy số Fibonacci được định nghĩa đệ quy như sau: - Phần cơ sở: F(n) = 0 nếu n = 0, f(n) = 1 nếu n = 1. - Phần đệ quy: F(n - 1) + F(n - 2) nếu latex(n geq 2). Hàm đệ quy F(n) cho trong Hình 6 sử dụng định nghĩa để quy ở trên để tính và trả về giá trị của F(n). a) Em hãy cho biết dấu (?) trong hàm để quy F(n) cần được thay bằng gì. b) Hình 7 liệt kê lần lượt 17 bước trong chương trình sẽ thực hiện khi lời gọi đếnF(4) được thực thi. Em hãy đưa ra giải thích bằng lời ý nghĩa của 17 bước đã cho.
Bài tập ứng dụng
Ảnh
Hình 6. Hàm đệ quy
Ảnh
Hình 7. Sơ đồ phân tích trình tự hoạt động của chương trình thực thi F(4).
Bài tập
Ứng dụng
Hình vẽ
Mẹ An là cô giáo dạy toán, muốn nhờ An in lời một bài toán dạy đếm số cho các em học sinh có định dạng như sau: Có 20 chiếc kẹo trong hộp các bạn ơi, ta lấy 1 chiếc ra ăn các bạn nhé. Vậy trong hộp còn 19 chiếc thôi. Có 19 chiếc kẹo trong hộp các bạn ơi, lấy ra 1 chiếc ăn các bạn nhé. Vậy trong hộp còn 18 chiếc thôi. ............................................................................................ Có 02 chiếc kẹo trong hộp các bạn ơi, ta lấy 1 chiếc ra ăn các bạn nhé .Vậy trong hộp còn một chiếc thôi. Còn duy nhất một chiếc kẹo trong hộp các bạn ơi, ta lấy nốt chiếc cuối cùng ra ăn các bạn nhé . Không còn chiếc kẹo nào trong hộp, ta cùng nhau đi mua thêm kẹo thôi nào. Em hãy giúp An viết Hàm đệ quy in_loi_bai_hat (n) với là số kẹo có thể in ra lời bài hát như trên nếu gọi hàm in_loi_bai_hat (20)
Ảnh
Câu hỏi
Hình vẽ
Trong những câu sau đây, câu nào đúng khi nói về hàm đệ quy. a) Trong hàm đệ quy chỉ được phép chứa duy nhất một lệnh gọi đến chính nó. b) Trong hàm đệ quy, trường hợp cơ sở không được phép tiếp tục gọi đệ quy. c) Hàm đệ quy là hàm mà thân hàm có chứa những lệnh gọi đến chính nó. d) Hàm đệ quy được sử dụng để cài đặt thuật toán đệ quy e) Trong hàm dệ quy có thể có nhiều hơn một trường hợp cơ sở. g) Hàm đệ quy không bao giờ dừng nếu không có trường hợp cơ sở.
Ảnh
Bài hoc
Tóm tắt
Hình vẽ
Tóm tắt bài học. 1. Đặc diểm của hàm đệ quy: * Trong hàm có một hoặc nhiều lệnh gọi đến chính nó. * Mỗi lần gọi đệ quy thì kích thước của bài toán được thu nhỏ hơn so với lần gọi trước. Khi đạt được trường hợp cơ sở thì không cần gọi đệ quy 2. Thuật toánđệ quy được cài đặt dưới dạng hàm đệ quy, để xử lí các đối tượng được định nghĩa đệ quy.
Cảm ơn
Thank you
Ảnh