Giáo án Tin học Lớp 10 - Tuần 6 - Năm học 2021-2022 - Nguyễn Thị Thìn

Tuần: 06
Tiết PPCT: 11
Ngày soạn: 18/ 09/ 2021
Bài 4: BÀI TOÁN VÀ THUẬT TOÁN (tiếp)
I/ MỤC TIÊU
1. Về kiến thức
- Nêu được khái niệm bài toán và thuật toán, các tính chất của thuật toán.
- Phân tích cách biễu diễn thuật toán bằng sơ đồ khối và bằng liệt kê các bước.
- Trình bày được một số thuật toán thông dụng. 
2. Về năng lực
- Năng lực chung: Năng lực tự học, năng lực giải quyết vấn đề, năng lực hợp tác, năng lực giao tiếp:
- Năng lực chuyên biệt: Xây dựng được các thuật toán phục vụ cho việc lập trình ra các chương trình phục vụ trong học tập và đời sống.
3. Về phẩm chất
- Luyện khả năng tư duy lôgic khi giải quyết một vấn đề nào đó.
II/ THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU
Giáo viên
Giáo án, tranh ảnh
Phòng tin học
Học sinh
Sách giáo khoa, vở ghi.
Đọc bài trước.
III/ TIẾN TRÌNH BÀI DẠY
1. Ổn định lớp
2. Kiểm tra bài cũ
	- Nêu nguyên lý mã hoá nhị phân?
3. Đặt vấn đề
4. Nội dung bài mới
Hoạt động của giáo viên và học sinh
Nội dung
Hoạt động 1: Tìm thuật toán giải bài toán kiểm tra tính nguyên tố của một số nguyên dương
GV: Tổ chức các nhóm thảo luận
HS: Các nhóm thảo luận, trình bày ý kiến.
GV: Nhắc lại định nghĩa số nguyên tố?
HS: N là số nguyên tố, nếu:
+ N ≥ 2
+ N không chia hết cho các số từ 2 ® N – 1
hoặc	
+ N không chia hết cho các số từ 2 ®
GV: Hãy xác định Input và Output của bài toán này?
HS: N là số nguyên tố, nếu:
 + N ≥ 2
 + N không chia hết cho các số từ 2 ® N – 1
hoặc	+ N không chia hết cho các số từ 2 ®
GV: Hướng dẫn HS tìm thuật toán
GV: Cho các nhóm tiến hành xây dựng thuật toán bằng phương pháp liệt kê.
HS: Từng nhóm trình bày thuật toán
GV: Biến i nhận giá trị nguyên thay đổi trong phạm vi từ 2 đến + 1 và dùng để kiểm tra N có chia hết cho i hay không.
3. Một số ví dụ về thuật toán.
Ví dụ 1: Kiểm tra tính nguyên tố của một số nguyên dương.
· Ý tưởng:
 + 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ố.
 + 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ố. 
· Thuật toán:
a) Cách liệt kê: 
B1: Nhập số ng.dương N;
B2: Nếu N = 1 thì thông báo N không nguyên tố rồi kết thúc;
B3: Nếu N< 4 thì thông báo N là nguyên tố rồi kết thúc;
B4: i 2 ;
B5: Nếu i> thì thông báo N là nguyên tố rồi 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: ii + 1 rồi quay lại B5
 Hoạt động 2: Mô phỏng việc thực hiện thuật toán
GV: cho HS mô phỏng các bước thực hiện thuật toán trên với:
N = 31
· Xét với N = 29 có phải là số nguyên tố không? [] = 5
· Các nhóm thảo luận rồi đưa ra câu trả lời.
i
2
3
4
5
6
N/ i
29/ 2
29/ 3
29/ 4
29/ 5
Chia hết?
Không
Không
Không
Không
Vậy: 29 là số nguyên tố.
· Tương tự như trên xét với 
N = 45 có phải là số nguyên tố không?
45 không phải là số nguyên tố
5. Củng cố
 - Thế nào là bài toán trong tin học?
 - Việc xác định bài toán trong tin học?
 - Đọc tiếp bài "bài toán và thuật toán"
 - BTVN:Bài 1 SGK.
Tuần: 06
Tiết PPCT: 12
Ngày soạn: 18/ 09/ 2021
Bài 4: BÀI TOÁN VÀ THUẬT TOÁN (tiếp)
I/ MỤC TIÊU
1. Về kiến thức
- Nêu được khái niệm bài toán và thuật toán, các tính chất của thuật toán.
- Phân tích cách biễu diễn thuật toán bằng sơ đồ khối và bằng liệt kê các bước.
- Trình bày được một số thuật toán thông dụng. 
2. Về năng lực
- Năng lực chung: Năng lực tự học, năng lực giải quyết vấn đề, năng lực hợp tác, năng lực giao tiếp:
- Năng lực chuyên biệt: Xây dựng được các thuật toán phục vụ cho việc lập trình ra các chương trình phục vụ trong học tập và đời sống.
3. Về phẩm chất
- Luyện khả năng tư duy lôgic khi giải quyết một vấn đề nào đó.
II/ THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU
Giáo viên
Giáo án, tranh ảnh
Phòng tin học
Học sinh
Sách giáo khoa, vở ghi.
Đọc bài trước.
III/ TIẾN TRÌNH BÀI DẠY
1. Ổn định lớp
2. Kiểm tra bài cũ
	- Nêu nguyên lý mã hoá nhị phân?
3. Đặt vấn đề
4. Nội dung bài mới
Hoạt động của giáo viên và học sinh
Nội dung
 Hoạt động 1: Mô tả thuật toán sắp xếp bằng tráo đổi
Đặt vấn đề: Trong cuộc sống ta thường gặp những việc liên quan đến sắp xếp.
Cho một dãy số nguyên A:
	6, 1, 5, 3, 7, 8, 10, 7, 12, 4 
 Hãy sắp xếp dãy A trở thành dãy không giảm.
HS trả lời: 1, 3, 4, 5, 6, 7, 7, 8, 10, 12.
GV: Tổ chức các nhóm thảo luận 
GV:Hãy xác định Input và Ouput của bài toán?
HS trả lời.
+ Input: Dãy N số nguyên
 + Output: Dãy N số nguyên đã được sắp xếp không giảm.	
GV hướng dẫn HS tìm thuật toán giải bài toán.
GV nhận xét và bổ sung
Các nhóm thảo luận đưa ra ý kiến
GV hướng dẫn HS trình bày thuật toán (bằng pp liệt kê)
HS quan sát, theo dõi sơ đồ thuật toán và hình dung ra các bước thực hiện thuật toán.
GV Nhận xét: Sau mỗi lần đổi chỗ, giá trị lớn nhất của dãy A sẽ được chuyển dần về cuối dãy và sau lượt thứ nhất thì giá trị lớn nhất xếp đúng vị trí là ở cuối dãy. Và sau mỗi lượt chỉ thực hiện với dãy đã bỏ bớt số hạng cuối dãy (M M–1). Trong thuật toán trên, i là biến chỉ số có giá trị nguyên từ 0M+1.
3. Một số ví dụ (tt)
Ví dụ 2: Bài toán sắp xếp
Cho dãy A gồm N số nguyên a1, a2, , aN. Cần sắp xếp các số hạng để dãy A trở thành dãy không giảm.
·Thuật toán sắp xếp bằng tráo đổi (Exchange Sort)
· Xác định bài toán:
 - Input: Dãy A gồm N số nguyên a1, a2, , an.
 - Output: Dãy A được sắp xếp lại thành dãy không giả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 thì ta đổi chỗ 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.
· Thuật toán:
a) Cách liệt kê:
- B1: Nhập N, các số hạng a1, a2, , aN ;
 - B2: M N ;
 - B3: Nếu M< 2 thì đưa ra dãy A đã được 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 bước 3;
 - B7: Nếu ai> ai+1 thì tráo đổi ai và ai+1 cho nhau;
 - B8: Quay lại bước 5.
Hoạt động 2: Mô phỏng việc thực hiện thuật toán 
Mô phỏng việc thực hiện thuật toán với: 
N = 10 và dãy A: 
6, 1, 5, 3, 7, 8, 10, 7, 12, 4 
 Dãy A 
6
1
5
3
7
8
10
7
12
4
Lượt 1
1
5
3
6
7
8
7
10
4
12
Lượt 2
1
3
5
6
7
7
8
4
10
Lượt 3
1
3
5
6
7
7
4
8
Lượt 4
1
3
5
6
7
4
7
Lượt 5
1
3
5
6
4
7
Lượt 6
1
3
5
4
6
Lượt 7
1
3
4
5
Lượt 8
1
3
4
Lượt 9
1
3
Lượt 10
1
5. Củng cố
	- Tập mô phỏng việc thực hiện thuật toán trên với dãy số khác.
	- Tìm thuật toán tìm sắp xếp một dãy số nguyên thành dãy không tăng.
Ký duyệt của nhóm trưởng
Đoàn Văn Nghị
Ngày .... tháng .... năm 2021
Giáo viên
Nguyễn Thị Thìn