Giáo án môn Tin học 10 - Bài toán và thuật toán (tiếp)

$4. Bài toán và thuật toán (tiếp)
Tiết 12: Một số ví dụ về thuật toán
Ngày soạn : 
Ngày dạy:
Người soạn: Phạm Đình Thanh
GVHD: Lê Thị Bích Liên
Mục đích_Yêu cầu
Mục đích
Giới thiệu các cách biểu diễn thuật toán, các đặc trưng cơ bản của thuật toán – thuật toán kiểm tra tính nguyên tố của một số nguyên dương.
Hiểu rõ hơn về khái niệm thuật toán thông qua ví dụ cụ thể. 
Hình thành và phát triển tư duy lôgic, tư duy giải thuật. Góp phần phát triển nhân cách của con người trong xã hội tin học cho học sinh.
Yêu cầu
Nắm bắt được các bước của thuật toán kiểm tra tính nguyên tố của một số nguyên dương.
Hiểu và thực hiện được thuật toán kiểm tra tính nguyên tố của một số nguyên dương.
Phương pháp và đồ dùng học tập
Phương pháp :Thuyết trình và đặt câu hỏi gợi ý cho học sinh .
Đồ dùng học tập :
Sách giáo khoa, sách giáo viên. 
Bảng phụ: Vẽ sơ đồ khối của thuật toán kiểm tra tính nguyên tố của một số nguyên dương (trang 37).
Nội dung bài giảng
* Bảng phân phối thời gian
Nội dung
Thời gian
ổn định lớp
Kiẻm tra bài cũ
1’
10’
Đặt vấn đề
Xác định bài toán
ý tưởng
Thuật toán
Cách liệt kê
Sơ đồ khối
Ví dụ mô phỏng
1’
4’
5’
15’
10’
5’
5’
Củng cố 
4’
ổn định lớp
Lớp :Sĩ số:vắng:Có phép.Không phép:
Kiểm tra bài cũ
Câu hỏi 1: Khái niệm thuật toán và các tính chất của thuật toán ? (trả lời miệng)
Đáp án: Thuật toán để giải một bài toán là một dãy các 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.
Thuật toán có các tính chất:Tính xác định, tính dừng, tính đúng đắn.
Câu hỏi 2: Nêu các bước của thuật toán tìm giá trị lớn nhất của một dãy số nguyên ? (viết lên bảng)
Đáp án:
Các bước của thuật toán tìm giá trị lớn nhất là: 
Bước 1: Nhập N và dãy a1,a2,,aN;
Bước 2; Mãò a1, iò2;
Bước 3: Nếu i>N thì đưa ra giá trị Mã rồi kết thúc.
Bước 4:
Bước 4.1: Nếu ai> Mã thì max ò ai;
Bước 4.1: iòi+1 rồi quay lại bước 3;
3.Bài mới
Đặt vấn đề : Trong tiết học trước các em đã được tìm hiều hai khái niệm về bài toán và thuật toán. Để hiểu rõ hơn về khái niệm thuật toán hôm nay chúng ta sẽ tìm hiểu về thuật toán kiểm tra tính nguyên tố của một số nguyên dương.
Nội dung
Hoạt động của giáo viên và học sinh
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
 • Xác định bài toán:
Input: N là một số nguyên dương
Output: “N là số nguyên tố ” hoặc “N không là số nguyên tố ”.
• ý tưởng:
Định nhĩa số nguyên tố: Một số nguyên dương N là số nguyên tố nếu nó có đúng hai ước số khác nhau là 1 và chính nó.
Từ đó ta có: 
Nếu N=1 thì N không là số nguyên tố.
Nếu 1<N<4 thì N là số nguyên tố.
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ê:
Bước1: Nhập số nguyên dương N;
Bước 2: Nếu N=1 thì thông báo N không nguyên tố rồi kết thúc ;
Bước 3: Nếu N<4 thì thông báo N là nguyên tố rồi kết thúc;
Bước 4: i ò 2;
Bước 5: Nếu i> thì thông báo N là số nguyên tố rồi kết thúc;
Bước 6: 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;
Bước 7: iò i+1 rồi quay lại bước 5 
b)Sơ đồ khối (Bảng phụ)
Ví dụ: (SGK tr 37)
N=29 ([]=5)
i
2
3
4
5
6
N/i
29/2
29/3
29/4
29/5
Chia hết không
Không
Không
Không
Không
N=45 ([]=6)
i
2
3
N/i
45/2
45/3
Chia hết không
Không
Chia hết
GV: Cho các số sau: 5,9,10,6,11. Tìm số nguyên tố ?
GV: Trước khi trả lời câu hỏi trên em nào có thể cho biết số nguyên tố là số như thế nào ? 
HS: Đứng lên trả lời.
GV: Nhận xét và đưa ra kết quả các số nguyên tố là:5,11.
GV: Vậy thuật toán để xác định tính nguyên tố của một số nguyên dương là gì chúng ta đi vào bài hôm nay.
GV:Đầu tiên chúng ta xác định bài toán. Một em hãy xác định Input và Output của bài toán ?
HS: Đứng tại chỗ trả lời.
GV: Nhận xét và viết lên bảng câu trả lời.
GV: Nhắc lại định nghĩa số nguyên tố: 
Một số nguyên dương N là số nguyên tố nếu nó có đúng hai ước số khác nhau là 1 và chính nó.
GV: Theo định nghĩa trên thì số 1 không là số nguyên tố, số 2,3 là số nguyên tố.Còn các số >=4 thì ta thấy số 4,8,15, không là số nguyên tố, các số 7, 11, là số nguyên tố. Vậy để xác định một số nguyên dương là số nguyên tố thì ta làm như thế nào?
 GV: Để xác định được một số nguyên dương là một số nguyên tố người ta dựa vào khái niệm số nguyên tố và đưa ra ý tưởng như sau:
Nếu N=1 thì N không là số nguyên tố.
Nếu 1<N<4 thì N là số nguyên tố.
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ố.
GV: Chúng ta sẽ xét ví dụ mô phỏng ý tưởng trên.
- Với N=19 (Phần nguyên căn bậc hai của 19 là []=4)
i
2
3
4
5
N/i
19/2
19/3
19/4
Chia hết không
Không
Không
Không
-Với N=15 (Phần nguyên căn bậc hai của 15 là []=3)
i
2
3
N/i
15/2
15/3
Chia hết không?
Không
Chia hết
GV: Ta thấy 19 là số nguyên tố còn 15 không là số nguyên tố.
GV: Nhắc lại ý tưởng và yêu câu HS ghi lại ý tưởng.
HS: Ghi bài.
GV: Nêu thuật toán bừng cách liệt kê sau đó giải thích thuật toán.
Bước1: Nhập số nguyên dương N;
Bước 2: Nếu N=1 thì thông báo N không nguyên tố rồi kết thúc ;
Bước 3: Nếu N<4 thì thông báo N là nguyên tố rồi kết thúc;
Bước 4: Khởi tạo giá trị của i bằng 2.
Bước 5: Nếu i> thì thông báo N là số nguyên tố rồi kết thúc;
Chú ý là phần nguyên của N. 
Bước 6: 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; 
Tức là N có ước khác 1 và chính nó.
Bước 7:Tăng i lên một đơn vì rồi quay lại bước 5.
GV: Trong thuật toán này i nhận giá trị nguyên thay đổi trong phạm vi từ 2 đến +1 dùng để kiểm tra N có chia hết cho i hay không.
HS: Ghi bài
GV: Em nào cho thầy biết trong sơ đồ khối hình thoi, hình chữ nhật, hình ô van, các mũi tên thể hiện các thao tác gì. 
HS: Hình thoi thể hiện thao tác so sánh, Hình chữ nhật thể hiện các phép tính toán, hình ôvan thể hiện thao tác nhập, xuất dữ liệu, các mũi tên quy định trình tự thực hiện các thao tác.
GV: Treo bảng phụ mô phỏng thuật toán.
Giải thích sơ đồ khối đối. Chỉ ra các bước ở cách liệt kê tương ứng trên sơ đồ khối.
GV:Mô phỏng thuật toán bằng ví dụ SGK trang 37.
GV: Với N=29 thì []=?
HS: []=5
GV: Với i nhận các giá trị lần lượt từ 2 đến 5 thì 29 không chia hết i. Với i nhận giá trị là 6 > 5 thì thuật toán dừng. Vậy 29 là số nguyên tố.
GV: Với N=45 thì []=?
HS: []=6
GV: Với i=2 thì 45 không chia hết cho 2. Tăng i lên một đơn vị i=3 thì 45 chia hết cho 3 theo bước 6 thì N không là số nguyên tố.
 GV: Gọi học sinh lên mô phỏng với số 11,18.
HS: Lên bảng mô phỏng với ví dụ của GV.
N=11 ([]=3
i
2
3
4
N/i
11/2
11/3
Chia hết không
Không
Không
N=11 là số nguyên tố.
N=21 ([]=4
i
2
3
N/i
21/2
21/3
Chia hết không
Không
có
N=21 không là số nguyên tố
GV: Nhận xét bài làm của HS
Củng cố và bài tập về nhà
Củng cố :
Nắm chắc các bước của thuật toán kiểm tra tính nguyên tố của một số nguyên dương.
Đọc trước bài : Bài toán sắp xếp.
Nhận xét của GVHD