Bài giảng Tin học Lớp 10 - Bài 4: Bài toán và thuật toán

rù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 a 1 , a 2 ,, a N  và giá trị khoá k; 
 Bước 2: i  1; 
 Bước 3: Nếu a i = 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, a 1 , a 2 ,..., a N 
 và k 
i  1 
a i = 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 
Thuật toán tìm kiếm nhị phân 
ý tưởng:  Sử dụng tính chất dãy A đã sắp xếp tăng, ta tìm cách thu hẹp nhanh phạm vi tìm kiếm bằng cách so sánh k với số hạng ở giữa dãy (a giữa ), khi đó chỉ xảy ra một trong ba trường hợp: 	- Nếu a giữa = k => tìm được chỉ số, kết thúc;	- Nếu a giữa > k => do dãy A đã được sắp xếp tăng 	 nên việc tìm kiếm thu hẹp chỉ xét từ a 1 a giữa - 1 ; 	- Nếu a giữa do dãy A đã được sắp xếp tăng 	 nên việc tìm kiếm thu hẹp chỉ xét từ a giữa + 1 a N . 
Quá trình trên được lặp đi lặp lại cho đến khi tìm được OUTPUT. 
Mô phỏng thuật toán tìm kiếm nhị phân 
10 
9 
8 
7 
6 
5 
4 
3 
2 
1 
i 
33 
31 
30 
22 
21 
9 
6 
5 
4 
2 
A 
 Với k = 21 và dãy A gồm 10 số hạng như sau: 
Lượt thứ nhất : a giữa là a 5 = 9; 9 < 21   vùng tìm kiếm thu hẹp trong phạm vi từ a 6 a 10 ; 
33 
31 
30 
22 
21 
Lượt thứ hai : a giữa là a 8 = 30; 30 > 21  vùng tìm kiếm thu hẹp trong phạm vi từ a 6 a 7 ; 
Lượt thứ ba : a giữa là a 6 = 21; 21= 21  	  Vậy số cần tìm là i = 6. 
22 
21 
6 
6 
21 
 Liệt kê các bước 
 Bước 1: Nhập N, các số hạng a 1 , a 2 ,, a N  và giá trị khoá k; 
 Bước 2: Đầu  1, Cuối  N; 
 Bước 3: Giữa  [(Đầu + Cuối)/2]; 
 Bước 4: Nếu a Giữa = k thì thông báo chỉ số Giữa 	 rồi kết thúc; 
 Bước 5: Nếu a Giữa > k thì đặt Cuối = Giữa - 1 rồi	 chuyển sang bước 7; 
 Bước 6: Đầu  Giữa + 1; 
 Bước 7: Nếu Đầu Cuối thì 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; 
 Bước 8: Quay lại bước 3. 
1. Khái niệm bài toán 
Bài toán và thuật Toán 
2. Khái niệm 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ự và nhị phân.