Ngày soạn: 06/10/2008
Bài 4: BÀI TẬP
A. MỤC TIÊU
1. Kiến thức:
Vận dụng lý thuyết đã học giải quyết một số bài toán đề ra.
Nắm được cách viết một số thuật toán đơn giản .
2. Kỹ năng:
Vận dụng thuật toán để giải quyết các bài toán khác.
3. Thái độ:
Rèn luyện cho HS tư duy logic, làm việc có khoa học.
B. PHƯƠNG PHÁP:
Hướng dẫn học sinh làm bài tập.
C. CHUẨN BỊ CỦA GIÁO VIÊN VÀ HỌC SINH:
1. Chuẩn bị của GV: SGK, SBT
2. Chuẩn bị của HS: SGK, SBT
D. TIẾN TRÌNH LÊN LỚP:
1. Ổn định lớp: Ồn định lớp kiểm tra sĩ số.
2. Kiểm tra bài cũ:
Viết thuật toán dưới dạng sơ đồ khối của bài toán: nhập từ bàn phím 3 số nguyên dương và kiểm tra xem 3 số này có thể trở thành số đo 3 cạnh của một tam giác hay không?

3. Bài mới:
a, Đặt vấn đề:
Để hiểu tốt hơn về bài toán và thuật toán hôm nay chúng ta cùng làm một số bài toán căn bản.
b, Triển khai bài:
HOẠT ĐỘNG CỦA THẦY VÀ TRÒ
NỘI DUNG KIẾN THỨC


GV: gọi học sinh viết thuật toán sắp trao đổi theo chương trình phân phối của SGK
HS: lên bảng viết sơ đồ khối của bài toán.
GV: Gọi học sinh thứ hai lên bảng viết sơ đồ khối theo yêu cầu so sánh của bài tập.
HS: lên bảng viết sơ đồ khối
GV: Nhận xét đánh giá kết quả và sửa sai nếu có.
GV: cho một dãy A cụ thể
3 5 4 1 2
GV: gọi 2 học sinh lên dựa vào 2 sơ đồ khối đó mô phỏng bài toán.
HS: hai học sinh lên mô phổng theo 2 sơ đồ khối khác nhau
GV: Dựa vào các bước thực hiện của hai thuật toán trên cho học sinh nhận xét về độ chính xác , gọn nhẹ,
HS: Nhận xét thông qua mô phỏng của bài toán theo hai cách






GV:Tổ chức cho học sinh lên bảng viết thuật toán dưới dạng liệt kê và sơ đồ khối.
HS: hai học sinh lên bảng viết thuật toán dạng liệt kê và dạng sơ đô khối
GV: Từ thuật toán dạng liệt kê nếu chúng ta chuyển bước 5 lên sau bước 2 thuật toán sẽ thay đổi như thế nào?
HS: lên bảng thực hiện việc thay đổi này.
GV: Nhận xét bài làm và đưa ra một trường hợp cụ thể cho dãy

Ví dụ N=4 K=8
12 23 6 8

HS: Chạy bài toán trên dựa vào các bước liệt kê.
HS: Rút ra nhận xét sau khi thay đổi;
GV: Bổ sung.

GV: Gọi học sinh lên bảng viêt thuật toán dạng liệt kê của bài toán kiểm tra một số nguyên tố.
HS: lên bảng viêt thuật toán.
GV : Dựa vào các bước đó hãy mô phỏng thuật toán trên với N=37

=6

I
2 37 không chia hết cho 2
3 37 không chia hết cho 3
4 37 không chia hết cho 4
5 37 không chia hết cho 5
6 37 không chia hết cho 6
7
Đến đây i>
nên Kết luận số 37 là số nguyên tố.

GV: Tổ chức cho học sinh xem lai thuật toán tìm kiếm nhị phân.
HS: Lên bảng thực hiện thuật toán với input đã cho.
Với dãy A và khoá K=7
3 5 7 9 15 20 21 29 30 50

Dau Giua Cuoi Sosánh
1 5 10 a5=15>7
1 2 4 a2=5<7
3 3 4 a3=7=k

Thông báo chỉ số cần tìm là 3


GV : Trong thuật toán sắp xếp có thao tác đổi chổ ai với ai+1 cho nhau. Vậy hai giá trị này được trao đổi như thế nào. Chúng ta đi hoán đổi giá trị của hai biến A và B thông qua biến trung gian C

GV: Nêu ý tưởng
HS: Tình bày:
Ta thực hiện như sau:
C ← A;
A ← B;
B ← C;
Qua ba bước trên chúng ta đã hoán đổi được giá trị của hai biến A và B.
GV: Trong trường hợp không dùg biến trung gian C ta làm thế nào.
HS: Nêu ý tưởng của mình.
GV: Đưa ra cách giải quyết:
A ← A+B;
B ← A - B;
A ← A – B;