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

 Tiết 9:	 Ngày soạn: 20/09/2008
Bài 4: Bài toán và thuật toán
I- Mục tiêu:
	1. Về kiến thức:
- Hiểu được 2 khái niệm then chốt: Bài toán và thuật toán trong tin học
- Hiểu được cách giải bài toán mà về nguyên tắc có thể giao cho máy tính thực hiện
- Hiểu và thực hiện được một số thuật toán đơn giản trong sách giáo khoa như tìm giá trị lớn nhất của dãy số.
	2. Về kĩ năng:
- Diễn tả được thuật toán theo cách liệt kê hoặc bước đầu thể hiện được thuật toán bằng sơ đồ khối.
- Hiểu và diễn tả được một số bài toán cơ bản.
	3. Về thái độ:
Rèn luyện lòng say mê nghiên cứu tìm hiểu và tư duy khoa học. 
Tác phong làm việc độc lập sáng tạo, nâng cao lòng say mê học tập bộ môn.
II- Chuẩn bị:
	1. Giáo viên:
- Chuẩn bị tranh vẽ, máy tính và một số bài toán áp dụng để rèn luyện kỹ năng biẻu diễn thuật toán.
	2. Học sinh:
- Sách giáo khoa và máy tính ở nhà nếu có.
III- Hoạt động dạy học:
Hoạt động của giáo viên
Hoạt động của học sinh
ổn định lớp:
Bài cũ:
? Nguyên lí mã hoá nhị phân trong máy tính là gì? Thế nào là nguyên lí Phôn Nôi – man?
Bài mới:
Hoạt động 1
Giúp học sinh hiểu rõ khái niệm bài toán trong tin học:
- Phát vấn: Em hãy cho biết chương trình là gì?
Đặt vấn đề: Để 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.
Thuyết trình: Trong toán học ta nhắc nhiều đến khái niệm “bài toán” và ta hiểu đó là những việc mà con người cần phải thực hiện sao cho từ những dữ kiện ban đầu đã có phải tìm ra hay chứng minh một kết quả nào đó. Vậy khái niệm “bài toán” trong tin học có gì khác so với toán học không?
Giáo viên đưa ra một số ví dụ:
VD 1: Thực hiện quản lí một kỳ thi
VD2: Giải phương trình bậc nhất ax + b= c đều là các bài toán.
? Bài toán là g? đứng trước một bài toán công việc đầu tiên cần làm là gì?
Thuyết trình: Đúng vậy, ta cần đi xác định INPUT và OUTPUT của bài toán, từ đó giáo viên chốt lại kiến thức.
B Các yếu tố: Khi máy tính giải bài toán cần quan tân đến 2 yếu tố đó là gì?
- Yêu cầu học sinh tìm INPUT và OUTPUT từ hai ví dụ trên.
VD 3: Cho biết INPUT và OUTPUT của bài toán tìm UCLN của 2 số A và B?
VD 4: Cho biết INPUT và OUTPUT của bài toán giải phương trình bậc 2: ax2 + bx +c = 0;
Hoạt động 2: 
Đưa ra định nghĩa thuật toán và các cách diễn tả thuật toán.
Thuyết trình: Nếu muốn máy tính đưa ra output từ input đã cho thì ta phải có chương trình, nhưng muốn có chương trình ta phải xây dựng thuật toán của bài toán đó hãy nói cách khác ta phải tìm cách để giải bài toán đó. Cách giải bài toán đó trong tin học gọi là thuật toán. Vậy thuật toán là gì? 
Giáo viên đưa ra ví dụ yêu cầu học sinh nghiên cứu sách giáo khoa và đứng tại chỗ trả lời:
VD: Nêu cách giải bài toán giải phương trình bậc hai: ax2 + bx + c = 0.
Ghi bài lên bảng
? Các em có nhận xét gì về các bước thực hiện trên?
Từ đó giáo viên chốt lại kiến thức: Vậy thuật toán là gì?
Yêu cầu các em nghiên cứu sách giáo khoa và làm ví dụ sau:
VD: Tìm ước số chung lớn nhất của hai số nguyên dương A và B. Xác định INPUT và OUTPUT của bài toán, xây dựng thuật toán?
GV đưa ra một số bộ ví dụ cụ thể để giải thích học sinh hiểu thuật toán qua từng bước:
B1: Nhập A = 12; B = 8; " A > B
B3: A = A – B = 12 – 8 = 4, B = 8; " B > A;
B4: A = 4; B= B – A = 8 – 4 = 4; " A = B;
B5: UCLN (A, B) = 4
J Cách viết thuật toán như trên theo từng bước gọi là cách liệt kê, còn có cách làm khác để thể hiện thuật toán dùng bằng sơ đồ khối, các em về nghiên cứu sách giáo khoa tiết sau ta sẽ tìm hiểu cách thể hiện này thông qua ví dụ tìm giá trị lớn nhất của dãy số.
HS báo cáo sĩ số,
K Suy nghĩ và trả lời
K Suy nghĩ và trả lời:
Chương trình là một dãy các câu lệnh, mỗi lệnh là một chỉ dẫn cho biết điều mà máy tính cần thực hiện.
Nghe giảng và nghiên cứu sách giáo khoa
Suy nghĩ và trả lời
- Bài toán là những việc mà con người muốn máy tính thực hiện.
- Bài toán là một vấn đề cần giải quyết trong thực tế, để từ những dữ kiệu đã cho tìm được kết quả.
@ Thảo luận và trả lời:
Công việc đầu tiên là xác định đâu là giả thiết và kết luận, trong tin học là dữ kiện đã cho và đâu là cái cần tìm.
@ Thảo luận và trả lời:
- INPUT ( Thông tin đưa vào máy tính)
- OUTPUT ( thông tin cần lấy ra từ máy tính)
@ Thảo luận và trả lời:
VD 1: 
INPUT: SBD, họ tên, Đvăn, Đ toán, Đlí,
OUTPUT: Tổng điểm: dạng số
 Kết quả: đậu hoặc trượt
VD 2: 
INPUT: Các hệ số a, b bất kì
OUTPUT: Nghiêm của phương trình (nếu có) và thường là dạng số.
VD 3:
INPUT: A, B là hai số nguyên dương
OUTPUT: UCLN(A,B)
VD 4:
INPUT: a, b, c là các số thực
OUTPUT: Nghiệm x của phương trình.
@ Thảo luận và trả lời:
- Thuật toán là các thao tác tính toán giải bài toán, tìm ra kết quả cuối cần tìm.
Thuật toán là một hệ thống các quy tắc nhằm xác định một dãy các thao tác trên những đối tượng sao cho từ một bộ dữ liệu vào sau khi thực hiện xử lí ta đạt được mục tiêu định trước.
K Nghiên cứu sách giáo khoa và đứng tại chỗ trả lời câu hỏi:
INPUT: a, b, c là các số thực
OUTPUT: Nghiệm x của phương trình.
B1: Nhập a, b, c
B2: Tính 
B3: Nếu < 0 " phương trình vô nghiệm chuyển đến B6;
B4: Nếu = 0 " phương trình có nghiệm kép chuyển đến B6;
B5: Nếu > 0 " phương trình có hai nghiệm phân biệt x1, x2 chuyển đến bước 6
B6: Kết thúc.
K Suy nghĩ và trả lời:
- Các bước làm việc được sắp xếp theo một trình tự xác định
- Là một dãy hữu hạn các lệnh.
K Thuật 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 đó từ input của bài toán ta tìm được Output cần tìm.
K Suy nghĩ và lên bảng trình bày:
INPUT: A, B là hai số nguyên dương
OUTPUT: UCLN (A, B)
* Thuật toán:
B1: Nhập A, B
B2: Nếu A =B thì UCLN =A;
B3: Nếu A > B thì thay A = A – B; quay lại bước 2;
B4: Thay B = B – A quay lại bước 2
B5: Gán UCLN là A, rồi kết thúc.
K Nghe giảng và ghi nhớ lời dặn của giáo viên.
IV- Đánh giá cuối bài:
Nhắc lại những nội dung đã học:
Khái niệm bài toán trong tin học là gì?
Để giải quyết bài toán trong tin học ta phải xây dựng thuật toán. Vậy thuật toán là gì?
Biết cách thể hiện thuật toán dưới dạng liệt kê của một số bài toán đơn giản.
Một số câu hỏi trắc nghiệm làm tại lớp:
Câu 1: Khi dùng máy tính giải bài toán:
Ta cần xác định: Input và Output
Ta chỉ cần xác định Input
Ta chỉ cần xác định Output
Cả ba ý trên
Hãy lựa chọn phương án đúng nhất.
Câu 2: Phát biểu nào sau đây là sai?
Input là thông tin vào máy tính
Output là thông tin cần máy tính đưa ra
Input là mã chương trình
Lệnh được đưa vào máy tính dưới dạng mã nhị phân để lưu trữ, xử lí như các dữ liệu khác.
Hãy lựa chọn phương án đúng nhất.
Câu 3: Input của bài toán giải phương trình bậc hai là:
A) a, b, x	B) a, c, x	C) a, b, c	D- x, a, b, c
Hãy chọn phương án ghép đúng.
IV- Rút kinh nghiệm: