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

ai số nguyên dương. 
	INPUT: Hai số nguyên dương M và N. 
	OUTPUT: ư ớc số chung lớn nhất của M và N. 
Ví dụ 4: Bài toán xếp loại học tập của một lớp. 
 	INPUT: Bảng điểm của học sinh trong lớp. 
 	OUTPUT: Bảng xếp loại học lực của học sinh . 
Bài 4. Bài toán và thuật Toán 
2. Khái niệm thuật toán 
Từ INPUT làm thế nào để tìm ra OUTPUT ? 
Các em cần tìm ra cách giải của bài toán. 
Xét ví dụ 2: Giải phương trình bậc nhất ax + b = 0. 
B1: Xác định hệ số a, b; 
B2: Nếu a=0 và b=0 => Phương trình vô số nghiệm =>B5; 
B3: Nếu a = 0 và b ≠ 0 => Phương trình vô nghiệm =>B5; 
B4: Nếu a ≠ 0 => Phương trình có nghiệm x=-b/a =>B5; 
B5: Kết thúc. 
 Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận được Output cần tìm. 
 Có hai cách thể hiện một thuật toán: 	  Cách 1: Liệt kê các bước. 	  Cách 2: Vẽ sơ đồ khối. 
B7: Kết thúc. 
 B1: B...ới lớn nhất 
ồ! Quả này lớn hơn 
Tìm ra quả lớn nhất rồi! 
 Cùng tìm thuật toán 
MAX 
Thuật toán tìm số lớn nhất trong một dãy số nguyên 
 Xác định bài toán:  INPUT: Số nguyên dương N và dãy N số 	nguyên a 1 , a 2 , , a N (a i với i: 1 N). 	  OUTPUT: Số lớn nhất (Max) của dãy số. 
ý tưởng: - Đặt giá trị Max = a 1 .  - Lần lượt cho i chạy từ 2 đến N, so sánh giá trị a i với giá trị Max, nếu a i > Max thì Max nhận giá trị mới là a i . 
Cách 1: Liệt kê các bước 
 B1: Nhập N và dãy a 1 ,, a N ; 
 B2: Max  a 1 ; i  2; 
 B3: Nếu i > N thì đưa ra giá trị Max rồi kết thúc; 
 B4:	Bước 4.1: Nếu a i > Max thì Max  a i ;	Bước 4.2: i  i+1 rồi quay lại B3. 
Đ 
S 
Đ 
S 
Nhập N và dãy a1,,aN 
Max  a1 ; i  2 
i > N ? 
a i > Max ? 
 Max  a i 
i  i + 1 
Đưa ra Max rồi kết thúc 
 B1: Nhập N và dãy a 1 ,,a N ; 
 B2: Max  a 1 ; i  2; 
 B3: Nếu i > N thì đưa ra giá trị  Max rồi kết thúc; 
 B4 : 4.1: Nếu a i > Max thì Max  a i ; 
 4.2: i  i + 1 rồi quay lại B3. 
Cách 2: Sơ đồ khối 
Đ 
S 
Đ 
S 
Nhập N và dãy a1,,aN 
Max  a1 ; i  2 
I > N ? 
a i > Max ? 
 Max a i 
i  i+1 
Đưa ra Max rồi kết thúc 
Max 
i 
A 
7 
7 
5 
5 
5 
5 
4 
3 
2 
6 
7 
4 
1 
5 
N=5 ; A [ 5 1 4 7 6 ] 
Max  5 ; i  2 
2 > 5 ? 
1> 5 ? 
i  2+1 
3 > 5 ? 
4> 5 ? 
i 3+1 
4 > 5 ? 
7 > 5 ? 
 Max 7 
4 
i 4+1 
5 > 5 ? 
7 > 7 ? 
i 5+1 
6 > 5 ? 
Số lớn nhất của dãy là 7 
Mô phỏng 
thuật toán 
Với i = 2 
Với i = 3 
Với i = 4 
Với i = 5 
Đ 
S 
Đ 
S 
Nhập N và dãy a1,,aN 
Max  a1 ; i  2 
I > N ? 
a i > Max ? 
 Max a i 
i  i+1 
Đưa ra Max rồi kết thúc 
Max 
i 
A 
7 
7 
5 
5 
5 
5 
4 
3 
2 
6 
7 
4 
1 
5 
N=5 ; A [ 5 1 4 7 6 ] 
Max  5 ; i  2 
2 > 5 ? 
1> 5 ? 
i  2+1 
3 > 5 ? 
4> 5 ? 
i 3+1 
4 > 5 ? 
7 > 5 ? 
 Max 7 
4 
i 4+1 
5 > 5 ? 
7 > 7 ? 
i 5+1 
6 > 5 ? 
Số lớn nhất của dãy là 7 ...
7 
3 
5 
8 
1 
9 
7 
3 
5 
8 
1 
7 
9 
 Lượt thứ hai: 
3 
5 
8 
1 
7 
9 
3 
5 
1 
8 
7 
9 
3 
5 
1 
7 
8 
9 
 Lượt thứ ba: 
3 
5 
1 
7 
8 
9 
3 
1 
5 
7 
8 
9 
3 
1 
5 
7 
8 
9 
1 
3 
5 
7 
8 
9 
 Lượt thứ tư: 
Mô phỏng thuật toán sắp xếp bằng tráo đổi 
Cách 1: Liệt kê các bước 
B1: Nhập N, các số hạng a 1 , a 2 ,, a N ; 
B2: M  N; 
B3: Nếu M < 2 thì đưa ra dãy A đã sắp xếp rồi kết thúc; 
B4: M  M – 1; i  0; 
B5: i  i +1; 
B6: Nếu i > M thì quay lại B3; 
B7: Nếu a i > a i+1 thì tráo đổi a i và a i+1 cho nhau; 
B8: Quay lại B5. 
Nhập N và a 1 , a 2 ,..., a N 
M  N 
M < 2 ? 
M  M - 1; i  0 
i  i + 1 
i > M ? 
a i > a i+1 ? 
Tráo đổi 
a i và a i+1 
Đưa ra A đã sắp xếp 
rồi kết thúc 
Đ 
Đ 
Đ 
S 
S 
S 
Cách 2 
Vẽ sơ đồ khối 
Thuật toán tìm kiếm 
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! 
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 a 1 , a 2 ,, a N đôi một khác nhau và số nguyên k. OUTPUT: Chỉ số i mà a i = 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í i = 5 có a 5 = 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ó a i 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ự t