Giáo án mô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
Người soạn : Nguyễn Như Vũ
Lớp	: SP Tin K40 - ĐHSPTN
Ngày Soạn	: 24/11/2008
Giáo viên hướng dẫn: Lê Bích Liên
I. Mục đích yêu cầu:
Kiến thức: Tìm hiểu và nắm rõ thuật toán kiểm tra tính nguyên tố của một số nguyên tố.
Kĩ năng: Xây dựng được thuật toán và sơ đồ khối thuật toán của các thuật toán thông dụng khác.
II. Phương tiện dạy học:
Phương pháp :Thuyết trình và đặt câu hỏi gợi ý cho học sinh
Giáo viên: Sách giáo khoa, bảng phụ sơ đồ khối thuật toán kiểm tra số nguyên tố(SGK – T37).
 Học sinh: Sách giáo khoa.
III. Nội dung:
1. ổn định lớp
	Sĩ số:	Vắng:	Có phép:
2. Kiểm tra bài cũ:
- HS1(viết lên bảng): Hãy xác định Input và Output của bài toán sau.
Bài toán: Cho 3 cạnh a, b, c của tam giác ABC, tính diện tích S của tam giác đó.
Đáp án:
	Input: 3 số thực a, b, c (là 3 cạnh của tam giác)
	Output: Số thực S (diện tích tam giác ABC).
- HS2 (trả lời miệng): Nêu khái niệm thuật toán? Có mấy cách mô tả thuật toán? Là những cách nào?
Đáp án: 
	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 ấy, từ Input của bài toán ta nhận được Output cần tìm.
Có 2 cách để mô tả thuật toán:
Mô tả bằng cách liệt kê.
Mô tả bằng sơ đồ khối
 GV: Nhận xét và cho điểm.
3. Bài mới:
GV: Đặt vấn đề: ở tiết trước các em đã học thế nào là bài toán, thuật toán. Các em đã biết cách mô tả 1 thuật toán. Để rõ hơn chúng ta sẽ xét một số ví dụ sau đây.
Bài 4: Bài toán và thuật toán (Tiếp)
Nội dung
Hoạt động của GV và HS
3. Một số ví dụ về thuật toán:
Ví dụ 1: Kiểm tra tính nguyên tố của một số nguyên dương N.
a. Xác định bài toán:
Input: N là số nguyên dương.
Output: “N là số nguyên tố hoặc N không phải là số nguyên tố”.
b. ý tưởng
- N=1 thì N không là số nguyên tố.
- 1<N<4 thì N là số nguyên tố.
- N>=4 và không có ước số trong phạm vi từ 2 đến [] thì N là số nguyên tố.
Ví dụ N=13 ([]=3)
a=2, a=3 không là ước của N vậy N là số nguyên tố.
c. Thuật toán
Phương pháp liệt 
B1: Nhập số nguyên dương N.
B2: Nếu N=1 thì thông báo “ N không là nguyên tố” rồi kết thúc. 
B3: Nếu N<4 thì thông báo “ N là số nguyên tố” rồi kết thúc.
B4: i‹–2.
B5: Nếu i >[] thì thông báo “N là số 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 là số nguyên tố” rồi kết thúc.
B7: i ‹– i+1 rồi quay lại B5.
d. Mô tả thuật toán
VD1: Với N=29 ([])
i
2
3
4
5
6
N/ i
29/2
29/3
29/4
29/5
chia hết
ko
ko
ko
ko
VD2: N=55
GV: Đưa ra bài toán
GV: Để xác định bài toán ta phải xác định các yếu tố nào? Em hãy xác định bài bài toán trên.
HS: Trả lời.
GV: Nhận xét.
 Đưa ra Input, Output.
GV: Thế nào là số nguyên tố? Cho ví dụ về số nguyên tố.
HS: Trả lời.
GV: Một số được gọi là số nguyên tố nếu nó là số chỉ có hai ước số khác nhau là 1 và chính nó.
GV: Nếu N=1 thì N có là số nguyên tố không? Vì sao?
HS: Trả lời
GV: N=1 không phải số nguyên tố. Vì 1 chỉ có 1 ước là 1.
GV: N=2, N=3 thì N có là số nguyên tố không? Vì sao?
HS: Trả lời.
GV: N=2, N=3 là số nguyên tố. Vì có 2 ước phân biệt là 1 và chính nó.
GV: N= 8 có những ước nào?
HS: Trả lời.
GV: N=8 có ước là 1, 2, 4, 8
Một số bất kì (khác 1) luôn có ít nhất 2 ước là 1 và chính nó.
Nếu N có thêm ít nhất 1 ước a thì N sẽ có thêm ước b. Tích của a x b =N. Vậy ta chỉ cần kiểm tra a có phải là ước của N không.
Tương tự ta có ý tưởng thuật toán:
GV: Đưa ra ý tưởng 
HS: Ghi chép
GV: Dựa vào ý tưởng thuật toán thầy sẽ xây dựng thuật toán của bài toán.
GV: Vừa ghi bảng các bước và giải thích thuật toán.
B1: Nhập Input cho bài toán.
B2: N=1 chỉ 1 ước là 1 lên đưa ra thông báo N không là số nguyên tố.
B3: N<4 tức là N=2 hoặc N=3 thoả mãn. Đưa ra thông báo N là số nguyên tố. 
B4: Gán i=2. i nhận giá trị nguyên dương. i có tác dụng kiểm tra xem i có phải là ước của N hay không?
B5: i chạy từ 2 đến [] +1. Nếu i=[] +1 thì ta đã kiểm tra tất cả các giá trị của i. Vậy không có giá trị nào của i thoả mãn i là ước của N. N chỉ có ước là 1 và chính nó. Vậy N là số nguyên tố.
B6: Trong trường hợp N chia hết cho i. Vậy N có ít nhất là 3 ước. Đưa ra thông báo N không là số nguyên tố. Kết thúc thuật toán.
B7: Nếu N không chia hết cho i thì ta tăng biến i lên 1 đơn vị. Và quay trở lại kiểm tra 
i >[].
GV: Tương ứng với cách mô tả thuật toán bằng cách liệt kê. Ta cũng có mô tả thuật toán bằng sơ đồ khối.
GV: Trong sơ đồ khối người ta dùng hình thoi, chữ nhật, ô van và các mũi tên thể hiện thao tác gì.
HS: Trả lời.
GV: Nhận xét.
GV: Đưa treo bảng phụ (Sơ Đồ khối SGK - T37)
GV: Giải thích từng bước trong sơ đồ khối tương ứng với các bước mô tả bằng cách liệt kê: 
B1: Nhập giá trị Input (biểu diễn bằng hình ôvan): N
B2: Kiểm tra N(biểu diễn bằng hình thoi). N=1 đúng thì đưa ra thông báo N không là số nguyên tố rồi kết thúc. Nếu sai (N1) thì chuyển sang bước tiếp theo.
B3: Kiểm tra N<4? Nếu đúng thì Thông báo N là số nguyên tố rồi kết thúc. Nếu sai chuyển tới B4.
B4: Gán i ‹– 2 (biểu diễn bằng hình chữ nhật). Rồi chuyển sang B5
B5: Kiểm tra i >[]. Đúng thì thông báo N là số nguyên tố rồi kết thúc.
Sai chuyển sang B6.
B6: Kiểm tra N chia hết cho i.
Đúng thì thông báo N không là số nguyên tố rồi kết thúc.
Sai chuyển sang B7.
B7: Tăng biến i lên 1 đơn vị. Rồi quay lại B5 kiểm tra 
i >[]
GV: Để hiểu rõ hơn về thuật toán thầy có 1 vài ví dụ mô tả thuật toán.
GV: Đưa ra ví dụ và giải thích dựa vào sơ đồ khối.
B1: Nhập N=29.
B2: Kiểm tra 29=1 Sai chuyển sang B3.
B3: 29<4 Sai chuyển sang B4.
B4: i=2
B5: Kiểm tra 2> [] Sai
B6: Kiểm tra 29/2 Sai 
B7: i=3 Quay lại B5.
3> Sai. Kiểm tra 29/3 sai. Tăng i=4 [] đúng đưa ra thông báo 29 là số nguyên tố rồi kết thúc.
HS: Nghe giảng.
GV: Đưa ra ví dụ 2. Yêu cầu học sinh lên mô tả thuật toán trên.
HS: Lên bảng làm.
GV: Nhận xét.
4. Củng cố và dặn dò
Bài hôm nay thầy đã giới thiệu cho các em về thuật toán kiểm tra số nguyên tố của một số nguyên dương.
Yêu cầu về nhà các em làm bài sau: Cho 2 số nguyên dương bất kì mô phỏng việc thực hiện thuật toán trên
Về đọc trước ví dụ 2 trong SGK – T37
Nhận xét của Giáo Viên
................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................