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

Bài 4: BÀI TOÁN VÀ THUẬT TOÁN
A. Mục đích yêu cầu :
+ Kiến thức :
- Biết khái niệm bài toán và thuật toán, các tính chất 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.
+ Kĩ năng :
- Xây dựng thuật toán giải một bài toán đơn giản bằng sơ đồ khối hoặc liệt kê các bước.
B. Phương pháp : Diễn giải, vấn đáp .
C. Phương tiện : Sử dụng các hình minh họa sơ đồ khối của các bài toán.
NỘI DUNG
HĐ CỦA GV
HĐ CỦA HS
I. Khái niệm về bài toán
- Bài toán là một việc nào đó mà ta muốn máy tính thực hiện.
- Ví dụ : Giải bất phương trình, cho dòng chữ chạy ra màn hình.
- Để giải một bài toán cần lưu ý :
 + Input : cần đưa vào máy thông tin gì.
 + Output : cần lấy ra thông tin gì
- Ví dụ : 
 * Bài toán cộng trừ hai số
Input : Hai số nguyên a và b
Output : Tổng và hiệu của a, b
 * Giải phương trình bậc nhất ax+b=0
Input : Hai số nguyên a và b
Output : Tìm x sao cho ax + b = 0
 * Tính diện tích và chu vi hình chữ nhật.
Input : Chiều dài và chiều rộng của hình chữ nhật.
Output : Diện tích và chu vi của hình chữ nhật đó. 
Một số ví dụ khác :
+ Bài toán giải phương trình bậc 2
+ Bài toán tìm max, min cua 3 số
+ Bài toán sắp xếp 3 số theo thứ tự tăng dần.
- Diễn giải và vấn đáp
- Cho một vài ví dụ và hỏi HS Input và Output của ví dụ đó là gì?
- Đưa ra nhận xét và kết luận
- Học sinh nghe trình bày và ghi chép.
- Học sinh phát biểu.
I/ Khái niệm về thuật toán (Algorithm)
- Việc cho một bài toán là mộ tả rõ Input và Output cần tìm. Vấn đề là làm thế nào để tìm ra Output?
- 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 đó, từ Input của bài toán này ta nhận được Output cần tìm.
Vd : 
 * Giải phương trình bậc nhất ax+b = 0
Bước 1 : Nhập vào hai số nguyên a và b
Bước 2 : Nếu a = 0 thì x không xác định
Bước 3 : Nếu a ¹ 0 thì x = - b / a
Bước 4 : Đưa kết quả là nghiệm x
Ngoài cách liệt kê ra dãy các thao tác cần tiến hành, thuật toán còn được diễn tả bằng sơ đồ khối bằng cách dùng một số biểu tượng sau :
+ Thao tác so sánh
+ Thể hiện các phép toán
+ Thể hiện các thao tác nhập, xuất dữ liệu.
+ Quy định trình tự thực hiện các thao tác.
- Học sinh nghe trình bày và ghi chép.
- Học sinh nghe trình bày và ghi chép.
Nhập a,b
a = 0
b = 0
x = - b/a
PT vô nghiệm
PT vô số nghiệm
Xuất kết quả
Đ
Đ
S
S
III. Một số ví dụ về thuật toán :
 + Kiểm tra tính nguyên tố của 1 số nguyên dương (SGK – Trang 36, 37)
 + Thuật toán sắp xếp hoán đổi (Exchange Sort) hay còn gọi là sắp xếp nổi bọt (Bubble Sort) (SGK – Trang 38,40)
 + Thuật toán tìm kiếm tuần tự (Sequential Search) (SGK – Trang 40,41)
 + Thuật toán tìm kiếm nhị phân (Binary Search) (SGK – Trang 42,43)
D. TỔNG KẾT BÀI MỚI :
1/ Hãy phát biểu một bài toán và cho biết Input và Output của bài toán đó
2/ Hãy mô tả thuật toán giải các bài toán sau bằng cách liệt kê hoặc bằng sơ đồ khối
 + Cho N và dãy số a1 … aN , Tìm giá trị nhỏ nhất MIN của dãy đó.
 + Tìm nghiệm của PT bậc 2 tổng quát ax2 + bx +c = 0
 + Cho N và dãy a1 … aN, hãy sắp xếp dãy đó thành dãy số không tăng.
 + Cho N và dãy số a1 … aN, hãy cho biết có bao nhiêu số hạng trong dãy có giá trị bằng 0.
E. DẶN DÒ : Xem trước bài “NGÔN NGỮ LẬP TRÌNH”
F. RÚT KINH NGHIỆM :
Ò & Ï