VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí
GIÁO ÁN TIN HỌC 10
Tuần …….
Tiết …….
§ 4. BÀI TOÁN VÀ THUẬT TOÁN

I. Mục tiêu
1. Về kiến thức:
Biết 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.
Hiểu 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.
Hiểu một số thuật toán thông dụng.
2. Về 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.
3. Về tư duy và thái độ:
Học sinh cần nhận thức được tầm quan trọng của môn học, vị trí của môn học
trong hệ thống kiến thức phổ thông và những yêu cầu về mặt đạo đức trong xã hội
tin học hóa.
II. CHUẨN BỊ
1. Giáo viên: Máy tính Projecter, sách giáo khoa, sách giáo viên, giáo án, …
2. Học sinh: Tập soạn bài, sgk, đồ dùng học tập.
III. PHƯƠNG PHÁP VÀ PHƯƠNG TIỆN DẠY HỌC
- Phương pháp: Sử dụng các phương pháp,dạy học cơ bản sau một cách
linh họat nhằm giúp học sinh tìm tòi,phát hiện,chiếm lĩnh tri thức. Gợi mở vấn đáp,
thảo luận. Phát hiện và giải quyết vấn đề. Đan xen hoạt động nhóm.
- Phương tiện: Bảng phụ và các phiếu học tập, Computer và projector (nếu
có).
VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí
IV. TIẾN TRÌNH BÀI HỌC
1. Ổn định lớp, Kiểm tra sĩ số
2. Kiểm tra bài cũ:

dụ.
1.Khái niệm bài toán:
Bài toán là một việc nào đó ta
muốn máy tính thực hiện.
Ví dụ: Giải pt bậc 2, quản lý
nhân viên…
Khi giải bài toán có 2 yếu tố:
+ Đưa vào máy thông tin
gì?(Input)
+ Cần lấy ra thông tin
gì?(Output)
Vì vậy cần phải nói rõ Input và
Output và mối quan hệ giữa Input
và Output.
 Các bài toán được cấu tạo bởi
2 thành phần cơ bản:
VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí
Hoạt động 2:
1. Làm thế nào để tìm ra
Output?
2. Thế nào là thuật toán
(Arithmetic)
3. Nêu các bước giải bài
toán?
Ví dụ: Tìm giá trị lớn
nhất của một dãy số
nguyên
Hãy xác định các bước
bài toán trên?
Giảng các bước thực hiện

+ Output: Các thông tin cần tìm
từ Output.
2. Khái niệm thuật toán:
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 1 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 ra Output cần tìm.
Ví dụ: Tìm giá trị lớn nhất của 1
dãy số nguyên.
Ta có 3 bước thực hiện như
sau:
+ Xác định bài toán
+ Ý tưởng.
+ Thuật toán
Minh họa 3 bước trong sách giáo
khoa, cho ví dụ cụ thể.
Hướng dẫn chi tiết sơ đồ khối,
các hình thoi, chữ nhật, ô van,
mũi tên.
Ví dụ: Mô phỏng việc thực hiện
thuật toánvới N=8 và dãy số:
5,1,4,7,6,3,15,11
Ds
5
1
4
7
6

Tính đúng đắn.
+ Hs thảo luận và trả lời.
Số nguyên tố là số chỉ
có 2 ước số.
i
2
3
4
5
6
7
8 9
Max
5
5
5
7
7
7
15
15
+ Lưu bảng bài làm của hs.
 Ta thấy thuật toán có một số
tính chất sau:
+ Tính dừng: Thuật toán phải
kết thúc sau một số hữu hạn lần
thực hiện các thao tác.
+ Tính xác định: Sau một số
lần thực hiện thao tác, hoặc là kết
thúc hoặc xác định để thực hiện

Tuần…….
Tiết …….
§4. BÀI TOÁN VÀ THUẬT TOÁN (tiết 2)
I. Mục đích, yêu cầu:
1. Về kiến thức:
- Dạy học sinh hiểu hơn về thuật toán thông qua ví dụ tiếp theo.
2. Về kỹ năng:
- 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. Về tư duy và thái độ:
- Học sinh cần nhận thức được tầm quan trọng của môn học, vị trí của môn
học trong hệ thống kiến thức phổ thông và những yêu cầu về mặt đạo đức trong xã
hội tin học hóa
II. CHUẨN BỊ
1. Giáo viên: Máy tính Projecter, sách giáo khoa, sách giáo viên, giáo án, …
2. Học sinh: Tập soạn bài, sgk, đồ dùng học tập.
III. PHƯƠNG PHÁP VÀ PHƯƠNG TIỆN DẠY HỌC
- Phương pháp: Sử dụng các phương pháp,dạy học cơ bản sau một cách
linh họat nhằm giúp học sinh tìm tòi,phát hiện,chiếm lĩnh tri thức. Gợi mở vấn đáp,
thảo luận. Phát hiện và giải quyết vấn đề. Đan xen hoạt động nhóm.
- Phương tiện: Bảng phụ và các phiếu học tập, Computer và projector (nếu
có).
IV. TIẾN TRÌNH BÀI HỌC
1. Ổn định lớp, Kiểm tra sĩ số
2. Kiểm tra bài cũ:
VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí
- Khái niệm thuật toán là gì? Thuật toán có các tính chất nào? Hãy
xác định Input và Output của bài toán giải phương trình bậc hai: ax
2
+

3. Các 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.
Xác định bài toán:
Input: Số nguyên
dương N  Output: “N là số nguyên tố” hoặc “N không là số nguyên tố”.
VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí
Nhắc lại định lý: “Nếu một
số nguyên dương N không
chia hết cho các số trong phạm
vi từ 2 đến phần nguyên căn
bậc 2 của N thì nó cũng không
chia hết cho các số trong phạm
vi từ phần nguyên căn bậc 2
của N đến N – 1.
Từ định nghĩa và định lý trên,
các em hãy thảo luận và trình
bày ý tưởng để xây dựng thuật
toán của bài toàn này.
Nhận xét và trình bày ý
tưởng để xây dụng thuật toán.
Từ ý tưởng trên, chúng ta đi
xây dựng thuật toán bằng cách
liệt kê như sau:
Xây dựng từng bước của
thuật toán và giải thích.
Nghe giảng.
Thảo luận nhóm và

Với N = 29
Với N = 45
Giải thích từng bước thực
hiện của thuật toán qua 2 ví dụ
mô phỏng để học sinh hiểu
hơn về thuật toán
Trả lời.
Nghe giảng.
Lên bảng dán sơ đồ
khối của bài toán.
Nghe giảng và trả lời.
Nghe giảng và trả lời.
không có ước số trong
phạm vi từ 2 đến phần
nguyên căn bậc 2 của N
thì N là số nguyên tố.

Thuật toán:
a. Cách liệt kê:
 B1: Nhập số
nguyên dương N.
 B2: Nếu N = 1
thì thông báo N không
là số nguyên tố rồi kết
thúc.
 B3: Nếu N < 4
thì thông báo N là số
nguyên tố rồi kết thúc.
 B4: i  2
 B5: Nếu

- Hiểu một số thuật toán thông dụng.
2. Về 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.
3. Về tư duy và thái độ:
- Dùng để tìm thuật toán cho các bài toán khác…
- Tích cực trong học tập và rèn luyện tính chính xác.
II. CHUẨN BỊ
1. Giáo viên: Máy tính Projecter, sách giáo khoa, sách giáo viên, giáo án, …
2. Học sinh: Tập soạn bài, sgk, đồ dùng học tập.
III. PHƯƠNG PHÁP VÀ PHƯƠNG TIỆN DẠY HỌC
- Phương pháp: Sử dụng các phương pháp,dạy học cơ bản sau một cách
linh họat nhằm giúp học sinh tìm tòi,phát hiện,chiếm lĩnh tri thức. Gợi mở vấn đáp,
thảo luận. Phát hiện và giải quyết vấn đề. Đan xen hoạt động nhóm.
VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí
- Phương tiện: Bảng phụ và các phiếu học tập, Computer và projector (nếu
có).
IV. TIẾN TRÌNH BÀI HỌC
1. Ổn định lớp, Kiểm tra sĩ số
2. Kiểm tra bài cũ:
- Khái niệm thuật toán là gì? Thuật toán có các tính chất nào? Hãy
xác định Input và Output của bài toán giải phương trình bậc hai: ax
2
+
bx + c = 0?
3.Tiến trình bài học mới:
TG HOẠT ĐỘNG CỦA
GIÁO VIÊN
HOẠT ĐỘNG CỦA HS NỘI DUNG BÀI DẠY
VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí

hình)
+ Các nhóm thảo luận và
trình bày theo thuật toán
các lần duyệt bài toán
+ Hs đưa ra ý tưởng, thảo
luận nhiều ý tưởng khác
nhau.
+ Hs trao đổi, thảo luận.
+ Hs phát biểu từng bước
liệt kê sơ đồ khối.
+ Hs lần lượt vẽ các bước
sơ đồ khối theo các bước.
+ Các nhóm thảo luận
trình bày.
Ví dụ 2: Bài toán sắp xếp
Cho dãy A gồm N số nguyên
a
1
, a
2
, a
3
, …,a
N
. Cần sắp xếp
các số hạng để dãy A trở thành
dãy không giảm (tức là số
hạng trước không lớn hơn số
hạng sau)


i  i + 1
đưa ra A rồi
kết thúc
đúng
Sai
Sai
đúng
Tráo đổi a
i
và a
i+1
VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí
sau?
Sơ đồ khối cho thuật toán.
( Sử dụng máy chiếu minh
họa)
4. Củng cố :
-Sắp xếp dãy số nguyên từ lớn đến nhỏ (dãy số giảm).
5. Dặn dò:
- Xem lại bài đã học
- Chuẩn bị phần tiếp theo của bài học “Thuật toán tìm kiếm tuần tự”.
6. Rút kinh nghiệm:
Tuần…….
Tiết …….
§4. BÀI TOÁN VÀ THUẬT TOÁN (tiết 4)
VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí

I. Mục tiêu
1. Về kiến thức :
- Biết 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.

NỘI DUNG BÀI DẠY
Trong cuộc sống
chúng ta, thường
xảy ra việc tìm
kiếm. Chảng
hạn: tìm kiếm
tên của 1 học
sinh trong 1 lớp,
tìm 1 quyển sách
trong thư viện.
Điều quan tâm ở
đây là tìm kiếm
như thế nào?
? Ví dụ: 5 7
1 4 2
+ k = 2  I
= ?
+ k = 6  I = ?
? Nêu các bước
giải bài toán?
+ Ghi bài.
+ Cho ví dụ tìm
kiếm 1 đối
tượng nào đó.
+ Suy nghĩ
+ I = 5
+ Không có i
* Xác định bài
toán:
Input:

Output: chỉ số I mà a
i
= k.hoặc không
có số hạng nào.
* Ý tưởng. Tìm kiếm tuần tự một cách
tự nhiên. Lần lượt từ số hạng thứ 1, so
sánh các số hạng đến khi gặp số hạng
bằng khóa, hoặc không có giá trị nào
bằng khóa.
* Thuật toán.
B1: Nhập N, các số hạng khác nhau
VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí
+ Học sinh nêu
các bước của
thuật toán?
Những điều cần
lưu ý.
+ Mời học sinh
lần lượt vẽ sơ đồ
khối.
+ Cho dãy số bất
kỳ. Các em thực
hiện theo thuật
toán tìm chỉ số i.
* Lưu ý:
B1: Các số khác
nhau.
B3 và B5 lưu ý
các biểu thức
điều kiện.

i  1
a
i
= k ?
Đúng
Đưa ra i rồi
kết thúc
Sai
i  i + 1
i > N ?
Đúng
Dãy A không có số hạng
bằng k, rồi kết thúc
Sai
Dãy A có N = 7 khóa k = 10
Tìm chỉ số i để a
i
= k.
i 1 2 3 4 5 6 7
a
i
7 12 4 6 11 10 8
k = 10

i = 6
* Ghi chú:
Trong thuật toán trên, i là biến chỉ số
và nhận giá trị nguyên lần lượt từ 1 đến
VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí
+ Trong thuật

Cho N và dãy số a
1
,a
2
,…,a
N
, hãy cho bết có bao nhiêu số hạng trong dãy
có giá trị bằng 0.
5. Dặn dò:
- Xem lại bài đã học
- Chuẩn bị phần tiếp theo của bài học “Thuật toán tìm kiếm nhị phân”.
6. Rút kinh nghiệm:
VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí
Tuần…….
Tiết …….
§4. BÀI TOÁN VÀ THUẬT TOÁN (tiết 5)

I. Mục tiêu
1. Về kiến thức :
Biết 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.
Hiểu 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.
Hiểu một số thuật toán thông dụng.
2. Về 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.
3. Về tư duy và thái độ:
Học sinh cần nhận thức được tầm quan trọng của môn học, vị trí của môn
học trong hệ thống kiến thức phổ thông và những yêu cầu về mặt đạo đức trong xã
hội tin học hóa
II. CHUẨN BỊ

+ Các em chia thành
2 dãy dãy con.
+ Chỉ số ở giữa dãy
là bao nhiêu? So
sánh a
giua
với khóa
k?
+ Các em thảo luận
để hình thành ý
tưởng cho bài toán?
+ Cho dãy số
tăng dần.
+ Chia:
Dãy 1: 2 4
5
Dãy 2: 6 9
13
Ta thấy tìm
kiếm trên dãy
1 có giá trị
bằng k
+ Giữa = 3.
+ a
giua
= 5 > k
nên ta tìm trên
dãy 1.
+ Các nhóm
thảo luận và

= k  tìm đợc chỉ số, kết thúc;
- Nếu a
giua
> 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ừ
VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí
+ Học sinh thảo luận
trình bày các bước
cho thuật toán và vẽ
sơ đồ khối?
+ Gọi 2 nhóm thực
hiện vẽ sơ đồ khối?
+ Chiếu hình ảnh
các học sinh còn lại
ghi bài.
+ Lấy ví dụ:
K = 21 và N = 10
(SGK) minh họa
chạy theo thuật toán
sơ đồ khối.
+ Mời 1 học sinh
cho 1 khóa k bất kỳ
để chạy thuật toán
với các số hạng
trên?
+ Ghi ý tưởng
của bài toán.
+ Lần lượt
các hs lên
bảng.

> 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.
b) Sơ đồ khối
SGK Trang 43
Dưới đây là ví dụ mô phỏng các bước thực hiện
thuật toán trên.
VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí
+ Phát phiếu học tập
(ví dụ mô phỏng với
dãy gồm 10 số
nguyên cho trước),
các nhóm thảo luận
trình bày.
+ Học sinh
thực hiện.
+ Vẽ sơ đồ
khối.
+ Các nhóm
thực hiện và
trình bày.
k = 21, N =10
k = 25, N =10
i 1 2 3 4 5 6 7 8 9 1

0
7 7 7
Giu
a
5 8 6 Giu
a
5 8 6 7
a
Giu
a
9 3
0
2
1
a
Giu
a
9 3
0
2
1
2
2
L-ît 0 1 2 Lư
ợt
0 1 2 3 4
Lần lượt thứ hai thì a
Giua
= k.
Vậy chỉ số cần tìm là i =

- Xây dựng được thuật toán giải một số bài toán bằng sơ đồ khối hoặc liệt
kê các bước.
3. Về tư duy và thái độ:
- Học sinh cần nhận thức được tầm quan trọng của môn học, vị trí của môn
học trong hệ thống kiến thức phổ thông và những yêu cầu về mặt đạo đức trong xã
hội tin học hóa.
II. CHUẨN BỊ
1. Giáo viên: Máy tính Projecter, sách giáo khoa, sách giáo viên, giáo án, …
2. Học sinh: Tập soạn bài, sgk, đồ dùng học tập.
III. PHƯƠNG PHÁP VÀ PHƯƠNG TIỆN DẠY HỌC
VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí
- Phương pháp: Sử dụng các phương pháp,dạy học cơ bản sau một cách
linh họat nhằm giúp học sinh tìm tòi,phát hiện,chiếm lĩnh tri thức. Gợi mở vấn đáp,
thảo luận. Phát hiện và giải quyết vấn đề. Đan xen hoạt động nhóm.
- Phương tiện: Bảng phụ và các phiếu học tập, Computer và projector (nếu
có).
IV. TIẾN TRÌNH BÀI HỌC
1. Ổn định lớp, Kiểm tra sĩ số.
2. Kiểm tra bài cũ:
- Cho dãy A và N số nguyên tăng dần, hãy tìm khóa k (sử dụng thuật toán
tìm kiếm nhị phân).
3.Tiến trình bài học mới:
Nội dung: Giúp hs hiểu vận dụng được kiến thức để giải bài toán. Khi xây dựng
thuật toán thì phải thực hiện thông qua các bước sau:
+ Xác định bài toán.
+ Ý tưởng để giải bài toán.
+ Xây dựng thuật toán.
TG HOẠT ĐỘNG CỦA
GIÁO VIÊN
HOẠT ĐỘNG CỦA HỌC