Bài giảng Tin học Lớp 10 - Bài 4: Bài toán và thuật toán - Trường THPT Giao Thủy C

 Xin kính chào qúy thầy cô 
 ớ
và các bạn học sinh l p 10a2 Bình
Bơng Bơng
 An Bài 4: Bài tốn và thuật tốn
 (tiết 11 )
Thuật tốn tìm kiếm tuần tự Thuật tốn tìm kiếm tuần tự
BàiInput: tốn:Dãy Cho A dãygồm A N gồm số nguyên N số nguyên khác nhau:khác 
 nhau:A1, A 2A, ,1, A A2, ,N và A mộtN và số một nguyên số nguyên K. K. 
CầnOutput: biết cĩ Chỉ hay số khơng i (1<=i<=N) chỉ số imà (1<=i<=N) Ai = K hoặc 
màthơng A = báo K. Nếukhơng cĩ cĩ hãy số cho hạng biết nào chỉ của số đĩ.
 i Input
 dãyXác A định cĩ giá bài trị tốn: bằng K. Output Bài tốn tìm kiếm tuần tự
Với N=10, dãy A gồm 10 số hạng sau: 5, 7, 1, 4, 2, 9, 
8, 11, 25, 51 và K = 2 
 A1 = 5A 2 3 = 21A = 2 = 2
 A 5 7 1 4 2 9 8 11 25 51
 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10
 i 1 2 3 4 5 - - - - -
 i
 Vậy K thuộc A và chỉ số i cần tìm là 5. Bài tốn tìm kiếm tuần tự
Với N=10, dãy A gồm 10 số hạng sau: 5, 7, 1, 4, 2, 9, 
8, 11, 25, 51 và K = 6 
 A = 1 6
 A1 = 5A 6A4 = 4 5 7 =A6 88 = = 2A6510 6
 A 5 7 1 4 2 9 8 11 25 51
 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10
 i 1 2 3 4 5 6 7 8 9 10 11
 i
 K khơng thuộc A. Thuật tốn tìm kiếm tuần tự
Ý tưởng: 
- Lần lượt đi từ số hạng thứ nhất, ta so sánh giá trị của số hạng 
đang xét với khố K. 
- Nếu gặp một số hạng của dãy A cĩ giá trị bằng K thì ta đưa ra vị 
trí của số hạng đĩ.
- Nếu xét đến số hạng cuối cùng mà khơng cĩ số hạng nào cĩ giá 
trị bằng K thì thơng báo K khơng thuộc dãy A. Thuật tốn tìm kiếm tuần tự
 Nhiệm vụ các nhĩm: 
Nhĩm 1, 3: Xây dựng thuật tốn 
cho bài tốn theo phương pháp 
liệt kê.
Nhĩm 2, 4: Xây dựng thuật tốn 
cho bài tốn theo phương pháp sơ 
đồ khối. Thuật tốn theo phương pháp liệt kê:
Bước 1: Nhập N, các số hạng a1, a2, .. ,aN và giá trị 
khĩa 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 K khơng thuộc dãy 
A, rồi kết thúc.
Bước 6: Quay lại bước 3. Nhập N, a1, a2 ,..., aN 
 và K
 i = 1
 Đ
 Đưa ra giá trị của 
 ai = K ?
 i rồi kết thúc
 S
 i = i + 1
S
 i > N ?
 Đ
 Thơng báo K khơng thuộc A rồi 
 kết thúc