Giáo án điện tử chuyên đề Khoa học máy tính 11 kết nối Bài 2: Thiết kế thuật toán đệ quy

XIN CHÀO CÁC EM!

MỜI CÁC EM ĐẾN VỚI

BÀI HỌC MỚI!

KHỞI ĐỘNG

An được giao tìm một thiết kế mới cho bài toán tính tổng S(n)= 1+2 +..+n

An nhận thấy S(n) có thẻ được viết như sau:

S(n)=1+2+..+n=1+2+..+n-1+n=S(n-1)+n

Do đó, việc tính S(n) có thể được tính từ S(n - 1), tương tự S(n - 1) lại có thể được tính từ S(n - 2), cứ như vậy, cuối cùng sẽ dẫn đến cần tính S(0), nhưng S(0) = 0.

Em có thể giúp An hoàn thiện ý tưởng trên thành một chương trình hay không?

BÀI 2

THIẾT KẾ THUẬT TOÁN BẰNG ĐỆ QUY

NỘI DUNG BÀI HỌC

Ý tưởng thiết kế theo kĩ thuật đệ quy

1

Thuật toán tìm kiếm nhị phân

2

Ý TƯỞNG THIẾT KẾ

THEO KĨ THUẬT ĐỆ QUY

1

Hoạt động 1

Tìm hiểu ý tưởng thiết kế thuật toán theo kĩ thuật đệ quy

HƯỚNG DẪN THỰC HIỆN

1

2

3

Vì sao lại thiết kế lập trình đệ quy, các ví dụ này có những điểm gì giống nhau.

Điểm chung

Từ bài toán góc có thẻ đưa về trường hợp có tham số đầu vào nhỏ hơn.

Có thể dùng Kĩ thuật đệ quy để gọi chính hàm gốc.

Nếu với các dữ liệu đầu vào nhỏ có thẻ giải trực tiếp thì phản cơ sở của đệ quy sẽ thực hiện lời giải trực tiếp này.

• Trong cả ba chương trình trên, các hàm được định nghĩa với tham số n mặc định phải thoả mãn n > 0.
• Do đó, các hàm này không cần có lệnh điều khiển dừng tường minh.
• Nhóm các lệnh cơ sở sẽ làm luôn chức năng kiểm soát đùng của lặp đệ quy.

• Hãy chỉ ra phần cơ sở và phần đệ quy của các chương trình trên.
• Vì sao trong ý tưởng thiết kế đệ quy trên, yêu cầu từ bài toán với kích thước lớn cần phải đưa về cùng bài toán đó với kích thước nhỏ hơn?

Đọc thông tin và trả lời các câu hỏi sau đây:

HƯỚNG DẪN THỰC HIỆN

a) Phần cơ sở lệnh là 2,3, phần đệ quy là lệnh 5.

1

b) Phần cơ sở lệnh là 2,3, phần đệ quy là lệnh 5

c) Phần cơ sở lệnh là 2,3, phần đệ quy là lệnh 5.

HƯỚNG DẪN THỰC HIỆN

Vì trong tất cả các thuật toán đệ quy đều phải có yêu cầu bài toán có kích thước lớn hơn đưa về cùng bài toán đó với kích thước nhỏ hơn.

2

THUẬT TOÁN TÌM KIẾM NHỊ PHÂN

2

Hoạt động 2

Thiết kế thuật toán đệ quy cho bài toán tìm kiếm nhị phân

Chúng ta đã biết thuật toán tìm kiếm nhị phân trên dãy các phần tử đã sắp xếp. Hãy tìm thiết kế mới của thuật toán này theo kĩ thuật đệ quy. Trao đổi, thảo luận và trả lời các câu hỏi sau:

• Nêu ý tưởng chính của giải thuật tìm kiếm nhị phân sử dụng kĩ thuật đệ quy.
• Vị trí nào trong thuật toán có thể gợi ý cho kĩ thuật đệ quy?
• Phần cơ sở của thiết kế đệ quy nằm ở bước nào?

GỢI Ý

1

Ý tưởng chính của thuật toán tìm kiếm nhị phân:

A(left, right)

Left

Mid

right

Nếu A[mid] > K thì tìm kiếm tiếp tại đây:

A(left, mid – 1)

Nếu A[mid] < K thì tìm kiếm tiếp tại đây:

A(mid + 1, right)

Hình 2.1. Ý tưởng của thuật toán tìm kiếm nhị phân

Các bước thực hiện tìm kiếm nhị phân

Bước 1

Đầu tiên thiết lập các biến left = 0, right = len(A) - 1

Bước 2

Lặp liên tục cho đến khi left > right. Các bước lặp như sau:

Bước 2.1: Đặt mid = (left + right)//2.

Bước 2.2: Nếu A[mid] = K thì dừng chương trình, trả về giá trị mid.

Bước 2.3: Nếu A[mid] > K thì tìm tiếp trong dãy con bên trái: A(left, mid – 1)

Bước 2.4: Nếu A[mid] < K thì tìm tiếp trong dãy con bên phải: A(mid + 1, right)

Bước 3

Nếu left > right thì dừng chương trình, trả về giá trị -1.

2

Vị trí trong thuật toán gợi ý cho kĩ thuật đệ quy:

Bước 2.1: Đặt mid = (left + right)//2.

Bước 2.2: Nếu A[mid] = K thì dừng chương trình, trả về giá trị mid.

Bước 2.3: Nếu A[mid] > K thì tìm tiếp trong dãy con bên trái: A(left, mid – 1)

Bước 2.4: Nếu A[mid] < K thì tìm tiếp trong dãy con bên phải: A(mid + 1, right)

Thực hiện việc đưa bài toán tìm kiếm về chính bài toán đó với kích thước dãy ban đầu.

Lệnh gọi đệ quy sẽ thực hiện tại các bước này

Bước 3

Nếu left > right thì dừng chương trình, trả về giá trị -1.

3

Bước 3 đóng vai trò phần cơ sở của đệ quy, khi độ dài của dãy cần tìm kiếm bằng 0 thì chương trình sẽ dừng lại và thông báo không tìm thấy.

KẾT LUẬN

1. Trong chương trình trên lệnh nào đóng vai trò là phần cơ sở của đệ quy?

2. Giả sử A = [1, 3, 7, 9] và K= 10. Nếu áp dụng chương trình trên thì cần mấy lần gọi hàm đệ quy?

Đọc thông tin và trả lời các câu hỏi sau đây:

HƯỚNG DẪN THỰC HIỆN

1

Phần cơ sở nằm ở các lệnh 10, 11 khi left > right, khi dãy rỗng.

2

Nếu A = [1,3,7, 9], K = 10 thì lời gọi hàm tìm kiếm nhị phân sẽ gọi đệ quy ba lần.

• Lần 1, hàm sẽ gọi đệ quy đến đãy [7, 9].
• Lần 2, hàm sẽ gọi đệ quy đến dãy [9].
• Lần 3, hàm sẽ gọi đệ quy đến dãy [].

LUYỆN TẬP

• Câu 1. Viết chương trình theo kĩ thuật đệ quy để tính hàm SL(n) là tổng các số tự nhiên lẻ nhỏ hơn hoặc bằng n.
• Câu 2. Cho trước dãy A. Viết chương trình theo kĩ thuật đệ quy để in dãy A theo thứ tự ngược lại.

KẾT QUẢ

--------------- Còn tiếp ---------------