Nội Dung Chính
(Trang 48)
| Sau bài này em sẽ:
|
|
Để 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? |
1. Kĩ thuật duyệt trong bài toán tìm kiếm
| Hoạt động 1 Kĩ thuật duyệt trong bài toán tìm kiếm 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, 9.6] C = [8.3, 7.8, 8.9, 9.5, 9.3, 9.0] D = [7.9, 9.0, 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. |
Phần lớn các bài toán tìm kiếm trong thực tế đều có thể giải quyết bằng cách sử dụng kĩ thuật duyệt. Sau khi xác định được miền tìm kiếm, kĩ thuật duyệt sẽ lần lượt xét các dữ liệu trong miền tìm kiếm để đưa ra phần tử thoả mãn. Các bài toán tìm kiếm có thể:
– Đa dạng về yêu cầu tìm kiếm như tìm một nghiệm, tìm nghiệm theo yêu cầu, tìm nghiệm tối ưu, tìm tất cả các nghiệm,...
– Đa dạng về miền tìm kiếm như mảng 1 chiều, mảng 2 chiều, danh sách liên kết, dữ liệu chưa sắp xếp, dữ liệu đã sắp xếp,...
Tuỳ thuộc vào yêu cầu tìm kiếm, miền tìm kiếm, người ta thực hiện các kĩ thuật duyệt theo những cách khác nhau.
Ví dụ, với bài toán yêu cầu tìm kiếm một nghiệm, có thể xét những phần tử có nhiều khả năng nhất và dừng lại khi tìm thấy nghiệm đầu tiên. Với bài toán tìm nghiệm tối ưu hoặc tìm tất cả các nghiệm, chúng ta cần duyệt tất cả các phần tử trong miền tìm kiếm.
Với miền tìm kiếm là danh sách thông thường, chưa được sắp xếp, ta có thể thực hiện tìm kiếm tuần tự. Với miền tìm kiếm là danh sách đã được sắp xếp, ta có thể thực hiện thuật toán tìm kiếm nhị phân để tăng tốc độ tìm kiếm.
Trong yêu cầu a, của Hoạt động 1, 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 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í thì 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.
Trong yêu cầu b, của Hoạt động 1, 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.
Trong yêu cầu c, của Hoạt động 1, 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.
Chương trình mô tả thuật toán tìm kiếm theo ba yêu cầu trên có thể được thực hiện như sau:
1 A = ["Nam", "Sơn", "Hương", "Huyền", "Hà", "Hùng"]
2 B = [8.3, 8.4, 8.7, 8.9, 9.1, 9.6]
3 C = [8.3, 7.8, 8.9, 9.5, 9.3, 9.0]
4 D = [7.9, 9.0, 8.2, 9.5, 9.1]
5 kqa = ""
6 for i in range(0, len(A)):
7 if B[i] > C[i]:
8 kqa=A[i]
9 break
10 if len(kqa) > 0:
11 print("Tên một học sinh có điểm Toán lớn hơn điểm Vật lí là:", kqa)
12 kqb = []
13 for i in range(0, len(A)):
14 if C[i] > D[i]:
15 kqb.append(A[i])
(Trang 50)
16 if len(kqb) > 0:
17 print("Tên các học sinh có điểm Vật lí lớn hơn điểm Hoá là:", kqb)
18 kqc = []
19 for i in range(len(A)-1, -1, -1):
20 if B[i] >= 9:
21 if C[i] >= 9 and D[i] >= 9:
22 kqc.append(A[i])
23 else:
24 break
25 if len(kqb) > 0:
26 print("Tên các học sinh có cả ba điểm lớn hơn 9 là:", kqc)
| 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 tìm kiếm để xác định phần tử đó có thoả mãn điều kiện tìm kiếm hay không. Tuỳ vào yêu cầu tìm kiếm, miền tìm kiếm, người ta có thể thiết kế theo các cách khác nhau. |
1. So sánh số vòng lặp cần thực hiện các yêu cầu a, b, c trong ví dụ trên.
2. 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.
2. Tìm kiếm vét cạn
| Hoạt động 2 Khái niệm duyệt vét cạn 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. |
Tuỳ thuộc vào yêu cầu tìm kiếm, ta có thể duyệt một phần hoặc duyệt toàn bộ các phần tử trong miền tìm kiếm. Kĩ thuật duyệt toàn bộ dữ liệu trong miền tìm kiếm được gọi là duyệt vét cạn. Kĩ thuật duyệt vét cạn có thể áp dụng cho hầu hết các bài toán tìm kiếm trong tất cả các dạng. Chúng ta cùng quan sát và phân tích khả năng áp dụng kĩ thuật duyệt vét cạn cho các bài toán trên.
(Trang 51)
Bài toán 1. Miền tìm kiếm là toàn bộ các xâu nhị phân có độ dài n hay tập hợp các dãy kí tự có dạng s[0], s[1]...., s[n - 1], trong đó mỗi kí tự s[k] bằng "0" hoặc "1". Số lượng các dãy như vậy là 2n. Giá trị này quá lớn để có thể lưu dữ liệu vào một mảng 1 chiều hay 2 chiều. Do vậy sử dụng kĩ thuật duyệt vét cạn cho bài toán này là rất khó.
Bài toán 2. Miền tìm kiếm của bài toán là các dãy số A[0], A[1].....A[n - 1], với mỗi dãy là một hoán vị của [1, 2,..., n]. Số lượng các hoán vị là n!. là một số rất lớn. Do vậy cũng rất khó áp dụng kĩ thuật duyệt vét cạn cho bài toán này.
Hai bài toán trên là ví dụ cho lớp những bài toán thực tế khó có thể thực hiện kĩ thuật tìm kiếm thông thường, kể cả duyệt vét cạn.
| Tìm kiếm vét cạn là kĩ thuật duyệt trên toàn bộ miền tìm kiếm để giải quyết các yêu cầu đa dạng của các bài toán tìm kiếm. Tuy nhiên, có nhiều bài toán tìm kiếm dùng duyệt vét cạn cũng không hiệu quả. |
1. 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?
2. Một mảng hai chiều kích thước m x n thì duyệt vét cạn sẽ phải duyệt qua tổng số bao nhiêu phần tử?
3. 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?
LUYỆN TẬP
1. 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.
2. 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.
VẬN DỤNG
1. Cho trước dãy số n 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 đó mà mỗi phần tử là 3 số nguyên liên tiếp (có thể tăng dần hoặc giảm dần).
2. 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ó.
Các Bài Học Khác
Chuyên đề học tập Tin học 11 - Bài 12: Thực Hành Kĩ Thuật Duyệt Cho Bài Toán Tìm Kiếm - Áp dụng kĩ thuật duyệt giải quyết bài toán tìm bạn chung trên Facebook và gợi ý kết bạn.
Xem thêm ⟶
Chuyên đề học tập Tin học 11 - Bài 13: Kĩ Thuật Duyệt Quay Lui - Trình bày ý tưởng kĩ thuật quay lui qua bài toán mê cung và mô hình tổng quát, mối liên quan với đệ quy.
Xem thêm ⟶
Bình Luận
Để Lại Bình Luận Của Bạn