Giáo án điện tử chuyên đề Khoa học máy tính 11 kết nối Bài 6: Ý tưởng và kĩ thuật chia để trị

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

NGÀY HÔM NAY!

KHỞI ĐỘNG

Hình 6.1. Cân thăng bằng

Có 5 viên bi giống hệt nhau, biết rằng trong các viên bi này có một viên bi giả và viên bi giả này nặng hơn các viên bi còn lại.

Chỉ cần một cái cân thăng bằng, em hãy tìm ra viên bi giả đó. Cần ít nhất bao nhiêu lần cân để tìm ra viên bi giả?

CHUYÊN ĐỀ 2: THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT CHIA ĐỂ TRỊ

BÀI 6.

Ý TƯỞNG VÀ KĨ THUẬT CHIA ĐỂ TRỊ

NỘI DUNG BÀI HỌC

1

Ý tưởng chia để trị

2

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

PHẦN 1. Ý TƯỞNG CHIA ĐỂ TRỊ

Hoạt động 1

Tìm hiểu ý tưởng của kĩ thuật chia để trị để giải một bài toán

• Hãy trình bày cách giải bài toán tìm bi giả với 5 viên bi.
• Trường hợp tổng quát có n viên bi cách làm như thế nào?
• Ý tưởng chia để trị để giải bài toán tìm bi giả được thể hiện như thế nào?

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

1

Với 5 viên bi, lần cân đầu tiên chúng ta lấy 4 viên bi, đặt 2 viên bi ở hai bên cân.

Trường hợp 1: Nêu cân thăng bằng thì xác định được viên bi còn lại chưa cân là bi giả.

Trường hợp 2: Nêu cân bị lệch, ta sẽ xác định bên nặng hơn chứa bi giả. Lấy hai viên bi ở bên nặng hơn và cân mỗi bên một viên, ta sẽ xác định được viên bi giả.

2

Tổng quát:

• Sau một lần cân, từ bài toán n viên bi sẽ dẫn đến bài toán với [n/2] viên bi.
• Khi bài toán dẫn đến còn hai hoặc ba viên bi thì chỉ cần một lần cân nữa sẽ tìm được viên bi giả.

3

Từ bài toán gốc luôn chia thành các bài toán có kích thước nhỏ hơn, ở đây là [n/2]. Khi số bi còn lại là 2 thì bài toán rất đơn giản để có thể giải quyết ngay, đó là trị. Sau khi trị xong, kết hợp lại cả quá trình để tổng hợp kết quả chung sẽ giải quyết được bài toán gốc.

KẾT LUẬN

Bài toán P

Lời giải bài toán P

Bài toán con P1

Bài toán con P2

Bài toán con Pk

Lời giải P1

Lời giải P2

Lời giải Pk

…

…

Bước chia – Chia nhỏ bài toán thành các bài toán con

Bước kết hợp – Kết hợp các lời giải của các bài toán con

Bước trị – Giải các bài toán con

CHIA ĐỂ TRỊ

chia (divide)

trị (conquer)

kết hợp (combine)

• Bài toán gốc sẽ được chia thành các bài toán với kích thước nhỏ hơn, sau đó sẽ trị các bài toán với kích thước nhỏ hơn, cuối cùng kết hợp các kết quả để giải quyết bài toán ban đầu.
• Thường sử dụng kĩ thuật đệ quy ở bước chia (divide) và bước trị (conquer).

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

Câu 1: Với n = 9, bài toán tìm bi giả cần tối đa bao nhiêu lần cân?

Câu 2: Mô tả bước "kết hợp" của bài toán 9 viên bi trên.

HƯỚNG DẪN TRẢ LỜI

1

Với 9 viên bi, số lần cân tối đa là 3 lần.

2

Mô tả chi tiết cách cân của 9 viên bi.

Bước 1: Phân tách số bi thành 4 + 4 + 1 và cân 2 nhóm 4 viên. Nêu cân cân bằng thì tìm ngay 1 viên bi kia là bi giả. Nếu cân không cân bằng thì lấy ra 4 viên bên nặng hơn và thực hiện tiếp

Bước 2. Thực hiện tiếp đệ quy giải bài toán với 4 viên bi đã chọn. Kết quả của bước này sẽ tìm được ngay viên bi giả.

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

Hoạt động 2

Tìm hiểu kĩ thuật chia để trị thông qua tìm kiếm nhị phân

Quan sát lại một lần nữa thuật toán tìm kiếm nhị phân trên dãy các phần tử đã sắp xếp và liên hệ với phương pháp chia để trị.

Cho trước dãy A gồm n phần tử đã được sắp xếp theo thứ tự tăng dần:

A[0] ≤ A[1] ≤ … ≤ A[n-1]

Cho trước giá trị cần tìm K. Cần tìm chỉ số k của dãy A sao cho A[k] = K. Nếu tìm thấy trả về k, nếu không thấy trả về -1.

BÀI TOÁN GỐC

• Thuật toán tìm kiếm nhị phân được mô tả bởi hàm đệ quy binarySearch(A, left, right, K) như sau:

Thuật toán tìm kiếm nhị phân là một triển khai của kĩ thuật chia để trị của bài toán tìm kiếm trên dãy các phần tử đã sắp xếp.

KẾT LUẬN

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

Câu 1: Trong thuật toán tìm kiếm nhị phân trên, phần cơ sở là các lệnh nào?

Câu 2: Mô tả các bước thực hiện thuật toán tìm kiếm nhị phân khi left = right.

HƯỚNG DẪN TRẢ LỜI

1

Phần cơ sở là các lệnh tại dòng 10,11.

2

Trường hợp left = right các bước thực hiện như sau:

Bước 1. Tính mid = left.

Bước 2. Nếu A[mid] = K thì trả về mid.

Bước 3. Nếu A[mid] ≠ K thì;

• Bước 3.1. Nếu mid < K thì gọi đệ quy đến A [mid + 1..right] và trả về -1.
• Bước 3.2. Nếu mid > K thì gọi đệ quy đến A [left..mid – 1] và trả về -1.

Hoạt động 3

Tìm hiểu kĩ thuật chia để trị thông qua tìm kiếm nhị phân

Đọc, quan sát phân tích sau để biết được tính vượt trội của tìm kiếm nhị phân với tìm kiếm tuần tự, biết được vai trò của kĩ thuật chia để trị trong thiết kế thuật toán.

• Công thức tổng quát:

T(n) = T(n/2) + O(1)

Từ các công thức (1) và (2) có thể chứng minh được T(n) = O(logn).

Theo công thức (2) ta có:

T(n) = T(2k) = T(2k-1) + C

T(1) = C (1)

T(n) = T(n/2) + C (2)

Vậy không mất tổng quát có thể giả thiết tồn tại hằng số C sao cho:

= T(2k-2) + C + C = T(2k-2) + 2C = …

= T(20) + kC // theo công thức (1)

= (k+1)C

= C.k + C = C.log2n + C = O(log2n).

T(n) = T(2k) = T(2k-1) + C

Thuật toán tìm kiếm nhị phân có độ phức tạp thời gian O(logn), tốt hơn hẳn so với tìm kiếm tuần tự với thời gian chạy là O(n)

KẾT LUẬN

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

Câu 1: Tìm chính xác số phép toán đơn cần thực hiện trong thuật toán tìm kiếm nhị phân nếu dãy gốc chỉ có 1 phần tử.

Câu 2: Tìm số phép toán đơn cần thực hiện trong thuật toán trên nếu dãy có 2 phần tử.

HƯỚNG DẪN TRẢ LỜI

1

Nếu dãy gốc có 1 phần tử thì số phép toán đơn tối đa là 4.

2

Trường hợp dãy gốc có 2 phần tử. Số phép toán đơn được tính như sau:

• Các dòng 2, 3, 4 mỗi dòng cần thực hiện 1 phép tính.
• Các dòng tiếp theo sẽ gọi đệ quy tại dòng 7, 9 sẽ sử dụng nhiều nhất là 4 phép tính nữa.

LUYỆN TẬP

Bài 1. Viết chương trình hoàn chỉnh nhập một dãy số đơn điệu tăng từ bàn phím, các số cách nhau bởi dấu cách. Sau đó, nhập số K bất kì từ bàn phím và thực hiện việc tìm kiếm số K trong dãy trên. Nếu tìm thấy thì trả lại chỉ số của phần tử có giá trị K, ngược lại trả về – 1.

Bài 2. Cho trước danh sách gồm có tên, điểm thi và được sắp xếp theo thứ tự tăng dần của điểm thi, ví dụ danh sách: [["Bình", 7.5], ["Hoa", 8], ["An", 9], ["Quang", 10]]. Viết chương trình nhập một điểm số và tìm tên học sinh có điểm thi bằng điểm số đã nhập, nếu không tìm thấy thì thông báo "không có".

1

Chương trình có thể như sau:

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