KHÁNH AN
TRƯỜNG THPT

TIN HỌC 10
Đặng Hữu Hoàng
Kiểm tra bài cũ
Bài toán: Cho dãy A gồm N số nguyên a1, a2,….,aN. Hãy viết thuật toán sắp xếp các số hạng trong dãy A trở thành dãy không giảm (tức là số hạng trước không lớn hơn số hạng sau).
Xác định bài toán:
Input = ?
Output = ?
Số nguyên dương N và dãy số nguyên a1,..,aN
Dãy A được sắp xếp thành dãy không giảm
B1: Nhập N và dãy a1,…, aN.
B2: Gán M:=N.
B3: Nếu M<2 thì dãy A đã được sắp xếp rồi kết thúc.
B4:Gán M:=M-1, i:=0
B5: Gán i:=i+1;
B6: Nếu i>M thì quay lại B3
B7: Nếu ai>ai+1, thì đổi ai và ai+1
B8: Quay lại B5.
Thuật toán
CHƯƠNG 1: MỘT SỐ KHÁI NIỆM CƠ BẢN CỦA TIN HỌC
BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN
III. Một số ví dụ về thuật toán
BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 5)
Ví dụ: cho dãy A gồm các số: 5, 7, 1, 4, 2, 9, 8, 11, 25, 51.
Với k = 2 ?
Với k = 6 ?
Hãy xác định bài toán:
 Input = ?
 Output = ?
Dãy A gồm N số nguyên đôi một khác nhau a1, a2,..., aN và số nguyên k;
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.
 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à 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ó dãy cho biết chỉ số đó.
III. Một số ví dụ về thuật toán
BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 5)
Ví dụ: hãy tìm kiếm trong dãy:N=10 gồm 5, 7, 1, 4, 2, 9, 8, 11, 25, 51 và K=2
5
7
1
4
2
9
8
11
25
51
i=1
i=2
i=3
i=4
i=6
i=5
i=7
i=8
i=9
i=10
K=2
Xuất ra màn hình tại vị trí i =5 và kết thúc thuật toán
K=6
Dãy số không tìm thấy giá trị K=6 và kết thúc
K=6
lần lượt ta so sánh số hạng thứ nhất đến thứ hạng cuối với khóa k. có hai trường hợp là tìm thấy giá trị bằng khóa k và không bằng khóa k
BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 5)
Bài toán tìm kiếm tuần tự: 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ó dãy cho biết chỉ số đó.là số hạng trước không lớn hơn số hạng sau.
III. Một số ví dụ về thuật toán
 Ý tưởng:
III. Một số ví dụ về thuật toán
BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 5)
Thuật toán tìm kiếm tuần tự
B1: Nhập N, các số hạng a1, a2,..., aN và khoá k;
B2: i ← 1;
B3: Nếu ai = k thì thông báo chỉ số i, rồi kết thúc;
B4: i ← i + 1;
B5: 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;
B6: Quay lại bước 3.
Nhập N và dãy a1,..,aN, K
i←1
ai=k ?
Đưa i ra
màn hình
Đúng
Sai
i>N ?
i ←i+1
Đúng
Dãy A không có số hạng
có giá trị K rồi kết thúc
sai
 Liệt kê
Sơ đồ khối (SGK)
III. Một số ví dụ về thuật toán
BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 5)
Ví dụ: hãy tìm kiếm trong dãy:N=7 gồm 5, 7, 1, 4, 2, 9, 8 và K=2
5
7
1
4
2
9
8
i=1
i=2
i=3
i=4
i=5
K=2
Xuất ra màn hình tại vị trí i =5 và kết thúc thuật toán
B1: Nhập N, các số hạng a1, a2,..., aN và khoá k;
B2: i ← 1;
B3: Nếu ai = k thì thông báo chỉ số i, rồi kết thúc;
B4: i ← i + 1;
B5: 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;
B6: Quay lại bước 3.
N=7
K=6
III. Một số ví dụ về thuật toán
BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 5)
Ví dụ: hãy tìm kiếm trong dãy:N=7 gồm 5, 7, 1, 4, 2, 9, 8 và K=6
5
7
1
4
2
9
8
i=1
i=2
i=3
i=4
i=6
i=5
i=7
K=6
Không có số hạng nào của dãy A có giá trị bằng K=6 và kết thúc
B1: Nhập N, các số hạng a1, a2,..., aN và khoá k;
B2: i ← 1;
B3: Nếu ai = k thì thông báo chỉ số i, rồi kết thúc;
B4: i ← i + 1;
B5: 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;
B6: Quay lại bước 3.
N=7
i=8
Củng cố kiến thức
Bài toán tìm kiếm tuần tự
Input, Output của bài toán?
Ý tưởng thuật toán
Hãy viết thuật toán bằng sơ đồ khối hoặc liệt kê?
BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 5)
Dặn dò bài mới
CHÚC CÁC EM HỌC TỐT
- Học sinh về học bài.
- Xem trước các bài tập 1, 2, 3, 4,…., 6, 7 trang 44 (SGK)