&4. BÀI TOÁN VÀ THUẬT TOÁN
Ngày soạn : 4/10/2007
Tiết : 11
Lớp : 10
I. MỤC ĐÍCH YÊU CẦU (Như tiết 10)
II. CHUẨN BỊ
Thầy:
- Soạn giáo án, nghiên cứu sách giáo khoa, sách bài tập, tài liệu tham khảo.
- Máy tính cá nhân và máy chiếu ( nếu có).
Trò: Đọc trước ở nhà Sách giáo khoa.
III.TIẾN TRÌNH LÊN LỚP.
1. Ổn định tổ chức, kiểm tra sĩ số (1’).
2. Kiểm tra bài cũ (5’).
Câu hỏi: Nêu khái niệm thuật toán? Các tính chất của thuật toán?
Đáp án:
a)Khái niệm 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 ấy, từ Input của bài toán, ta nhận được Output cần tìm. (5đ)
b)Các tính chất của thuật toán: (5đ)
+ Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện các thao tác.
+ Tính xác định: Sau khi thực hiện một thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng một thao tác xác định để được thực hiện tiếp theo.
+ Tính đúng đắn: Sau khi kết thúc thuật toán, ta phải nhận được Output cần tìm.
- Đối tượng HS: HS trung bình.
3. Nội dung bài học mới.
Nội dung
Hoạt động của GV
Hoạt động của HS



3. Một số ví dụ về thuật toán

* Tìm giá trị lớn nhất của một dãy số nguyên. (15’)
* 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 nhận giá trị mới là ai.
* Thuật toán:
Liệt kê:
- B1: Nhập N và dãy a1, …, aN.
- B2: Max ← ai; i ← 2;
- B3: Nếu i > N thì đưa ra giá trị Max và kết thúc.
- B4:
+ B 4.1: Nếu ai > Max thì Max← ai.
+ B 4.2: i ← i+1 rồi quay lại B3.
- Sơ đồ khối:














Mô phỏng thuật toán.







Ví dụ 2: Kiểm tra tính nguyên tố của một số nguyên dương. (20’)



* Xác định bài toán:
- Input: N là một số nguyên dương.
- Output: N là số ngyên tố hoặc N không là số nguyên tố.

* Ý tưởng:
- Nếu N =1 thì N không là số nguyên tố.
- Nếu 1- Nếu N ≥ 4 và không có ước số trong phạm vi từ 2 đến phần nguyên căn bậc hai của N thì N là số nguyên tố.
* Thuật toán:
a) Cách liệt kê:
-B1: Nhập số nguyên dương N.
-B2: Nếu N=1 thì thông báo N không nguyên tố rồi kết thúc.
-B3: Nếu N<4 thì thông báo N là nguyên tố rồi kết thúc.
-B4: i ←2;
- B5: Nếu i>[
] thì thông báo N là nguyên tố rồi kết thúc.
-B6: Nếu N chia hết cho i thì thông báo N không nguyên tố rồi kết thúc.
-B7: i← i+1 rồi quay lại bước 5.
b) Sơ đồ khối:


















GV: Để hiểu rõ hơn về thuật toán ta lần lượt xem xét các ví dụ.

GV: Yêu cầu HS nêu Input, Output của bài toán.
GV: Nêu ra ví dụ, chẳng hạn tìm bạn nam cao nhất trong lớp và gọi HS nêu ý tưởng?



GV: Từ đó ta có ý tưởng về thuật toán tìm giá trị lớn nhất của một dãy số nguyên.

GV: Ghi lên bảng và giải thích từng bước của thuật toán:





GV: Từ các bước liệt kê, yêu cầu 1 HS lên bảng và vẽ sơ đồ khối, HS ở dưới lớp vẽ ra nháp.
GV: Gọi HS khác nhận xét bài trên bảng.
GV: Đưa ra nhận xét cuối cùng và ghi sơ đồ.
GV: