Giáo án môn Tin học khối 10 - Tiết 13, 14 - Bài 4: Bài toán và thuật toán

Tiết dạy:	13 Chương I: MỘT SỐ KHÁI NIỆM CƠ BẢN CỦA TIN HỌC
Ngày soạn: 07/2009 	 Bài 4: BÀI TOÁN VÀ THUẬT TOÁN (tt)
Ngày dạy: 07/2009 
I. MỤC TIÊU:
Kiến thức: 	
	– 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
	Kĩ năng: 
	– Biết xây dựng thuật toán của một số bài toán thông dụng
	Thái độ: 
	– Luyện khả năng tư duy lôgic khi giải quyết một vấn đề nào đó.
II. CHUẨN BỊ:
	Giáo viên: – Giáo án + bảng vẽ các sơ đồ khối
	– Tổ chức hoạt động nhóm.
	Học sinh: SGK, vở ghi. Đọc bài trước.
III Phương Pháp dạy học
Thuyết trình, hỏi đáp, đặt vấn đề, so sánh
IV. HOẠT ĐỘNG DẠY HỌC:
	1. Ổn định tổ chức: Kiểm tra sĩ số lớp.
	2. Kiểm tra bài cũ:
	Hỏi: Nêu thuật toán xét tính nguyên tố của một số nguyên dương cho trước.
 Đáp: 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
	3. Giảng bài mới:
TL
Nội dung
Hoạt động của Giáo viên
Hoạt động của Học sinh
Hoạt động 1: Mô tả thuật toán sắp xếp bằng tráo đổi
20
III. Một số ví dụ (tt)
2. 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.
Đặ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.
· Tổ chức các nhóm thảo luận 
H. Hãy xác định Input và Ouput của bài toán?
· 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
· Hướng dẫn HS trình bày thuật toán (bằng pp liệt kê)
· 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ừ 0 M+1.
· HS trả lời: 1, 3, 4, 5, 6, 7, 7, 8, 10, 12.
· Các nhóm 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.	
· Các nhóm thảo luận đưa ra ý kiến
· Ghi lại sơ đồ thuật toán và hình dung ra các bước thực hiện thuật toán.
Hoạt động 2: Diễn tả thuật toán bằng sơ đồ khối
10
b) Sơ đồ khối:
Hoạt động 3: Mô phỏng việc thực hiện thật toán – Củng cố
10
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
	4. BÀI TẬP VỀ NHÀ:
	– 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.
V. RÚT KINH NGHIỆM, BỔ SUNG:
Tiết dạy:	 14 Chương I: MỘT SỐ KHÁI NIỆM CƠ BẢN CỦA TIN HỌC
Ngày soạn: 07/2009	 BÀI TOÁN VÀ THUẬT TOÁN (tt)
Ngày dayj: 07/2009
I. MỤC TIÊU:
Kiến thức: 	
	– 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.
	Kĩ năng: 
	– Biết xây dựng thuật toán của một số bài toán đơn giản.
	Thái độ: 
	– Luyện khả năng tư duy lôgic khi giải quyết một vấn đề nào đó.
II. CHUẨN BỊ:
	Giáo viên: – Giáo án + bảng vẽ sơ đồ khối
	– Tổ chức hoạt động nhóm.
	Học sinh: SGK, vở ghi. Đọc bài trước.
III Phương Pháp dạy học
Thuyết trình, hỏi đáp, đặt vấn đề, so sánh
IV. HOẠT ĐỘNG DẠY HỌC:
	1. Ổn định tổ chức: Kiểm tra sĩ số lớp.
	2. Kiểm tra bài cũ:
	Hỏi: Nêu ý tưởng thuật toán sắp xếp bằng tráo đổi?
Đáp: Ý 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
	3. Giảng bài mới:
TL
Nội dung
Hoạt động của Giáo viên
Hoạt động của Học sinh
Hoạt động 1: Hướng dẫn tim thuật toán giải bài toán
10
III. Một số ví dụ: (tt)
3. Ví dụ 3: Bài toán tìm kiếm
Cho dãy A gồm N số nguyên khác nhau: a1, a2, , aN và một số nguyên 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ố đó. 
a) Thuật toán tìm kiếm tuần tự 
	(sequential search)
 · Xác định bài toán
 - Input: Dãy A gồm N số nguyên khác nhau a1, a2, , aN và số nguyên k;
 - Output: Chỉ số i 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.
· Ý tưởng:
 - Tìm kiếm tuần tự là 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 một số hạng bằng khoá hoặc dãy đã được xét hết và không có giá trị nào bằng khoá. Trong trường hợp thứ hai dãy A không có số hạng nào bằng khoá.
· Thuật toán:
* Cách liệt kê:
 - B1: Nhập N, các số hạng a1, a2, , aN và khoá k;
 - B2: i 1;
 - B3: Nếu ai = k thì thông báo chỉ số 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.
Đặt vấn đề: Tìm kiếm là một việc thường xảy ra trong cuộc sống.
Cho dãy A gồm: 5, 7, 1, 4, 2, 9, 8, 11, 25, 51. Tìm i với ai = 2 ?
· Tổ chức các nhóm thảo luận
H. Hãy xác định bài toán?
· GV hướng dẫn HS tìm thuật toán giải bài toán.
· GV hướng dẫn HS trình bày thuật toán tìm kiếm bằng cách liệt kê.
· i là biến chỉ số và nhận giá trị nguyên lần lượt từ 1 đến N+1.
· i = 5
· Các nhóm thảo luận, đưa ra ý kiến
Đ. + Input: N, a1, a2, , aN, k
 + Output: i hoặc thông báo không có i
· Cho các nhóm trình bày ý tưởng.
· Các nhóm thảo luận và đưa ra thuật toán.
Hoạt động 2: Diễn tả thuật toán tìm kiếm bằng sơ đồ khối
5
* Sơ đồ khối:
Hoạt động 3: Mô phỏng việc thực hiện thuật toán
5
Mô phỏng việc thực hiện thuật toán với:
+ N = 10, k = 2
k = 2 vµ N = 10
A
5
7
1
4
2
9
8
11
25
51
i
1
2
3
4
5
-
-
-
-
-
Víi i = 5 th× a5 = 2.
Hoạt động 4: Hướng dẫn tìm thuật toán giải bài toán
10
b) Thuật toán tìm kiếm nhị phân (Binary Search)
· Xác định bài toán
 - Input: Dãy A là dãy tăng gồm N số nguyên khác nhau a1, a2, , aN và một số nguyên k
 - Output: Chỉ số i 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.
· Ý tưởng: Sử dụng tính chất dãy A là dãy tăng, ta tìm cách thu hẹp nhanh phạm vị tìm kiếm sau mỗi lần so sánh khoá với số hạng được chọn, ta chọn số hạng aGiữa ở " giữa dãy" để so sánh với k, trong đó Giưa = . Khi đó:
 - Nếu aGiưa = k thì Giưa là chỉ số cần tìm.
 - Nếu aGiưa> k thì do dãy A là dãy đã sắp xếp nên việc tìm kiếm tiếp theo chỉ xét trên dãy a1, a2, , aGiưa-1 .
 - Nếu aGiưa < k thì thực hiện tìm kiếm trên dãy aGiưa+1, aGiưa+2, , an. 
Quá trình trên sẽ được lặp lại một số lần cho đến khi hoặc đã tìm thấy khoá k trong dãy A hoặc phạm vi tìm kiếm bằng rỗng.
· Thuật toán:
* Cách liệt kê:
 - B1: Nhập N, các số hạng a1, a2, , aN và khoá k
 - B2: Dau 1,Cuoi N;
 - B3: Giưa = ;
 - B4: Nếu aGiưa = k thì thông báo chỉ số Giưa, rồi kết thúc;
 - B5: Nếu aGiưa > k thì đặt Cuoi = Giưa - 1, rồi chuyển đến bước 7;
 - B6: Dau Giưa +1;
 - B7: Nếu Dau > cuoi thì thông báo dãy A không có số hạng nào có giá trị bằng k, kết thúc;
 - B8: Quay lại bước 3.
· Nhấn mạnh dãy A là một dãy tăng.
H. So sánh 2 bài toán tìm kiếm trong 2 thuật toán?
· GV hướng dẫn HS tìm thuật toán giải bài toán.
· Minh hoạ qua việc tra từ điển
Cho các nhóm thảo luận việc tra từ điển. Từ đó rút ra thuật toán.
Đ. Dãy A ở đây là dãy tăng
· Các nhóm trình bày cách làm
Hoạt động 5: Mô tả thuật toán bằng sơ đồ khối
5
* Sơ đồ khối
Hoạt động 6: Mô phỏng việc thực hiện thuật toán
5
Mô phỏng việc thực hiện thuật toán với N = 10,k= 21
k = 21, N =10
i
1
2
3
4
5
6
7
8
9
10
A
2
4
5
6
9
21
22
30
31
33
Dau
1
6
6
Cuoi
10
10
7
Giua
5
8
6
aGiua
9
30
21
L­ỵt
1
2
3
 l­ỵt th ba th× aGiua = k. Vy ch s cÇn t×m lµ i = Giua = 6.
Hoạt động 7: Củng cố các kiến thức đã học
3
· GV cho HS nhận xét điểm khác biệt cơ bản của 2 thuật toán
· Các nhóm thảo luận và trình bày
	4. BÀI TẬP VỀ NHÀ: 
	– Mô phỏng việc thực hiện thuật toán với dãy số khác.
	– Bài 3, 7 SGK.	
V. RÚT KINH NGHIỆM, BỔ SUNG: