Giáo án Tin học 10 tiết 15: Bài tập

Ngày soạn : 25/10/2006	Tiết thứ : 15 
Ngày giảng: 26/10/2006	Tên bài giảng: Đ4. Bài tập.
Mục đích, yêu cầu
1. Kiến thức.
- Hiểu biết của HS qua bài 4. bài toán và 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
Kiểm tra tính nguyên tố của một số nguyên dương
Thuật toán sắp xếp bằng tráo đổi
Thuật toán tìm kiếm tuần tự
Thuật toán tìm kiếm nhị phâ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 : Tìm giá trị lớn nhất của một dãy số nguyên, Kiểm tra tính nguyên tố của một số nguyên dương, Thuật toán sắp xếp bằng tráo đổi, Thuật toán tìm kiếm tuần tự, Thuật toán tìm kiếm nhị phâ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.
Nội dung
Kiểm tra bài cũ ( ):
Vào bài mới( ) : 
Nội dung bài mới : 
Nội dung
Hoạt động của giáo viên và học sinh
TG
Câu 1: Hãy chỉ ra tính dừng của thuật toán tìm kiếm tuần tự.
Trả lời: Chỉ số i mỗi lần tăng một đơn vị nên nếu có số hạng của dãy bằng giá trị cần tìm thì hiển nhiên thuật toán thực hiện hữu hạn bước (vì ít hơn N bước mà N là hữu hạn). Với 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à việc thực hiện thuật toán kết thúc sau hữu hạn bước.
Câu 2: Hãy phát biểu một bài toán và chỉ rõ Input và Output của bài toán đó.
Câu 3: Dãy các thao tác sau:
	Bước 1. 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?
	Các việc nêu trong bài tập không phải là thuật toán vì tuy số bước mô tả là hữu hạn nhưng việc thực hiện là vô hạn, không dừng.
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.
Câu 4: Cho N và dãy số a1,..., aN, hãy tìm giá trị nhỏ nhất (Min) của dãy đó.
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ị Min rồi kết thúc;
Bước 4.
	Bước 4.1. Nếu ai < Min thì Max ơ ai;
	Bước 4.2. i ơ i + 1 rồi quay lại bước 3;
Câu 5: Tìm nghiệm của phương trình bậc hai tổng quát: ax2 + bx + c = 0.
I: a, b, c
O: Kết luận về nghiệm của ptb2: ax2+bx+c=0
Bước 1. Nhập a, b, c ( a#0);
Bước 2.D ơ b2- 4ac;
Bước 3.Nếu D< 0 thi thông báo phươnh trình vô nghiệm rồi kết thúc.
Bước 4.Nếu D=0 thì x ơ ; thông báo phương trình có nghiệm kép x rồi kết thúc;
Bước 5 Nếu D>0 thì x ơ thông báo phương trình có nghiệm hai nghiệm phân biệt x1,2 rồi kết thúc;
Câu 6: Cho N và dãy số a1,..., aN, hãy sắp xếp dãy số đó thành dãy số không tăng (số hạng trước lớn hơn hay bằng số hạng sau).
Nhập N, các số hạng a1, a2,..., aN;
M ơ N;
Nếu M < 2 thì đưa ra dãy A đã được sắp xếp rồi kết thúc;
M ơ M – 1, i ơ 0;
i ơ i + 1;
Nếu i > M thì quay lại bước 3;
Nếu ai < ai+1 thì tráo đổi ai và ai+1 cho nhau;
Quay lại bước 5.
Câu 7: 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.
Nhập N, các số hạng a1, a2,..., aN ;
i ơ 1; count ơ 0;
Nếu i > N thì thông báo chỉ số count, rồi kết thúc;
Nếu ai = 0 thì count ơ count + 1;
i ơ i + 1; rồi quay lại Bước 3.
GV: Dãy các việc nêu trong bào tập không phải là một thuật toán ví tuy số bước trong mô tả thuật là hứu hạn nhưng việc thưch hiện là vô hạn.
GV: Mục tiêu là để củng cố thêm sự hiểu biết của HS về thuật toán tìm Max nên: thay biến Max bằng biến Min và thay phép so sánh ở bước 4.1 theo chiều ngược lại.
GV: Vì ý tưởng lời giải HS đã biết, do vậy ở đây chỉ yêu cầu vận dụng các hiểu biết để mô tả đúng thuật toán bằng cách do HS tuỳ chọn.
GV: áp dụng tương tự với bài toán và thuật toán sắp xếp nổi bọt: thay dãy bất đẳng thức ở bước 7 thành ai < ai+1.
GV: áp dụng tư tưởng thuật toán tìm kiếm tuần tự và thêm một biến đếm để đếm số lượng số 0 trong dãy số, duyệt bắt đầu từ a1 đến aN, nếu ai = 0 thì tăng biến đếm số lượng lên 1 (ban đầu biến đếm được khởi tạo có giá trị bằng 0), thuật toán kết thúc sau N lần so sánh. 
5’
5’
5’
7’
7’
8’
8’
IV. Củng cố, bài tập: (3’)
1. Củng cố: 
2. Bài tập : 1.41; 1.42; 1.43; 
V. Rút khinh nghiệm giảng dạy: