Tìm kiếm là việc thường xảy ra trong cuộc sống, chẳng hạn cần tìm cuốn sách giáo khoa Tin học lớp 10 trên giá sách, cần tìm một học sinh trong danh sách 1 lớp học,… Nói một cách tổng quát là cần tìm một đối tượng cụ thể nào đó trong tập các đối tượng cho trước.
Dưới đây ta chỉ xét bài toán đơn giản sau:
Cho dãy A số N nguyên khác nhau: a1, a2,… aN và một số nguyên k. Cần biết có hay không chỉ số i (1≤ i ≤ N) mà ai=k. Nếu có hãy cho biết chỉ số đó.
Số nguyên k được gọi là khoá tìm kiếm(gọi tắt là khoá).
Ví dụ, cho dãy A gồm các số 5,7,1,4,2,9,8,11,25,51.
Với khoá k=2, trong dãy trên có số hạng a5 có giá trị bằng k. Vậy chỉ số cần tìm là i=5;
Với khoá k=6 thì không có số hạng nào của dãy A có giá trị bằng k.
Xác định bài toán:
Input: Dãy A gồm N số nguyên khác nhau a1,a2 … aN và số nguyên k;
Output: Chỉ số I mà ai=k hoặc thông báo không có số hạng nào của dãy A có giá trị bằng k.
Ý tưởng: Tìm kiếm tuần tự được thực hiện một cách ngẫu nhiên. Lần lượt từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khoá cho đến khi hoặc gặp một số hạng bằng khoá hoặc dãy đã được xét hết và không có giá trị nào bằng khoá. Trong trường hợp thứ hai dãy A không có số hạng nào bằng khoá.
Cách liệt kê
Bước 1: Nhập N, các số hạng a1, a2,…aN và khoá k;
Bước 2: i←1;
Bước 3: Nếu ai =k thì thông báo chỉ số i, rồi kết thúc
Bước 4: i ← i + 1
Bước 5: Nếu i> N thì thông báo dãy A không có số hạng nào có giá trị bằng k rồi kết thúc;
Bước 6: Quay lại bước 3.
Ghi chú: Trong thuật toán trên, i là biến chỉ số và nhận giá trị nguyên lần lượt từ 1 đến N+1.
b) Sơ đồ khối
Nhập N và a1,a2,…aN;k
i← 1
ai = k
Đưa ra i rồi kết thúc
Đúng
Sai
i← i + 1
i> N ?
Đúng
Thông báo dãy A không có số
hạng có giá trị bằng k rồi kết thúc
Sai
Dưới đây là một số ví dụ mô phỏng việc thực hiện thao tác trên
k=2 và N=10
Với i=5 thì a5=2
k=6 và N=10
Với mọi i từ 1 đến 10 không có
ai có giá trị bằng 6
Xác định bài toán:
Input: Dãy A là dãy tăng gồm N số nguyên khác nhau a1,a2, … aN và một số nguyên k;
Output: Chỉ số I mà ai=k hoặc thông báo không có số hạng nào của dẵy A có giá trị bằng k.
Ý tưởng: Sử dụng tính chất dãy A là dãy tăng, ta tìm cách thu hẹp nhanh phạm vi tìm kiếm sau mỗi lần so sánh với số hạng được chọn. Để làm điều đó, ta chọn số hạng aGiua ở “giữa dãy” để so sánh với k, trong đó Giua=[ (N+1)/2 ]
Khi đó, chỉ xảy ra 1 trong 3 trường hợp sau đây:
Nếu aGiua=k thì Giua là chỉ số a cần tìm. Việc tìm kiếm kết thúc.
Nếu aGiuaNếu aGiuaQuá trình trên sẽ được lặp đi lặp lại một số lần đến khi hoặc đã tìm thấy khoá k trong dãy A hoặc phạm vi tìm kiếm bằng rỗng
Cách liệt kê
Bước 1: Nhập N, các số hạng a1, a2,…aN và khoá k;
Bước 2: Dau ← 1, Cuoi ← N
Bước 3: Giua ← [ (Dau+Cuoi)/2]
Bước 4: Nếu aGiua=k thì thông báo chỉ số Giua, rồi kết thúc;
Bước 5: Nếu aGiua >k thì đặt Cuoi = Giua -1, rồi chuyến đến bước 7;
Bước 6: Dau ← Giua +1;
Bước 7: Nếu Dau> Cuoi thì thông báo dãy A không có số hạng bằng k, rồi kết thúc;
Bước 8: Quay lại bước 3.
Ghi chú: Tuỳ thuộc aGiua> k hoặc aGiua< k mà chỉ số đầu hoặc chỉ số cuối của dãy ở bước tìm kiếm tiếp theo sẽ thay đổi. Để thực hiện điều đó, trong thuật toán chỉ sử dung các biến nguyên tương ứng Dau và Cuoi có giá trị khởi tạo Dau =1 và Cuoi+N
b) Sơ đồ khối
Nhập N và a1,a2,…aN;k
Dau← 1;Cuoi ←N
aGiua = k ?
Đưa ra Giua
rồi kết thúc
Đúng
Sai
Cuoi← Giua - 1
aGiua>k
Đúng
Thông báo dãy A không có số
hạng có giá trị bằng k rồi kết thúc
Sai
Giua← [(Dau + Cuoi)/2]
Dau← Giua + 1
Dau> Cuoi
Sai
Đúng
Dưới đây là ví dụ mô phỏng việc thực hiện thuật toán trên
k=21 và N=10
Ở lần duyệt thứ 3 thì aGiua=k.
Vậy chỉ số cần tìm là i=Giua=6
Dưới đây là ví dụ mô phỏng việc thực hiện thuật toán trên
k=25 và N=10
Tại lần duyệt thứ 5 Dau> Cuoi nên kết luận trong dãy A không có số hạng nào là 25 cả.
Nguyễn Hoàng Ngân Quỳnh
Nguyễn Thái Việt
Nguyễn Mai Anh
Trương Hương Thảo
Lê Thị Hoà
Trần Huỳnh Linh Giang
Nguyễn Yên Bình

CẢM ƠN THẦY CÔ VÀ CÁC BẠN