Chuyên đề Tin học 11 Bài 11 (Kết nối tri thức): Bài toán tìm kiếm theo kĩ thuật duyệt

Giải Chuyên đề Tin học 11 Bài 11: Bài toán tìm kiếm theo kĩ thuật duyệt

Khởi động trang 48 Chuyên đề Tin học 11: Để xác định một giá trị a có xuất hiện trong một dãy A cho trước hay không ta có thể áp dụng phương pháp tìm kiếm tuần tự: lần lượt so sánh a với từng phần tử trong A. Theo em, liệu có cách nào đề giải bài toán này trong trường hợp A là một dãy bất kì hay không?

Lời giải:

Các bài toán tìm kiếm có thể được giải quyết bằng cách sử dụng kĩ thuật duyệt. Kĩ thuật duyệt là lần lượt kiểm tra các phân tử trong miền tim kiếm để xác định xem phần tử đó có thoả mãn điều kiện tìm kiếm hay không. Tuy vào yêu cầu tìm kiếm, miền tìm kiếm mà kĩ thuật duyệt có thể được thiết kế theo các cách khác nhau.

1. Kĩ thuật duyệt trong bài toán tìm kiếm

Hoạt động 1 trang 48 Chuyên đề Tin học 11: Cho A, B, C, D lần lượt là các danh sách tên học sinh, điểm thi môn Toán, điểm thi môn Vật lí và điểm thi môn Hoá học. Danh sách điểm Toán được sắp xếp theo thứ tự tăng dần và các danh sách tên học sinh và điểm các môn còn lại được sắp xếp theo tương ứng

A = [“Nam”, “Sơn”, “Hương”, “Huyền”, “Hà”, “Hùng”

B = [8.3, 8.4, 8.7, 8.9, 9.1.96]

C= [ 8.3, 7.8, 8.9, 9.5, 9.3, 9.0]

D= [7.9, 9.0, 8.9, 8.2, 9.5, 9.1]

Hãy thảo luận về kĩ thuật tìm kiếm được thực hiện với mỗi yêu cầu sau:

a) Tìm một học sinh có điểm Toán lớn hơn điểm Vật lí.

b) Tìm tất cả các học sinh có điểm Vật lí lớn hơn điểm Hoá học.

c) Tìm tất cả các học sinh có cả 3 điểm đều lớn hơn hoặc bằng 9.

Lời giải:

a) Trong yêu cầu a, chỉ cần tìm một học sinh có điểm Toán lớn hơn điểm Vật lí nên có thể thực hiện tìm kiếm duyệt tuần tự từ học sinh đầu tiên trong dãy. Khi gặp học sinh có điểm Toán không lớn hơn điểm Vật lí thi tiếp tục duyệt học sinh tiếp theo. Khi gặp học sinh đầu tiên có điểm Toán lớn hơn điểm Vật lí thì dừng chương trình và in tên học sinh đó lên màn hình.

b) Trong yêu cầu b, cần tìm tất cả các học sinh có điểm Vật lí lớn hơn điểm Hoá học. Như vậy, ta cần duyệt tất cả các học sinh, ngay cả khi đã tìm thấy một học sinh có điểm Vật lí lớn hơn điểm Hoá học thì chương trình vẫn tiếp tục duyệt đề tìm ra tất cả học sinh thoả mãn điều kiện.

c) Trong yêu cầu c, do danh sách tên và điểm các môn khác được sắp xếp theo điểm Toán tăng dần nên ta có thể duyệt từ cuối dãy và dùng tìm kiếm khi gặp điểm Toán nhỏ hơn 9.

Câu hỏi 1 trang 50 Chuyên đề Tin học 11: So sánh số vòng lặp cần thực hiện để thực hiện các yêu cầu a, b, c trong ví dụ trên.

Lời giải:

Yêu cầu a có số vòng lặp nhỏ nhất, chỉ cần tìm được 1 học sinh phù hợp và kết thúc chương trình. Còn ở yêu cầu b, c thì cần duyệt tất cả các học sinh nên số vòng lặp sẽ lớn hơn.

Câu hỏi 2 trang 50 Chuyên đề Tin học 11: Phân tích và viết chương trình để thực hiện các yêu cầu sau:

a) Tìm học sinh có điểm Toán bằng 8.9.

b) Tìm một học sinh có tổng điểm ba môn Toán, Vật lí, Hoá học lớn hơn 26.5.

c) Tìm học sinh có tổng điểm ba môn Toán, Vật lí, Hoá học nhỏ nhất.

Lời giải:

a) Tìm học sinh có điểm Toán bằng 8.9.

Để tìm học sinh có điểm Toán bằng 8.9, ta có thể dùng hàm index() để tìm chỉ số của giá trị trong danh sách B, sau đó lấy tên của học sinh ở vị trí đó trong danh sách A.

b) Tìm một học sinh có tổng điểm ba môn Toán, Vật lí, Hoá học lớn hơn 26.5.

Để tìm một học sinh có tổng điểm ba môn Toán, Vật lí, Hoá học lớn hơn 26.5, ta có thể dùng vòng lặp for để duyệt qua danh sách điểm của từng học sinh và tính tổng điểm của ba môn. Nếu tổng lớn hơn 26.5 thì lấy tên của học sinh đó ở vị trí tương ứng trong danh sách A.

c) Tìm học sinh có tổng điểm ba môn Toán, Vật lí, Hoá học nhỏ nhất.

Để tìm học sinh có tổng điểm ba môn Toán, Vật lí, Hoá học nhỏ nhất, ta sẽ ghép các danh sách điểm thành một danh sách con, sau đó tính tổng điểm của từng học sinh và lấy tên học sinh có tổng điểm nhỏ nhất.

Kết quả là:

2. Tìm kiếm vét cạn

Hoạt động 2 trang 50 Chuyên đề Tin học 11: Với các bài toán sau, em hãy thảo luận với bạn để tìm kĩ thuật tìm kiếm đã học (tìm kiếm trên các mảng 1 hoặc 2 chiều) để giải.

1. Cho trước số tự nhiên n. Tìm và in ra tất cả các xâu nhị phân có độ dài n.

2. Viết chương trình tìm và liệt kê tất cả các hoán vị của tập hợp [1, 2, ..., n] với n là số tự nhiên cho trước.

Lời giải:

1. Để giải quyết bài toán tìm tất cả các xâu nhị phân có độ dài n, ta có thể sử dụng kỹ thuật duyệt vét cạn trên mảng một chiều có độ dài n. Với mỗi phần tử trong mảng, ta sẽ thử đặt giá trị 0 hoặc 1 vào đó và tiếp tục thử đặt giá trị cho các phần tử tiếp theo. Khi đã duyệt hết tất cả các phần tử trong mảng, ta sẽ có được một xâu nhị phân độ dài n. Quá trình này sẽ được lặp lại cho đến khi tất cả các xâu nhị phân độ dài n đã được tìm thấy.

2. Để giải quyết bài toán tìm tất cả các hoán vị của tập hợp [1, 2, ..., n], ta có thể sử dụng kỹ thuật đệ quy. Với mỗi số trong tập hợp [1, 2, ..., n], ta đưa số đó vào một mảng và gọi lại hàm đệ quy với tập hợp [1, 2, ..., n] đã loại bỏ số đó. Quá trình đệ quy sẽ được tiếp tục cho đến khi tất cả các số đã được sử dụng trong mảng, lúc đó ta sẽ có được một hoán vị của tập hợp [1, 2, ..., n]. Quá trình này sẽ được lặp lại cho đến khi tất cả các hoán vị của tập hợp [1, 2, ..., n] đã được tìm thấy.

Câu hỏi 1 trang 51 Chuyên đề Tin học 11: Tìm kiếm tuần tự trên một dãy n phần tử có phải là duyệt vét cạn hay không?

Lời giải:

Tìm kiếm tuần tự (linear search) trên một dãy n phần tử là một thuật toán duyệt vét cạn (brute force algorithm), bởi vì nó duyệt qua tất cả các phần tử của dãy cho đến khi tìm thấy phần tử cần tìm hoặc hết dãy. Thuật toán này không sử dụng bất kỳ phương pháp tối ưu nào để giảm bớt số lần so sánh, mà đơn giản là duyệt qua từng phần tử một, nên được gọi là duyệt vét cạn.

Câu hỏi 2 trang 51 Chuyên đề Tin học 11: Một mảng hai chiều kích thước m×n thi duyệt vét cạn sẽ phải duyệt qua tổng số bao nhiêu phần tử?

Lời giải:

Để duyệt vét cạn một mảng hai chiều kích thước m×n, ta sẽ cần duyệt qua từng phần tử của mỗi hàng và mỗi cột. Do đó, tổng số phần tử cần duyệt là:

m x n = số hàng x số cột

Câu hỏi 3 trang 51 Chuyên đề Tin học 11: Theo em, thuật toán tìm kiếm nhị phân có sử dụng duyệt vét cạn hay không?

Lời giải:

Thuật toán tìm kiếm nhị phân không sử dụng duyệt vét cạn. Thuật toán này áp dụng cách tiếp cận chia để trị để tìm kiếm phần tử cần tìm trong mảng đã sắp xếp. Nó chia mảng thành hai phần và so sánh giá trị cần tìm với phần tử ở giữa mảng. Nếu giá trị cần tìm nhỏ hơn phần tử ở giữa, thuật toán sẽ tìm kiếm trong nửa mảng bên trái. Ngược lại, nếu giá trị cần tìm lớn hơn phần tử ở giữa, thuật toán sẽ tìm kiếm trong nửa mảng bên phải. Thuật toán sẽ tiếp tục chia đôi mảng và tiếp tục tìm kiếm đến khi tìm thấy giá trị cần tìm hoặc không còn phần tử nào để tìm kiếm.

Luyện tập

Luyện tập 1 trang 51 Chuyên đề Tin học 11: Viết chương trình cho phép người dùng nhập một số nguyên dương N từ bàn phím rồi in ra số có nhiều ước số nhất trong các số nhỏ hơn N

Lời giải:

Để giải quyết bài toán này, ta có thể sử dụng hai phương pháp số lượng ước số: Tính số lượng ước số của các số nhỏ hơn N và chọn ra số có số lượng ước số lớn nhất.

Luyện tập 2 trang 51 Chuyên đề Tin học 11: Với bài toán trong Hoạt động 1, em hãy viết thêm các lệnh để tìm ra 3 học sinh có tổng điểm lớn nhất.

Lời giải:

Bổ sung đoạn lệnh sau:

Vận dụng

Vận dụng 1 trang 52 Chuyên đề Tin học 11: Cho trước dãy n số nguyên. Viết chương trình đếm và liệt kê tất cả các bộ 3 phần tử liền nhau của dãy thoả mãn điều kiện ba số này là 3 số nguyên liên tiếp (có thể tăng dần hoặc giảm dần).

Lời giải:

Để giải bài toán này, ta cần duyệt qua từng phần tử trong dãy và kiểm tra xem với mỗi phần tử đó, có thể tạo thành một bộ 3 liên tiếp thỏa mãn điều kiện hay không.

Với mỗi phần tử trong dãy, ta sẽ kiểm tra xem nó có tạo thành bộ 3 liên tiếp nào không bằng cách kiểm tra các phần tử kế tiếp. Nếu tìm thấy bộ 3 thỏa mãn điều kiện, ta sẽ tăng biến đếm số lượng bộ 3 tìm được và in ra bộ 3 đó.

Vận dụng 2 trang 52 Chuyên đề Tin học 11: Viết chương trình cho phép người dùng nhập một số nguyên dương N từ bàn phím, sau đó in ra toàn bộ các số hoàn hảo nhỏ hơn N. Số hoàn hảo là số có giá trị bằng tổng số các ước số của nó, không kể chính nó.

Lời giải:

Để giải quyết bài toán này, ta sẽ duyệt từng số nhỏ hơn N và kiểm tra xem số đó có phải là số hoàn hảo không. Để kiểm tra xem một số có phải là số hoàn hảo hay không, ta cần tính tổng các ước số của nó. Nếu tổng này bằng chính nó thì số đó là số hoàn hảo.

Xem thêm các bài giải Chuyên đề Tin học 11 sách Kết nối tri thức hay, chi tiết khác:

Bài 12: Thực hành kĩ thuật duyệt cho bài toán tìm kiếm

Bài 13: Kĩ thuật duyệt quay lui

Bài 14: Thực hành kĩ thuật duyệt quay lui

Bài 15: Bài toán xếp hậu

Bài 16: Thực hành thiết kế thuật toán theo kĩ thuật quay lui