BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 5)
3. Một số ví dụ về thuật toán
b. Bài toán tìm kiếm
Cho dãy A gồm N số nguyên khác nhau a1, a2,…, aN và 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ố 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.
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í = 5 có a5 = 2 = k
☞ Với k = 6 và dãy A gồm 10 số hạng như sau:
A | 5 | 7 | 1 | 4 | 2 | 9 | 8 | 11 | 25 | 51 | |
I | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
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.
BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 5)
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
Câu 1: Thuật toán tìm kiếm tuần tự trên dừng khi nào?
Câu 2: Có thể chuyển điều kiện i > n (bước 5) lên sau bước 2 được không ?
Nếu được cần thay đổi lại thuật toán liệt kê hoặc sơ đồ khối như thế nào ?
Luyện tập kiến thức:
Câu 1: Sửa thuật toán trên thành thuật toán đếm số lượng số k trong dãy A?
Câu 2: Trong trường hợp dãy A có một số phần tử có giá trị bằng k. Có thể tìm được nhiều vị trí xuất hiện số k được không ?
Nếu được cần thay đổi lại cách liệt kê và sơ đồ khối như thế nào ?
Câu 3: Nhà An ở trong căn hộ có 8 tầng, mỗi tầng có 8 căn hộ, các căn hộ được đánh số từ 1 đến 64. Một hôm các bạn trong lớp hỏi An:
“Nhà An ở căn hộ số mấy”.
An nói: Các bạn hãy thử hỏi một số câu, mình sẽ trả lời tất cả các câu hỏi của các bạn nhưng chỉ nói “đúng” hoặc “không” thôi. Qua các câu hỏi đó bạn hãy đoán xem An ở căn hộ bao nhiêu?
Trong lớp có nhiều bạn mỗi bạn có các câu hỏi khác nhau để tìm ra nhà An ở căn hộ nào? Cô giáo sẽ trao phần thưởng cho ai hỏi số câu hỏi ít nhất. Bạn hãy tìm ra cách hỏi để bạn có thể giành phần thưởng của cô giáo.
Bài tập củng cố:
1. Bài toán: Khái niệm, các yếu tố của bài toán.
CHỐT NỘI DUNG BÀI HỌC
2. Thuật toán: Khái niệm, các cách biểu diễn thuật toán
Thuật toán giải phương trình bậc hai (a ≠0).
Thuật toán tìm Max của một dãy số.
Thuật toán kiểm tra tính nguyên tố của một số nguyên dương.
Thuật toán sắp xếp bằng tráo đổi.
Thuật toán tìm kiếm tuần tự.
3. Cách trình bày thuật toán của một số bài toán cơ bản thường gặp: