Giáo án điện tử chuyên đề Khoa học máy tính 11 cánh diều Bài 2: Kĩ thuật đệ quy trong chia để trị

CHÀO MỪNG CÁC EM ĐẾN VỚI

BÀI HỌC NGÀY HÔM NAY!

KHỞI ĐỘNG

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 trên một ví dụ trong Hì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.

BÀI 2: KĨ THUẬT ĐỆ QUY TRONG CHIA ĐỂ TRỊ

NỘI DUNG BÀI HỌC

1

Cài đặt thuật toán tìm kiếm nhị phân bằng đệ quy

2

Bài toán Tính an

PHẦN 1. CÀI ĐẶT THUẬT TOÁN TÌM KIẾM NHỊ PHÂN BẰNG ĐỆ QUY

Đọc nội dung và trả lời câu hỏi: Thuật toán tìm kiếm nhị phân được mô tả chi tiết như thế nào?

CÁC BƯỚC THỰC HIỆN

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.

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.

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ử giữa của dãy số.
• 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.

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ố.
• 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 trái này.

Bước 3

Bước 4

Chức năng hoạt động hoàn toàn giống nhau, chỉ khác ở phạm vi hoạt động

Nghiên cứu sách chuyên đề học tập và trả lời câu hỏi Hoạt động 1 trang 31:

Hoạt động 1

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.

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

KẾT LUẬN

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.

Phần 2. Bài toán tính an

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 310. 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 để trị, Thanh An nghĩ ra cách để giảm bớt số phép nhân. Thanh An thấy rằng 310 = 35 x 35(Hình 2) nên chỉ cần một lần tính 35 và bình phương giá trị đó lên thì số phép nhân phảisử dụng giảm đi đáng kể. Tuy nhiên, với 35 thì Thanh An lại chưa nghĩ ra được cách chia đôi ra để giảm bớt số phép nhân do 5 là số lẻ.

Hoạt động 2

Em hãy giúp Thanh An mô tả chi tiết các bước tính giá trị 310 với số phép tính nhân phải sử dụng là ít nhất.

CÁC TRƯỜNG HỢP

an = an/2 x an/2, nếu n chẵn.

an = a x an-1 nếu n lẻ và n > 1.

Hình 3. Cách tính 310 dùng chia để trị có số phép tính nhân là ít nhất

KẾT LUẬN

Bài toán tính an được giải hiệu quả bằng kĩ thuật đệ quy trong phương pháp chia để trị nhờ việc xét trường hợp n chẵn và n lẻ.

Mô tả chi tiết tính an­ dùng chia để trị mà sử dụng số phép tính nhân là ít nhất. Viết hàm đệ quy tính an. Sau đó, viết chương trình nhập vào hai số nguyên dương a, n và hiển thị giá trị của an.

THỰC HÀNH

LUYỆN TẬP

Câu 1: Bước đầu tiên trong mô tả thuật tìm kiếm nhị phân là gì?

A. So sánh x với phần tử nằm ở vị trí giữa dãy số.

B. Nếu x bằng giá trị phần tử giữa, đưa ra vị trí phần tử tìm được.

C. Nếu x lớn hơn giá trị phần tử giữa, quay lại áp dụng thuật toán.

D. Nếu x nhỏ hơn giá trị phần tử giữa, quay lại áp dụng thuật toán.

A. So sánh x với phần tử nằm ở vị trí giữa dãy số.

Câu 2: Bài toán tính an giải hiệu quả bằng kĩ thuật đệ quy trong phương pháp chia để trị. Khi giải bài toán bằng cách này cần lưu ý điều gì?

A. Xét trường hợp n và n -1.

B. Công thức chung: an = a x an-1.

C. Công thức chung: an = an/2 x an/2.

D. Xét trường hợp n chẵn và n lẻ.

D. Xét trường hợp n chẵn và n lẻ.

Câu 3: Nếu sử dụng phương pháp chia để trị để tính 421 thì cần ít nhất bao nhiêu phép tính nhân?

A. 4.

B. 5.

C. 6.

D. 7.

C. 6.

Câu 4: Dòng lệnh sau có nhiệm vụ gì?

A. Xác định vị trí i giữa t và p.

B. Kiểm tra nếu x bằng phần tử số i.

C. Nếu x nhỏ hơn phần tử số i, bỏ qua nửa bên phải, gọi đệ quy tìm kiếm nhị phân cho phần bên trái.

D. Nếu x lớn hơn phần tử số i, bỏ qua nửa bên trái, gọi đệ quy tìm kiếm nhị phân cho phần bên phải.

C. Nếu x nhỏ hơn phần tử số i, bỏ qua nửa bên phải, gọi đệ quy tìm kiếm nhị phân cho phần bên trái.

Câu 5: Nếu sử dụng phương pháp chia để trị để tính 211 thì cần ít nhất bao nhiêu phép tính nhân?

A. 4.

B. 5.

C. 6.

D. 7.

B. 5.

VẬN DỤNG

Bài tập phần vận dụng: 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ử A0, A1,…,An-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à Ai = x. Nếu không tìm thấy thì hàm này trả về -1.

1 def TKNP(A, t, p, x):

2 if t <= p:

3 #Xác định vị trí i giữa t và p

4 i = (t + p)//2

5 #Kiểm tra nếu x bằng phần tử thứ i

6 if A[i] == x:

7 if i == 0:

8 return 0 #Phần tử cần tìm Là 0

9 elif A[i-1]<x:

10 return i #Phần tử cần tìm là i

11 else:

12 #Bỏ qua nửa bên phải,

13 #gọi đệ quy TKNP cho phần bên trái

14 return TKNP (A, t, i-1, x)

15 return i

16 #Nếu x nhỏ hơn, bỏ qua nửa bên phải

17 #gọi đệ quy TKNP cho phần bên trái

18 elif A[i] > x:

19 return TKNP (A, t, i-1, x)

20 #Nếu x lớn hơn, bỏ qua nửa bên trái

21 #gọi đệ quy TKNP cho phần bên trái

22 else:

23 return TKNP(A, i+1, p, x)

24 else

25 #Không tồn tại phần tử cần tìm trong mảng

26 return -1

27 n, x = map(int, input().split())

28 A = list(map(int, input().split()))

29 #Gọi đệ quy

30 kq = TKNP(A, 0, len(A)-1, x)

31 if kq == -1:

32 print ("Không tồn tại phần tử có giá trị ",x)

33 else:

34 print ("Phần tử số ",kq, " có giá trị ", x)

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