Giáo án Tin học 10 tiết 12: Bài toán và thuật toán

Ngày soạn : 14/10/2006	Tiết thứ : 12 
Ngày giảng: 16/10/2006	Tên bài giảng: Đ4. Bài toán và thuật toán 
Mục đích, yêu cầu
1. 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 : Bài toán sắp xếp.
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 : Thuật toán sắp xếp bằng tráo đổi bằng sơ đồ khối hoặc liệt kê các bước.
3. Thái độ.
- Thông qua thuật toán để rèn luyện tư duy cho HS. 
- Có thể nói rằng các kiến thức này không chỉ giúp ích cho HS tiếp tục học Tin học về sau mà quan trọng hơn là góp phần phát triển trí tuệ, khả năng tư duy để giải quyết vấn đề cho HS trong học tập cũng như trong công việc phục vụ xã hội.
Phương pháp, phương tiện giảng bài
Phương pháp: thuyết trình, vấn đáp.
Phương tiện: SGK, SGV, bảng phụ (đèn chiếu).
III. Tiến trình bài giảng
Kiểm tra bài cũ :
Nêu ý tưởng của thuật toán Kiểm tra tính nguyên tố của một số nguyên dương.
Mô phỏng thuật toán với N = 25; N= 51.
Vào bài mới(3’) : 
Trong cuộc sống, ta thường gặp những việc liên quan đến sắp xếp như học sinh xếp hàng theo thứ tự từ thấp đến cao, giáo viên xếp loại học lực học sinh trong lớp. Nói một cách tổng quát, cho một dãy đối tượng, cần sắp xếp lại vị trí các đối tượng theo một tiêu chí nào đó. 
Chẳng hạn, cho 10 chiếc cọc có chiều cao khác nhau, cần xếp lại sao cho cọc thấp ở trước, cọc cao ở sau. Giáo viên cho HS xem hình vẽ 22. 
Trong phạm vi bài ngày hôm nay ta chỉ xét đến bài toân đơn giản sau đây:
Nội dung bài : 
Nội dung bài giảng
Họat động của giỏo viờn và học sinh
TG
Bài toán : 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 (tức là số hạng trước không lớn hơn số hạng sau).
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 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ê
Nhập N, các số hạng a1, a2,..., aN;
M ơ N;
Nếu M < 2 thì đưa ra dãy A đã được sắp xếp rồi kết thúc;
M ơ M – 1, i ơ 0;
i ơ i + 1;
Nếu i > M thì quay lại bước 3;
Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau;
Quay lại bước 5.
ã Ghi chú: 
- Qua nhận xét trên, ta thấy quá trình so sánh và đổi chỗ sau mỗi lượt chỉ thực hiện với dãy đã bỏ bớt số hạng cuối dãy.
- Trong thuật toán, i là biến chỉ số các số hạng của dãy có giá trị nguyên thay đổi lần lượt từ 0 đến M + 1.
b) Sơ đồ khối
M ơ N
Nhập N và a1, a2,..., aN
M ơ M – 1; i ơ 0
M < 2 ? 
i > M ? 
Đúng
Sai
ai > ai+1 ?
i ơ i + 1 
Đưa ra A rồi kết thúc
kết thúc
Đúng
Sai
Sai
Đúng
Tráo đổi ai và ai+1
ã Ví dụ mô phỏng các bước thực hiện của thuật toán trên: 
Sắp xếp dãy: 6 1 5 3 7 8 10 7 12 4
GV : Yêu cầu một HS đứng lên đọc bài toán.
GV: Lấy vd, với A là dãy gồm các số nguyên: 6, 1, 5, 3, 7, 8, 10, 7, 12, 4, sau khi sắp xếp ta có dãy: 1, 3, 4, 5, 6, 7, 7, 8, 10, 12.
GV: Giới thiệu về thuật toán sắp xếp bằng tráo đổi.
GV: Yếu cầu HS xác định bài toán
HS: Xác định rõ được Input và output
GV: Xuất phát từ ví dụ minh hoạ yêu cầu HS đứng tại chỗ phát biểu ý tưởng của thuật toán.
HS: Dựa vào việc so sánh hai só đứng liền kề nhau.
GV: đúc kết lại và đưa ra ý tưởng 
HS dựa trên ý tưởng hãy đưa ra thuật toán 
GV: chốt lại thuật toán bằng PP liệt kê 
GV: Giải thích thêm 
+ 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. 
+ Tương tự, sau lượt thứ hai, giá trị lớn thứ hai được xếp đúng ở vị trí sát cuối,... 
+ Có thể vì thế mà sắp xếp bằng tráo đổi còn có tên gọi là sắp xếp nổi bọt (Bubble Sort). Cụ thể: hình dung, sau mỗi lượt có ít nhất một số hạng đã xếp đúng vị trí và không còn tham gia vào quá trình đổi chỗ nữa, giống như các bọt nước từ đáy hồ nổi dần và khi đã lên mặt nước rồi thì tan biến.
GV: Trong thuật toán sử dụng biến nguyên M có giá trị khởi tạo là N, sau mỗi lượt M giảm một đơn vị cho đến khi M < 2. 
GV: ngoài cách liệt kê để biểu diễn thuật toán người ta sử dụng pp sơ đồ khối
GV: Yêu cầu HS dựa vào cách liệt kê háy biểu diễn thuật toán bằng pp sơ đồ khối.
HS: Lên bảng trình bày.
GV: Yêu cầu một HS khác nhận xét bổ sung sau đó chốt lại. Sơ đồ khối bao gồm 9 khối: 
Mỗi khối là tương ứng một bước có xuất hiện thêm một khối đưa ra dãy A( khối xuất). 
GV: Đưa ra lần duyệt thứ nhất rồi sau đó yêu cầu HS thực hiện các bước sau tương tự:
2’
2’
5’
15’
5’
10’
10’
IV. Củng cố, bài tập: (3’)
1. Củng cố: 
Nêu lại thuật toán biểu diễn Thuật toán Thuật toán Sắp xếp bằng tráo đổi( Nhấn mạnh ở các bước2, bước3, 4, 6 )
2. Bài tập:
bài 6: SGK - Tr 44
V. Rút khinh nghiệm giảng dạy: