Bài giảng Tin học Lớp 10 - Tiết 10-14, Bài 4: Bài toán và thuật toán - Trường THPT Quang Trung

Trường THPT Quang Trung Đà Nẵng 
Bài 4. Bài toán và thuật Toán 
Tuần 5+6+7. 
Tiết 10, 11, 12, 13, 14. 
12/24/2023 
1 
Nguồn: Sưu tầm 
1. Khái niệm bài toán 
Là việc nào đó ta muốn máy thực hiện để từ thông tin đưa vào (INPUT) tìm đư ợc thông tin ra (OUTPUT). 
Ví dụ 3: Tìm ư ớc số chung lớn nhất của hai 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 . 
12/24/2023 
2 
Nguồn: Sưu tầm 
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 . 
12/24/2023 
3 
Nguồn: Sưu tầm 
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 . 
12/24/2023 
4 
Nguồn: Sưu tầm 
 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 . 
12/24/2023 
5 
Nguồn: Sưu tầm 
B7: Kết thúc . 
 B1: Bắt đ ầu ; 
 B2: Nhập a, b, c; 
 B3: Tính = b 2 – 4ac; 
 B4: Nếu PT vô nghiệm => B7; 
 B5: Nếu = 0 => PT có nghiệm kép x = -b/2a => B7; 
 B6: Nếu > 0 => PT có hai nghiệm x1, x2 = (-b  )/2a  => B7; 
3. Một số ví dụ về thuật toán 
Thuật toán giải phương trình bậc hai (a 0). 
Cách 1: Liệt kê các bước 
12/24/2023 
6 
Nguồn: Sưu tầm 
Quy ư ớc các khối trong sơ đồ thuật toán 
Bắt đ ầu thuật toán . 
Dùng để nhập và xuất dữ liệu . 
Dùng để gán gi á trị và tính toán . 
Xét đ iều kiện rẽ nhánh theo một trong hai đ iều kiện đ úng , sai . 
Kết thúc thuật toán . 
BĐ 
 ĐK 
đ 
S 
KT 
Cách 2: Vẽ sơ đồ khối 
12/24/2023 
7 
Nguồn: Sưu tầm 
Nhập vào a, b, c 
D 
= b 
- 
4ac 
D 
< 0 
PT vô nghiệm 
D 
= 0 
 PT có nghiệm x= - 
 b/2a 
KT 
BD 
đ 
s 
Sơ đồ thuật toán giải phương trình bậc hai 
2 
PT có 2 nghiệm 
x1,x2 
 = ( 
-b 
 ±ệD 
 )/2a 
B1 
B2 
B3 
B4 
B5 
B6 
s 
đ 
B7 
12/24/2023 
8 
Nguồn: Sưu tầm 
 a,b,c = 1 3 5 
D = 3*3 - 4*5 = - 11 
-11 < 0 
PT vô nghiệm 
D 
= 0 
PT có nghiệm x = 
-b/2a 
KT 
BD 
-11 
5 
3 
1 
c 
 b 
 a 
S 
PT có 2 nghiệm x1, x2 = (-b  )/2a 
Đ 
S 
D = b*b - 4*a*c 
 nh ập vào a,b,c 
 < 0 
Mô phỏng thuật toán giải phương trình bậc hai 
Bộ TEST 1: 	 
12/24/2023 
9 
Nguồn: Sưu tầm 
 a,b,c = 1 2 1 
D = 2*2 - 4*1*1 = 0 
PT vô nghiệm 
PT có nghiệm x=-b/2a 
KT 
BD 
0 
1 
2 
1 
c 
 b 
 a 
S 
PT có 2 nghiệm  x1, x2 = (-b  )/2a 
Đ 
S 
D = b*b - 4*a*c 
 nh ập vào a,b,c 
 < 0 
Mô phỏng thuật toán giải phương trình bậc hai 
Bộ TEST 2: 	 
Đ 
 = 0 
PT có nghiệm kép x=-1 
12/24/2023 
10 
Nguồn: Sưu tầm 
 a,b,c = 1 -5 6 
D = 25 - 24 = 1 
PT vô nghiệm 
PT có nghiệm x=-b/2a 
KT 
BD 
1 
6 
-5 
1 
c 
 b 
 a 
S 
PT có 2 nghiệm x1, x2 = (-b  )/2a 
Đ 
S 
D = b*b - 4*a*c 
 nh ập vào a,b,c 
 < 0 
Mô phỏng thuật toán giải phương trình bậc hai 
Bộ TEST 3: 	 
Đ 
 = 0 
PT có nghiệm x1 = 3 
 x2 = 2 
12/24/2023 
11 
Nguồn: Sưu tầm 
Thuật toán tìm max 
3 
Người ta đ ặt 5 qu ả bóng có kích thước khác nhau trong hộp đã đư ợc đ ậy nắp nh ư hình bên . Chỉ dùng tay hãy tìm ra qu ả bóng có kích thước lớn nhất . 
12/24/2023 
12 
Nguồn: Sưu tầm 
Qu ả này lớn nhất 
Qu ả này mớ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 
12/24/2023 
13 
Nguồn: Sưu tầm 
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ố . 
12/24/2023 
14 
Nguồn: Sưu tầm 
ý 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 . 
12/24/2023 
15 
Nguồn: Sưu tầm 
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. 
12/24/2023 
16 
Nguồn: Sưu tầm 
Đ 
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 
12/24/2023 
17 
Nguồn: Sưu tầm 
Đ 
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 
12/24/2023 
18 
Nguồn: Sưu tầm 
Đ 
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 
12/24/2023 
19 
Nguồn: Sưu tầm 
Thuật toán kiểm tra tính nguyên tố của một số nguyên dương 
 Xác đ ịnh bài toán :  INPUT: N là một số nguyên dương . OUTPUT: Tr ả lời câu hỏi N có là số  nguyên tố không ? 
12/24/2023 
20 
Nguồn: Sưu tầm 
ý tưởng : Xét các trường hợp  
Các em hãy nêu đ ịnh nghĩa số nguyên tố . 
 - Nếu N 4 và không có ư ớc số trong phạm vi từ 2 đ ến phần nguyên căn bậc hai của N th ì N là số nguyên tố . 
 - Nếu N = 1 th ì N không là số nguyên tố . 
- Nếu 1< N <4 th ì N là số nguyên tố .  
12/24/2023 
21 
Nguồn: Sưu tầm 
i 
2 
3 
4 
5 
N/i 
29/2 
29/3 
29/4 
29/5 
Chia hết không ? 
Không 
Không 
Không 
Không 
Chia hết 
Không 
Chia hết không ? 
45/3 
45/2 
N/i 
3 
2 
i 
45 không là số nguyên tố . 
 29 là số nguyên tố . 
 Trường hợp 2: N = 29 ([  29 ] = 5) 
 Trường hợp 1: N = 45 ([  45 ] = 6) 
Mô phỏng thuật toán kiểm tra tính nguyên tố 
12/24/2023 
22 
Nguồn: Sưu tầm 
Cách 1: Liệt kê các bước 
B1: Nhập số nguyên dương N; 
B2: Nếu N = 1 thông báo N không nguyên tố , kết thúc ; 
B3: Nếu N < 4 thông báo N là nguyên tố rồi kết thúc ; 
B4: i 2; 
B5: Nếu i > [ N ] th ì thông báo N là nguyên tố , kết thúc ; 
B6: Nếu N chia hết cho i th ì thông báo N không nguyên 	 tố rồi kết thúc ; 
B7: i  i +1 rồi quay lại B5. 
12/24/2023 
23 
Nguồn: Sưu tầm 
Nhập N 
N =1 ? 
N < 4 ? 
i  2 
i>[  N ] ? 
N có chia hết cho i ? 
i  i +1 
Thông báo N là số nguyên tố rồi kết thúc . 
Thông báo N không là số nguyên tố rồi kết thúc . 
Đ 
S 
S 
Đ 
S 
S 
Đ 
Đ 
Cách 2 
Vẽ sơ đồ khối 
12/24/2023 
24 
Nguồn: Sưu tầm 
Thuật toán sắp xếp 
Hãy tìm cách sắp xếp học sinh đ ứng chào cờ ( hình a) theo thứ tự thấp trước cao sau ( hình b). 
Hình a 
Hình b 
12/24/2023 
25 
Nguồn: Sưu tầm 
Thuật toán sắp xếp bằng tráo đ ổi 
 Xác đ ịnh bài toán :  INPUT: Dãy A gồm N số nguyên a 1 , a 2 ,, a N .OUTPUT: Dãy A đư ợc sắp xếp thành dãy không giảm . 
12/24/2023 
26 
Nguồn: Sưu tầm 
ý tưởng :  
Với mỗi cặp số hạng đ ứng liền kề trong dãy , nếu số trước lớn hơn số sau ta đ ổi vị trí chúng cho nhau . Việc đó đư ợc lặp lại cho đ ến khi không có sự đ ổi chỗ nào xảy ra nữa . 
12/24/2023 
27 
Nguồn: Sưu tầm 
 Với N = 6 và dãy A gồm 6 số hạng nh ư sau : 
3 
5 
9 
8 
1 
7 
 Lượt thứ nhất : 
3 
5 
9 
8 
1 
7 
3 
5 
8 
9 
1 
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 
12/24/2023 
28 
Nguồn: Sưu tầm 
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. 
12/24/2023 
29 
Nguồn: Sưu tầm 
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 
12/24/2023 
30 
Nguồn: Sưu tầm 
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 ! 
12/24/2023 
31 
Nguồn: Sưu tầm 
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. 
12/24/2023 
32 
Nguồn: Sưu tầm 
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 
12/24/2023 
33 
Nguồn: Sưu tầm 
ý 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. 
12/24/2023 
34 
Nguồn: Sưu tầm 
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. 
12/24/2023 
35 
Nguồn: Sưu tầm 
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 
12/24/2023 
36 
Nguồn: Sưu tầm 
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. 
12/24/2023 
37 
Nguồn: Sưu tầm 
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 
12/24/2023 
38 
Nguồn: Sưu tầm 
 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. 
12/24/2023 
39 
Nguồn: Sưu tầm