Tiet 13

Thuật toán tìm kiếm
Hai bạn chó (Bi và Bông) chơi trốn tìm, Bông đã trốn vào một trong những chiếc mũ của ông già Nôen trên. Hãy chỉ ra các cách tìm chiếc mũ mà Bông đang trốn? Cho biết có những cách nào?
Bông trốn đâu nhỉ ?
C1: Tìm kiếm tuần tự
( mở từng mũ)
C2: Do các mũ đã sắp xếp lớn dần, hai mũ đầu nhỏ hơn
người của Bông nên chỉ tìm hai mũ sau thôi!
Thuật toán tìm kiếm tuần tự
Xác định bài toán:
INPUT: Dãy A gồm N số nguyên a1, a2,., aN đôi
một khác nhau 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 A bằng k.
Bài toán: Dãy A gồm N số nguyên a1, a2,., aN đôi một khác nhau và số nguyên k. Có hay không
chỉ số i (1? i ? N ) mà ai = k. Nếu có hãy cho biết chỉ số đó
5
4
3
2
1
i
51
25
11
8
9
2
4
1
7
5
A
Mô phỏng thuật toán tìm kiếm tuần tự
? Với k = 2 và dãy A gồm 10 số hạng như sau:
Tại vị trí i = 5 có a5 = 2 = k
? Với k = 6 và dãy A gồm 10 số hạng như sau:
Với mọi i từ 1? 10 không có ai có giá trị bằng 6
5
ý tưởng:
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á (k) cho đến khi có sự trùng nhau, nếu đã xét tới số hạng cuối cùng mà không có sự trùng nhau thì có nghĩa là dãy A không có số hạng nào có giá trị bằng k.
Cách 1: Liệt kê các bước
Bước 1: Nhập N, các số hạng a1, a2,., aN
và giá trị 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 B3.
Nhập N, a1, a2,..., aN
và k
i ? 1
ai = k ?
Đưa ra i
rồi kết thúc
Đ
S
Đ
i ?i + 1
i > N ?
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
S
Cách 2
Vẽ sơ đồ khối