Giáo án Tin học Lớp 10 - Bài 4: Bài toán và thuật toán - Trường THPT Tịnh Biên

TRƯỜNG THPT TỊNH BIÊN
MÔN : TIN HỌC – THPT
BÀI 4. BÀI TOÁN VÀ THUẬT TOÁN
Môn học: Tin học lớp10
Thời gian thực hiện: 5 tiết
I. MỤC TIÊU
Yêu cầu cần đạt: Biết cách diển đạt và mô phỏng một số thuật toán.
1. Kiến thức: 
Biết khái niệm bài toán và thuật toán, các đặc trưng chính của thuật toán.
Biết một số thuật toán thông dụng.
Biết cách biểu diễn thuật toán bằng ngôn ngữ liệt kê (dùng ngôn ngữ tự nhiên)
Biết cách biểu diễn thuật toán bằng sơ đồ khối 
2. Kĩ năng:
Xây dựng được thuật toán giải một số bài toán đơn giản bằng sơ đồ khối hoặc liệt kê các bước.
Rèn luyện cho học sinh kỹ viết thuật toán để chuẩn bị cho việc học Tin học ở lớp 11.
3. Năng lực 
Năng lực chung: Năng lực sử dụng máy tính, Năng lực giải quyết vấn đề, Năng lực tự học, Năng lực hợp tác, làm việc nhóm.
Năng lực chuyên biệt: Năng lực diễn đạt thuật toán, Năng lực thực hành mô phỏng thuật toán.
4. Phẩm chất: Giúp học sinh rèn luyện bản thân phát triển các phẩm chất tốt đẹp: chăm chỉ, trung thực, trách nhiệm 
II. THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU 
- Giáo viên: chuẩn bị học liệu trên một số công cụ hỗ trợ (Powerpoint, zalo, Padlet, Azota, thiết bị máy tính, ), Sách giáo khoa Tin học 10.
Học sinh: đồ dùng học tập, SGK, vở ghi, Thiết bị học tập ( ĐTDĐ, máy tính,..)
HS sử dụng đường link google meet được giáo viên cung cấp.
III. TIẾN TRÌNH DẠY HỌC
A. MỞ ĐẦU (thực hiện trước giờ học)
a) Mục tiêu: Tạo tình huống khơi gợi tinh thần cho học sinh
b) Nội dung: Tình huống: hiện tại tôi đang ở chùa Bàu Mướp tôi muốn đi đến chợ nhà bàng, vậy tôi phải đi đường nào? 
c) Sản phẩm: Từ yêu cầu của GV, HS đưa ra câu trả lời câu hỏi GV đưa ra bằng cách đánh vào trả lời trực tuyến bằng giọng nói.
d) Tổ chức thực hiện: 
	GV giới thiệu và dẫn dắt vào bài: Câu hỏi chỉ đường
	Ai có kết quả chính sát, đường đi đơn giản, ngắn... sẽ có điểm cộng.
	GV hỏi: câu hỏi đường là gì? Và cách chỉ đường đi là gì? 
 	 Và để máy tính hiểu và thực hiện ta phải chuyển như thế nào? Gọi là gì?
B. HÌNH THÀNH KIẾN THỨC MỚI
Hoạt động 1: Khái niệm về bài toán và thuật toán, cách biểu diễn thuật toán.
a) Mục tiêu: Biết khái niệm bài toán và thuật toán, các đặc trưng chính của thuật toán.
b) Nội dung: HS nghiên cứu SGK để tìm hiểu nội dung kiến thức theo yêu cầu để báo cáo
c) Sản phẩm: bài báo cáo, trình bày của học sinh
d) Tổ chức thực hiện:
#1: Yêu cầu học sinh nghiên cứu sách giáo khoa và trình bày giới thiệu Khái niệm về bài toán và thuật toán, cách biểu diễn thuật toán. (Làm việc nhóm và nhận nhiệm vụ từ giáo viên ờ tiết bài trước, chuẩn bị trước tới phần được giao thì cử đại diện lên trình bày)
#2: HS thực hiện nhiệm vụ (tự thực hiện có hướng dẫn): HS nghiên cứu trình bày nội dung qua Powerpoint hoặc file. 
#3: GV tổ chức báo cáo, thảo luận và kết luận (trực tuyến): 
GV: yêu cầu nhóm chuẩn bị nôi dung lên báo cáo, trình bày.
HS: lắng nghe và đóng góp ý kiến cho nhóm báo cáo
GV: Quan sát tiến trình báo cáo và ghi nhận đóng góp của các nhóm, gợi ý một số câu hỏi để xem sự chú ý và ghi nhớ bài của học sinh.
Gợi ý:
Biểu diễn thuật toán có cách nào?
Thuật toán là gì? 
Thuật toán có mấy tính chất? Liệt kê?
Để giải bài toán cần xác định gì? Định nghĩa chúng?
#4: GV chốt kiến thức: 
1. Khái niệm bài toán
a. Khái niệm
Là việc nào đó mà ta muốn máy tính thực hiện để từ thông tin đưa vào (Input) tìm được kết quả ra (Output).
Bài toán trong tin học gồm:
- Thông tin đã có, dữ liệu vào: Input
- Thông tin cần tìm từ Input, kết quả: Output
b.Ví dụ 
Xác định Input và Output của các bài toán sau:
Vd1: Tìm ước chung lớn nhất (M,N)
Input: Hai số nguyên dương M, N
Output: UCLN(M,N).
Vd2: Kiểm tra số nguyên dương N có phải là số nguyên tố không?
Input: Số nguyên dương N
Output: “N là số nguyên tố” hoặc “N không là số nguyên tố”.
2. Khái niệm thuật 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 đó, từ Input của bài toán ta nhận được Output cần tìm.
* Biểu diễn thuật toán
Có 2 cách biểu diễn thuật toán:
- Liệt kê: Nêu các bước cần thực hiện thuật toán.
- Sơ đồ khối: Sử dụng các hình khối để thể hiện các thao tác của thuật toán.
Thể hiện thao tác nhập hoặc xuất
 	Thể hiện phép tính toán
 	 Thể hiện thao tác so sánh
	 	 Quy trình thực hiện các thao tác 
Ví dụ: Giải phương trình ax + b = 0
Cách 1. Liệt kê:
B1. Nhập a, b 
B2. Nếu a = 0, b = 0 PT có vô số nghiệm. => B5
B3. Nếu , PT có nghiệm => B5
B4. - Nếu a = 0, PT vô nghiệm. => B5
B5. Kết thúc
Cách 2: Sơ đồ khối
3. Các tính chất của thuật toán:
- Tính dừng: Thuật toán phải kết thúc sau 1 số lần thực hiện các thao tác.
- Tính xác định: Sau khi thực hiện 1 thao tác thì xác định thao tác tiếp theo
- Tính đúng đắn: Sau khi thuật toán kết thúc ta phải nhận được output cần tìm.
Hoạt động 2: Biểu diễn thuật toán Tìm giá trị lớn nhất của một dãy số nguyên
a. Mục tiêu: HS biết cách biểu diễn thuật toán 
b. Nội dung: HS nghiên cứu SGK để tìm hiểu nội dung kiến thức theo yêu cầu để báo cáo
c. Sản phẩm: Bài báo cáo của học sinh, kĩ năng CNTT và giải quyết nhiệm vụ học tập.
d. Tổ chức thực hiện: 
#1: Yêu cầu học sinh nghiên cứu sách giáo khoa và trình bày giới thiệu Biểu diễn thuật toán Tìm giá trị lớn nhất của một dãy số nguyên (Làm việc nhóm và nhận nhiệm vụ từ giáo viên ờ tiết bài trước, chuẩn bị trước tới phần được giao thì cử đại diện lên trình bài)
#2: HS thực hiện nhiệm vụ (tự thực hiện có hướng dẫn): HS nghiên cứu trình bày nội dung qua Powerpoint hoặc file. 
#3: GV tổ chức báo cáo, thảo luận và kết luận (trực tuyến): 
GV: yêu cầu nhóm chuẩn bị nôi dung lên báo cáo, trình bày.
HS: lắng nghe và đóng góp ý kiến cho nhóm báo cáo
GV: Quan sát tiến trình báo cáo và ghi nhận đóng góp của các nhóm, cho dãy số nguyên yêu cầu học sinh lên làm bằng cách mô phòng thuật toán để đánh giá việc nắm bài của học sinh
# 4 GV chốt kiến thức vừa trình bày của nhóm
Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên
*Xác định bài toán:
 - Input: N, dãy số nguyên a1,..., aN
 - Output: Số lớn nhất của dãy số
* Ý tưởng:
Khởi tạo giá trị Max= a1
Với i từ 2 đến N, so sánh giá trị số hạng a1 với giá trị Max, nếu ai>Max thì Max nhận giá trị mới là ai.
*Thuật toán:
Cách 1. Liệt kê
Bước 1: Nhập N và dãy số nguyên a1 aN;
Bước 2: Max:=a1, i:=2;
Bước 3: Nếu i>N thì đưa ra giá trị Max và kết thúc.
Bước 4: 
	4.1. Nếu ai > Max thì Max := ai;
	4.2. i:=i+1. rồi quay lại bước 3;
Cách 2: Sơ đồ khối (SGK)
Mô phỏng ví dụ việc thục hiện thuật toán với N = 4 và dãy số 9 6 10 1
dãy số
9
6
10
1
i
2
3
4
5
Max
9
9
10
10
Hoạt động 3: Nvàa1,a2,...,aN aN
Max :=a1; i :=2
i > N
ai>Max
Max:= ai
i := i + 1
TB giá trị Max 
Đ
Đ
S
S
Nvàa1,a2,...,aN aN
Max :=a1; i :=2
i > N
ai>Max
Max:= ai
i := i + 1
TB giá trị Max 
Đ
Đ
S
S
 Biểu diễn thuật toán sắp xếp bằng tráo đổi
a. Mục tiêu: HS biết cách biểu diễn thuật toán 
b. Nội dung: HS nghiên cứu SGK để tìm hiểu nội dung kiến thức theo yêu cầu để báo cáo
c. Sản phẩm: Bài báo cáo của học sinh, kĩ năng CNTT và giải quyết nhiệm vụ học tập.
d. Tổ chức thực hiện: 
#1: Yêu cầu học sinh nghiên cứu sách giáo khoa và trình bày giới thiệu Biểu diễn thuật toán toán sắp xếp bằng tráo đổi (Làm việc nhóm và nhận nhiệm vụ từ giáo viên ờ tiết bài trước, chuẩn bị trước tới phần được giao thì cử đại diện lên trình bày)
#2: HS thực hiện nhiệm vụ (tự thực hiện có hướng dẫn): HS nghiên cứu trình bày nội dung qua Powerpoint hoặc file. 
#3: GV tổ chức báo cáo, thảo luận và kết luận (trực tuyến): 
GV: yêu cầu nhóm chuẩn bị nôi dung lên báo cáo, trình bày.
HS: lắng nghe và đóng góp ý kiến cho nhóm báo cáo
GV: Quan sát tiến trình báo cáo và ghi nhận đóng góp của các nhóm, cho dãy số nguyên yêu cầu học sinh lên làm bằng cách mô phòng thuật toán để đánh giá việc nắm bài của học sinh
# 4 GV chốt kiến thức vừa trình bày của nhóm
Ví dụ: Cho dãy A gồm N số nguyên a1,a2,..., aN. Cần sắp xếp các hạng số để dãy A trở thành dãy không giảm.
* Xác định bài toán:
-Input: Dãy A gồm N số nguyên a1,a2,..., aN
-Output: Là dãy A được sắp tăng dần.
* Ý Tưởng: Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số đứng trước lớn hơn số sau ta đổi chổ chúng cho nhau. Việc đó được lặp lại, cho đến khi mỗi số đứng trước nhỏ hơn số đứng sau.
 * Thuật toán sắp xếp bằng tráo đổi (Exchange Sort)
 Cách 1: 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 B5.
Ghi chú: M=N, giảm M cho đến khi M<2. i chạy từ 0 đến M+1
Cách 2: Sơ đồ khối ( SGK trang 39)
 Mô phỏng ví dụ Cho dãy A gồm N số nguyên 7 3 5 10 8 2 1 9 
. Cần sắp xếp các hạng số để dãy A trở thành dãy không giảm.
N=M=8
Duyệt lần 1: M=M-1=7
 i=0 7 3 5 10 8 2 1 9
 i=1 3 7 5 10 8 2 1 9
 i=2 3 5 7 10 8 2 1 9
 i=3 3 5 7 10 8 2 1 9
 i=4 3 5 7 8 10 2 1 9
 i=5 3 5 7 8 2 10 1 9 
 i=6 3 5 7 8 2 1 10 9
 i=7 3 5 7 8 2 1 9 10
 Duyệt lần 2: M=6
 i=0 3 5 7 8 2 1 9 10
 i=1 3 5 7 8 2 1 9 10
 i=2 3 5 7 8 2 1 9 10
 i=3 3 5 7 2 8 1 9 10
 i=4 3 5 7 2 1 8 9 10
 i=5 3 5 7 2 1 8 9 10
 i=6 3 5 7 2 1 8 9 10
Duyệt lần 3: M= 5
 i=0 3 5 7 2 1 8 9 10
 i=1 3 5 7 2 1 8 9 10
 i=2 3 5 7 2 1 8 9 10
 i=3 3 5 2 7 1 8 9 10
 i=4 3 5 2 1 7 8 9 10
 i=5 3 5 2 1 7 8 9 10
Duyệt lần 4: M=4
 i=0 3 5 2 1 7 8 9 10
 i=1 3 5 2 1 7 8 9 10
 i=2 3 2 5 1 7 8 9 10
 i=3 3 2 1 5 7 8 9 10
 i=4 3 2 1 5 7 8 9 10
Duyệt lần 5: M=3
 i=0 2 3 1 5 7 8 9 10
 i=1 2 3 1 5 7 8 9 10
 i=2 2 1 3 5 7 8 9 10
 i=3 2 1 3 5 7 8 9 10
Duyệt lần 6: M=2
 i=0 1 2 3 5 7 8 9 10
 i=1 1 2 3 5 7 8 9 10
 i=2 1 2 3 5 7 8 9 10
DL7: M=1
 i=0 1 2 3 5 7 8 9 10
 i=1 1 2 3 5 7 8 9 10
 KQ: 1 2 3 5 7 8 9 10
Hoạt động 4: Biểu diễn thuật toán tìm kiếm tuần tự
a. Mục tiêu: HS biết cách biểu diễn thuật toán 
b. Nội dung: HS nghiên cứu SGK để tìm hiểu nội dung kiến thức theo yêu cầu để báo cáo
c. Sản phẩm: Bài báo cáo của học sinh, kĩ năng CNTT và giải quyết nhiệm vụ học tập.
d. Tổ chức thực hiện: 
#1: Yêu cầu học sinh nghiên cứu sách giáo khoa và trình bày giới thiệu Biểu diễn thuật toán toán tìm kiếm tuần tự (Làm việc nhóm và nhận nhiệm vụ từ giáo viên ờ tiết bài trước, chuẩn bị trước tới phần được giao thì cử đại diện lên trình bày)
#2: HS thực hiện nhiệm vụ (tự thực hiện có hướng dẫn): HS nghiên cứu trình bày nội dung qua Powerpoint hoặc file. 
#3: GV tổ chức báo cáo, thảo luận và kết luận (trực tuyến): 
GV: yêu cầu nhóm chuẩn bị nôi dung lên báo cáo, trình bày.
HS: lắng nghe và đóng góp ý kiến cho nhóm báo cáo
GV: Quan sát tiến trình báo cáo và ghi nhận đóng góp của các nhóm, cho dãy số nguyên yêu cầu học sinh lên làm bằng cách mô phòng thuật toán để đánh giá việc nắm bài của học sinh
# 4 GV chốt kiến thức vừa trình bày của nhóm
Cho dãy A gồm N số nguyên khác nhau a1, a2,..,aN và 1 số k. Cần biết có hay không chỉ số i (1<=i<=N) mà ai =k. Nếu có hãy cho biết chỉ số đó.
*Xác định bài toán:
- Input: Dãy A gồm N số nguyên khác nhau a1,a2,.., aN và 1 số k.
- Output: Chỉ số i (1<=i<=N) mà ai=k. Hoặc thông báo không có số hạng nào của dãy A có giá trị bằng k.
**Ghi chú: i là biến chỉ số và nhận giá trị nguyên lần lượt từ 1 đến N+1
* Ý tưởng: Tìm kiếm tuần tự được thực hiện một cách tự nhiên. 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á cho đến khi hoặc gặp 1 số hạng bằng khoá hoặc dãy đang xét hết. Và không có gía trị nào bằng khoá.
*Thuật toán tìm kiếm tuần tự (Sequential seasch):
 Cách 1: Cách liệt kê:
B1: Nhập N các số hạng a1,a2,..., aN và k;
B2: i:=1;
B3: Nếu ai=k thi thông báo chỉ số i, rồi kết thúc;
B4: i:=i+1;
B5: 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;
B6: Quay lại bước 3
Cách 2: Sơ đồ khối (SGK trang 41)
Mô phỏng ví dụ
Cho dãy A gồm các số nguyên khác nhau 2 7 4 6 8 10 1 26 11 và k=10. Cần biết có hay không chỉ số i (1<=i<=N) mà ai =k. Nếu có hãy cho biết chỉ số đó.
A
2
7
4
6
8
10
1
26
11
i
1
2
3
4
5
6
.
.
.
 Kết luận: Với i = 6 thì a6 = 10
Cho dãy A gồm các số nguyên khác nhau 2 7 4 6 8 10 1 26 11 và k=3. Cần biết có hay không chỉ số i (1<=i<=N) mà ai =k. Nếu có hãy cho biết chỉ số đó.
A
2
7
4
6
8
10
1
26
11
i
1
2
3
4
5
6
7
8
9
10
 Kết luận: Với mọi i từ 1 đến 9 không có giá trị ai = k = 3
Hoạt động 5: Vận dụng và công việc về nhà
a. Mục tiêu: Vận dụng các kiến thức vừa học để các bài tập . và giao nhiệm về nhà.
b. Nội dung: bài tập các dạng thuật toán đã học. và giao nhiệm về nhà phân công về nhà, xem nội dung của bài 5 và trả lời một số câu hỏi trong nội dung bài 5 đã gởi.
Bài tập về nhà Với cách thức mô phỏng thuật toán hãy
1/ Tìm giá trị lớn nhất của dãy số 9 6 10 1 .
2/ Cho dãy A gồm N số nguyên 7 3 5 10 8 2 1 9 
. Cần sắp xếp các hạng số để dãy A trở thành dãy không giảm.
3/ Cho dãy A gồm các số nguyên khác nhau 7 4 6 8 1 26 15 và k = 9. Cần biết có hay không chỉ số i (1<=i<=N) mà ai =k. Nếu có hãy cho biết chỉ số đó.
4/ Cho dãy A gồm các số nguyên khác nhau 2 6 8 10 1 12 và k = 2. Cần biết có hay không chỉ số i (1<=i<=N) mà ai =k. Nếu có hãy cho biết chỉ số đó.
c. Sản phẩm: HS vận dụng các kiến thức vào làm bài tập.
d. Tổ chức thực hiện:
#1: GV cho bài tập. Giao nhiệm vụ cho HS chuẩn bị theo 4 nhóm thảo luận và trình bày nội dung và yêu cầu nghiêm túc thực hiện.
#2: HS thực hiện nhiệm vụ ở nhà.
Nghiên cứu sách giáo khoa, và nội dung tư liệu gởi qua Zalo trả lời câu hỏi trong tư liệu
#3: GV yêu cầu HS làm bài trên tập và nộp bằng cách chụp hình gởi qua nhóm Zalo lớp.
– GV sửa bài, chọn một số bài làm tốt của HS để giới thiệu và tuyên dương trước lớp vào thời điểm thích hợp. Nhắc công việc về nhà.
-----HẾT ----