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

Ngày soạn : / /2006	Tiết thứ : 10 
Ngày giảng: / /2006	Tên bài giảng: Đ4. Bài toán và thuật toán 
I. Mục đích, yêu cầu
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.
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 : Tìm giá trị lớn nhất của một dãy số nguyên.
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.
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), các hình vẽ bằng sơ đồ khối.
III. Tiến trình bài giảng
1. Kiểm tra bài cũ :
Cho biết khái niệm chương trình? (Chương trình là một dãy lệnh, mỗi lệnh là một chỉ dẫn cho máy tính biết điều cần làm )
2. Vào bài mới(3’) : 
Để viết được chương trình cho máy tính thực hiện ta cần biết thế nào là bài toán và thuật toán. Ta sang bài mới ngày hôm nay: Bài toán và thuật toán.
2. Nội dung bài mới : 
Nội dung
Phương pháp
TG
1. Khái niệm về bài toán
- Bài toán là việc nào đó ta muốn máy tính thực hiện.
- Khi dùng máy tính giải bài toán, ta cần quan tâm đến hai yếu tố: đưa vào máy thông tin gì (Input) và cần lấy ra thông tin gì (Output), và mối quan hệ giữa Input và Output.
- Ví dụ 1. Bài toán tìm ước chung lớn nhất của hai số nguyên dương
Input: Hai số nguyên dương M và N;
Output: Ước chung lớn nhất của M và N.
Ví dụ 2. Bài toán tìm nghiệm của phương trình bậc hai
Input: Các số thực a, b, c (a ạ 0);
Output: Số thực x thoả mãn
ax2 + bx + c = 0.
ở đây, Output có thể là một hoặc hai số thực hoặc câu trả lời không có số thực nào như vậy.
Ví dụ 3. Bài toán kiểm tra tính nguyên tố
Input: Số nguyên dương N;
Output: "N là số nguyên tố" hoặc "N không là số nguyên tố". 
=> Ta thấy các bài toán được cấu tạo bởi hai thành phần cơ bản:
Input (giả thiết): Các thông tin đã có;
Output (kết luận): Các thông tin cần tìm từ Input.
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 một 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 được Output cần tì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: Số nguyên dương N và dãy N số nguyên a1,..., aN.
- Output: Giá trị lớn nhất Max của dãy số.
ã ý tưởng: + Khởi tạo giá trị Max = a1. 
 + Lần lượt với i từ 2 đến N, so sánh giá trị số hạng ai với giá trị Max, nếu ai > Max thì Max nhận giá trị mới là ai.
ã Thuật toán. Thuật toán giải bài toán này có thể được mô tả theo cách liệt kê như sau:
Bước 1. Nhập N và dãy a1,..., aN;
Bước 2. Max ơ a1, i ơ 2;
Bước 3. Nếu i > N thì đưa ra giá trị Max rồi kết thúc;
Bước 4.
	Bước 4.1. Nếu ai > Max thì Max ơ ai;
	Bước 4.2. i ơ i + 1 rồi quay lại bước 3;
GV giảng giải và vấn đáp
Yêu cầu HS lấy Vd về bài toán (đưa một dòng chữ ra màn hình, giải phương trình bậc hai, quản lí cán bộ của một cơ quan... )
Từ ví dụ đó yêu cầu học sinh phân tích dữ liệu vào và ra.
- Yêu cầu học sinh về nhà phân tích thêm một số ví dụ khác 
+ Ví dụ 3. Bài toán kiểm tra tính nguyên tố
Input: Số nguyên dương N;
Output: "N là số nguyên tố" hoặc "N không là số nguyên tố". 
+ Ví dụ 4. Bài toán xếp loại học tập của một lớp
Input: Bảng điểm của học sinh trong lớp;
Output: Bảng xếp loại học lực.
GV giảng giải và vấn đáp
- Việc chỉ ra tường minh một cách tìm Output của bài toán được gọi là một thuật toán (algorithm) của bài toán đó. Có nhiều định nghĩa khác nhau về thuật toán sau đây là một định nghĩa thường dùng.
- GV: Cho vd và yêu cầu hs xác định I/O của bàI toán
+ Giảng kĩ về ý tưởng cuả bài toán để hs hiểu
- HS làm việc độc lập
+ Phõn tích từ INPUT và OUT PUT
+ Lệt kê ra các dãy thao tác cần tiến hành.
+ Học sinh có nhận xét, đánh gía, bổ sung.. cho từng lời giải cụ thể
- 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
+ Giải thích rõ chức năng của các khối 
+ Cho học sinh quan sỏt SGK và mụ hỡnh.
+ Lấy vd mô phỏng việc thực hiện thuật toán với n= 11
- GV: Các bước trong cách biểu diễn bằng liệt kê hoặc các hình khối trong cách biểu diễn bằng sơ đồ khối có duy nhất cho một thuật toán hay không? ( )
Câu trả lời dựa vào việc phân tích ví dụ: tính D
15
5’
IV. Củng cố, bài tập: 
1. Củng cố: 
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ểu diễn thuật toán bằng sơ đồ khối và bằng liệt kê các bước. 
Bài toán : Tìm giá trị lớn nhất của một dãy số nguyên.
Biểu diễn bằng hai cách : 
Liệt kê 
Sơ đồ khối
Làm bài tập trắc nghiệm: 
2. Bài tập:
bài 4 SGK - Tr 44
V. Rút khinh nghiệm giảng dạy: