Nhập N và AN: a1, a2,..., aN
M  N
M < 2 ?
M  M - 1; i 0
i  i + 1
i > M ?
ai > ai+1 ?
Tráo đổi
ai và ai+1
Đưa ra AN đã sắp xếp


rồi kết thúc
Đ
Đ
Đ
S
S
S
....................
không giảm
3. Một số ví dụ về thuật toán
Ví dụ 3. Bài toán tìm kiếm
Tiết 4.5
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!
Xét bài toán tìm kiếm đơn giản:
Cho dãy A gồm N số 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á)
Làm thế nào để giải được bài toán này nhỉ ?
Có 2 cách ư chọn cách nào đây ?
Các em cần xây dựng
thuật toán tìm kiếm tuần tự
để giải bài toán này
Chỉ số i mà ai = k (1 ? i ? N) hoặc thông báo không có số hạng nào của A bằng k.
Dãy A gồm N số nguyên khác nhau a1, a2,?, aN và số nguyên k.
INPUT:
OUTPUT:
1. Xác định bài toán:
5
4
3
2
1
i
51
25
11
8
9
2
4
1
7
5
A
Ví dụ
? 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
2. ý 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.
3. Thuật toán:
Nhập N, a1, a2,..., aN
và k
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
i ? 1
ai = k ?
Đưa ra i
rồi kết thúc
Đ
S
Đ
i ?i + 1
i > N ?
S
Cách 2
Vẽ sơ đồ khối
3
2
1
i
13
21
6
8
9
5
A
S
Mô phỏng thuật toán: K = 8 và dãy
Kết thúc bài học