CHƯƠNG I: MỘT SỐ KHÁI NIỆM CƠ BẢN CỦA TIN HỌC

Tiết 12
Bài 4: BÀI TOÁN VÀ THUẬT TOÁN (tt)

I). Mục tiêu bài học:

Về kiến thức:
Học sinh sau tiết học sẽ nắm được các vấn đề sau:
Biết khái niệm về bài toán và thuật toán. Đây là 2 khái niệm then chốt để hiểu được các khái niệm khác như chương trình và ngôn ngữ lập trình. Qua đó học sinh hình dung rõ hơn về cách thức hoạt động của máy tính.
Chỉ ra được Input và Output của mỗi bài toán đưa ra.
ví 2 toán.


Về thái độ:
Học sinh sẽ tò mò, thắc mắc về sự kỳ diệu của máy tính điện tử, từ đó gợi niềm say mê môn Tin học.
Hiểu được vai trò quan trọng của Tin học trong cuộc sống xã hội hiện đại.
Ý thức được nếu không có hiểu biết về Tin học thì khó có thể hoà nhập vào cuộc sống hiện đại.

II). Các phương pháp- phương tiện dạy học:

Phương pháp:
Phương pháp chủ yếu là thuyết trình, vấn đáp gợi mở, để học sinh tham gia tích cực vào bài học.

Phương tiện:
1. Chuẩn bị của giáo viên: Sách tin học 10, giáo án, chuẩn bị vài ví dụ cụ thể hơn để hướng dẫn rõ hơn về thuật toán.
2. Chuẩn bị của học sinh : Soạn bài, nghe giảng, đọc tài liệu, chuẩn bị trả lời các câu hỏi phía sau bài học.

III)- Tiến Trình Dạy Học:

+ Ổn định lớp
+ Điểm danh






TG
NỘI DUNG
GIÁO VIÊN
HỌC SINH


Hoạt động 2: Vào nội dung bài học
3. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN






8’

























15’






























15’


3. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN :
Ví dụ 2. Bài toán sắp xếp


Hình a


Hình b


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.


( 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. Để thực hiện điều đó 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.
- Trong thuật toán trê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




† 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 (h. 22a), cần xếp lại sao