Tin học 8 - Tiết 13, 14 - Bài 4: Bài toán và thuật toán (tiếp)

Tuần 7	Ngày soạn: 10/09
Tiết 13,14	Ngày dạy:
§4. BÀI TOÁN VÀ THUẬT TOÁN (TT)
I. Mục tiêu
1. Kiến thức
- Học sinh biết khái niệm về Bài toán và thuật toán, các tính chất của thuật toán
- Học sinh chỉ ra được Input và Output của mỗi bài toán đưa ra.
2. Kỹ năng
 - Hiểu và nhận biết được Input và Output trong mỗi bài toán. 
3. Thái độ
 - Chú ý nghe giảng, hăng hái phát biểu ý kiến.
 - Có thái độ học tập nghiêm túc. 
II. Chuẩn bị của giáo viên và học sinh
 1. Chuẩn bị của giáo viên: SGK, Giáo án, Tài liệu tham khảo.
 2. Chuẩn bị của học sinh: SGK, vở ghi
III. Phương pháp: 
 Hướng dẫn giảng giải, minh họa trực quan, nêu câu hỏi để học sinh thảo luận trả lời.
 Hoạt động nhóm, hoạt động cá nhân
IV. Hoạt động dạy - học
 1. Ổn định tổ chức
 2. Kiểm tra bài cũ: 
 -Viết thuật toán tìm Max của dãy số nguyên bằng liệt kê
GV: Nhận xét và ghi điểm.
 3. Nội dung bài mới
Hoạt động của thầy và trò
Nội dung
GV: Số nguyên tố là gì? 
HS: Trả lời.
GV: Chốt lại: 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ó.
HS: Lắng nghe và ghi nhớ.
GV: Yêu cầu HS xác định bài toán.
HS: Xác định bài toán.
GV: Từ định nghĩa trên các em hãy thử nêu ý tưởng để giải bài toán?
HS: Trả lời.
GV: Mời HS lên viết và thử giải thích thuật toán (dưới dạng liệt kê).
HS: Thực hiện.
GV: Yêu cầu HS còn lại nhận xét và hoàn thiện.
HS: Trả lời.
GV: Gọi HS tự ra ví dụ và tự kiểm tra thuật toán.
HS: Thực hiện.
GV: Yêu cầu HS về nhà hoàn thiện thuật toán dưới dạng sơ đồ khối.
3. Một số ví dụ về thuật toán
a. Thuật toán 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:
- 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ố. ta có thuật toán như sau:
* Thuật toán
a. Cách liệt kê
Bước 1: Nhập số nguyên dương N
Bước 2: Nếu N=1 thì thông báo N không là số nguyên tố
Bước 3: Nếu N<4 thì thông báo N là số nguyên tố.
Bước 4: i <- 2
HS: Lắng nghe và ghi nhớ.
GV: Trong cuộc sống ta thường gặp những bài toán sắp xếp ví dụ sắp điểm từ thấp đến cao hay sắp xếp học sinh theo ABC.v.v... Hôm nay chúng ta đi tìm hiểu một số thuật toán sắp xếp cơ bản.
GV: Đưa ra ví dụ về thuật toán sắp xếp rồi cho học sinh xác định Input, Output và ý tượng thuật toán.
HS: Đứng tại chỗ trả lời.
GV: Ghi lên bảng và phân tích ý tưởng thuật toán rồi gọi học sinh lên bảng viết thuật toán.
HS: Lên bảng viết thuật toán
GV: Gọi học sinh khác nhận xét về thuật toán trên.
HS: Đứng tại chỗ nhận xét.
GV: Tổng hợp lại, chính sửa thuật toán cho phù hợp và phân tích các bước hoạt động của thuật toán.
GV: Yêu cầu HS về nhà hoàn thiện thuật toán dưới dạng sơ đồ khối.
HS: Lắng nghe và ghi nhớ.
GV: Trong cuộc sống tìm kiếm là việc thường xuyên xảy ra vi dụ tìm một quốn sách trên giá sách hay tìm một học sinh trong lớp .v.v... Hôm nay chúng đi tìm hiểu một số thuật tìm kiếm cơ bản.
GV: Đưa ra ví dụ bài toán
 Giải thích, gợi ý để học sinh đưa ra ý tưởng thuật toán.
HS: Xác định bài toán.
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. Bài toán sắp xếp:
Cho dãy A gồm N số nguyên a1, a2,..., aN. Cần sắp xếp các số hạng để dãy A trở thành dãy không giảm (tức là số hạng trước không lớn hơn số hạng sau).
Thuật toán Sắp xếp bằng tráo đổi (Exchange Sort)
* Xác định bài toán
- Input: Số nguyễn dương N, dãy a1, a2,., aN.
- Output: Dãy a1, a2,., aN được sắp xếp thành dãy không giảm.
* Ý tưởng: Ta so sánh lần lượt các cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau ta đổi chỗ chúng cho nhau. Việc đổi chỗ được lặp lại, cho đến khi không có sự đổi chỗ nào xảy ra nữa.
* Thuật toán
a) Cách liệt kê
Bước 1: Nhập N, và dãy a1, a2,..., aN;
Bước 2: M ¬ N;
Bước 3: Nếu M < 2 thì đưa ra dãy A đã được sắp xếp rồi kết thúc;
Bước 4: M ¬ M – 1, i ¬ 0;
Bước 5: i ¬ i + 1;
Bước 6: Nếu i > M thì quay lại bước 3;
Bước 7: Nếu ai > ai+1 thì đổi chỗ ai và ai+1 cho nhau;
Bước 8: Quay lại bước 5.
Ví dụ 3. Bài toán tìm kiếm.
+ Thuật toán Tìm kiếm tuần tự:
* Xác định bài toán
- Input: Dãy gồm N số nguyên đôi một khác nhau a1, a2,..., aN và số nguyên k;
- Output: Chỉ số i mà ai = k hoặc thông báo không có số hạng nào của dãy có giá trị bằng k.
GV: Cho học sinh lên bảng viết thuật toán.
HS: Lên bảng viết thuật toán
GV: Nhận xét, chỉnh sửa thuật toán cho đúng và cho ví dụ mô phỏng quá trình thực hiện thuật toán.
HS: Lắng nghe và ghi nhớ.
GV: Phân tích thuật toán kỹ lưỡng và cho học sinh về nhà tự vẽ sơ đồ khối của thuật toán
HS: Lắng nghe và ghi nhớ.
GV: Ngoài việc tìm kiếm theo thuật toán tuần tự trên ta còn có các cách tìm kiếm khác như tìm kiếm nhị phân. Việc tìm kiếm sẽ nhanh hơn thuật toán tìm kiếm tuần tự.
 Thuật toán tìm kiếm nhị phân sử dụng phép chia đệ trị nó thường áp dụng đối với dãy số đã được sắp xếp.
HS: Lắng nghe 
GV: Đưa bài toán trong sách giáo khoa
cho học sinh xác định bài toán và ý tưởng thuật toán.
HS: Đứng tại chỗ xác định bài toán và ý tượng thuật toán.
GV: Tổng hợp lại và bổ sung và đưa ra ý tưởng thuật toán, các ví dụ mô tả cho 
học sinh hiểu và so sánh với thuật toán tìm kiếm tuần tự. 
Lắng nghe và ghi nhớ.
GV: Hướng dẫn và yêu cầu HS về nhà hoàn thiện thuật toán.
HS: Xem sự hướng dẫn của giáo viên để về nhà viết thuật toán
* Ý tưởng: Lần lượt từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khoá k cho đến khi hoặc gặp một số hạng bằng khoá k hoặc dãy đã được xét hết và không có giá trị nào bằng khoá k. 
* Thuật toán
a) Cách liệt kê
Nhập N, các số hạng a1, a2,..., aN và khoá k;
i ¬ 1;
Nếu ai = k thì thông báo chỉ số i, rồi kết thúc;
i ¬ i + 1;
Nếu i > N thì TB dãy A không có số hạng nào có giá trị bằng k, rồi kết thúc;
Quay lại bước 3.
+ Thuật toán Tìm kiếm nhị phân:
 * Xác định bài toán
- Input: Dãy A là dãy tăng gồm N số nguyên đôi một khác nhau a1, a2,..., aN và một số nguyên k;
- Output: Chỉ số i mà ai = k hoặc thông báo không có số hạng nào của dãy A có giá trị bằng k.
* Ý tưởng: Sử dụng tính chất dãy A là dãy tăng, ta tìm cách thu hẹp nhanh phạm vi tìm kiếm sau mỗi lần so sánh khoá với số hạng được chọn. Để làm điều đó, ta chọn số hạng aGiua ở "giữa dãy" để so sánh với k, trong đó Giua = .
 Khi đó, chỉ xảy ra một trong ba trường hợp sau:
- Nếu aGiua = k thì Giua là chỉ số cần tìm. Việc tìm kiếm kết thúc.
- Nếu aGiua > k thì do dãy A là dãy đã được sắp xếp nên việc tìm kiếm tiếp theo chỉ xét trên dãy a1, a2,..., aGiua–1 (phạm vi tìm kiếm mới bằng khoảng một nửa phạm vi tìm kiếm trước đó). 
- Nếu aGiua < k thì thực hiện tìm kiếm trên dãy aGiua+1, aGiua+2,..., aN. 
Quá trình trên sẽ được lặp lại một số lần cho đến khi hoặc đã tìm thấy khoá k trong dãy A hoặc phạm vi tìm kiếm bằng rỗng.
* Thuật toán (Học sinh về nhà viế thuật toán)
 4. Củng cố:
 - Hiểu ý tưởng thuật toán
 - Trình bày thuật toán bằng 2 cách
 - Mô phỏng được hoạt động của thuật toán
 5. Bài về nhà: 
 - Làm lại bài tập ví dụ đã chữa, lấy thêm một số ví dụ khác tương tự.
 - Xem lại toàn bộ kiến thức đã học từ đầu năm đến giờ để giờ sau chữa bài tập và ôn tập ở tiết sau.
Rút kinh nghiệm: