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
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
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.
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.
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
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.
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.
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
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
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.
Lời giải:
Bổ sung đoạn lệnh sau:
Vận dụng
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 đó.
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 lời giải bài tập Chuyên đề học tập Tin học lớp 11 Kết nối tri thức hay, chi tiết khác:
Bài 10: Thực hành giải toán bằng kĩ thuật chia để trị
Bài 12: Thực hành kĩ thuật duyệt cho bài toán tìm kiếm
