BÀI TẬP
Ngày soạn : 16/10/2007
Tiết : 15
Lớp : 10
I. MỤC TIÊU YÊU CẦU
- Kiến thức:
+ Củng cố khái niệm bài toán và thuật toán.
+ HS hiểu rõ hơn cách biểu diên thuật toán dùng sơ đồ khối và phương pháp liệt kê.
- Kĩ năng: HS biết viết thuật toán giải một số bài toán đơn giản theo phương pháp liệt kê và phương pháp dùng sơ đồ khối.
- Tư duy:
+ Rèn luyện tư duy lôgic và sáng tạo.
+ Tạo cho HS hứng thú ban đầu về thuật toán, là cơ sở của việc lập trình ở lớp 11.
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ũ. Kết hợp khi học bài mới.
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

Bài 1: (Trang 44 - SGK) (2’)
Hãy phát biểu một bài toán và chỉ õ Input, Output của bài toán.


Bài 2: (Trang 44 - SGK) (3’)
Dãy các thao tác sau :
Bước1: Xoá bảng.
Bước 2: Vẽ đường tròn.
Bước 3: Quay lại bước 1.
Có phải là thuật toán không? Tại sao?
- Dãy các việc nêu trong bài tập không phải là một thuật toán vì tuy số bước mô tả trong thuật toán là hữu hạn nhưng việc thực hiện là vô hạn.
Bài 3: Hãy chỉ ra tính dừng của thuật toán tìm kiếm tuần tự.(5’)


- Tính dừng thể hiện:
+ Trường hợp tìm thấy ai = k, thì kết thúc tại lần duyệt thứ i mà i ≤ N hữu hạn (mỗi lần i tăng lên một đơn vị).
+ Trường hợp trong dãy không có giá trị cần tìm thì sau N lần tăng i, mỗi lần một đơn vị thì
i >N và thuật toán kết thúc.

Bài 4: Cho N và dãy a1, a2,…,aN. Hãy tìm ra giá trị nhỏ nhất của dãy. (10’)








* Liệt kê:
- B1: Nhập N và dãy a1, …, aN.
- B2: Min ← ai; i ← 2;
- B3: Nếu i > N thì đưa ra giá trị Min và kết thúc.
- B4:
+ B 4.1: Nếu ai < Min thì Min← ai.
+ B 4.2: i ← i+1 rồi quay lại B3.






Bài 6: Cho N và dãy số a1,a2,…,an. Hãy sắp xếp dãy đó thành dãy không tăng.


- Sơ đồ khối thể hiện của thuật toán :



















Bài 7: Cho N và dãy a1,a2,…,aN . Hãy cho biết có bao nhiêu số hạng trong dãy có giá trị bằng 0.
+ B1: Nhập N, các số hạng a1,a2,…,aN.
+ B2: i ← 1; dem ← 0;
+ B3: Nếu ai = k thì
dem ← dem+1;
+ B4: i ← i+1;
+ B5: Nếu i > N thì đưa ra số các số hạng trong dãy bằng 0.
+ B6: Quay lại bước 3.
GV: Gọi 1 HS trình bày một bài toán và chỉ rõ Input, Output của bài toán.
GV: nhận xét.



GV: Gọi HS đọc đề bài bài 2.
GV: Gợi ý: Để xét dãy thao tác có phải là thuật toán không ta xét dãy các thao tác ấy có thoả mãn các tính chất của thuật toán hay không?
GV: Nhận xét và tóm lại.



GV: Gọi HS đọc đề bài bài 3.
GV: Gọi HS nhắc lại đặc điểm tính dừng của thuật toán
GV: Gợi ý cho HS: Kết quả của việc tìm kiếm xảy ra mấy khả năng? Và ở mỗi khả năng tính dừng thể hiện như thế nào?
GV: Nhận xét, cho điểm và đưa ra đáp án cuối cùng.




GV: Yêu cầu HS mô tả các thuật toán trong SGK bằng cách liệt kê hoặc bằng sơ đồ khối.
GV: Yêu cầu HS xác định Input, Output của bài toán.


GV: Gợi ý: thuật toán tìm Min có gì khác thuật toán tìm Max của một dãy