Hãy tìm hiểu các thuật toán sau đây và cho biết khi thực hiện thuật toán, máy tính sẽ thực hiện bao nhiêu vòng lặp? Khi kết thúc, giá trị của S bằng bao nhiêu? Viết chương trình Pascal thể hiện các thuật toán đó.
- Thuật toán 1
Bước 1. S ← 10, x ← 0.5
Bước 2. Nếu S ≤ 5.2, chuyển tới bước 4.
Bước 3. S ← S - x và quay lại bước 2.
Bước 4. Thông báo S và kết thúc thuật toán.
- Thuật toán 2
Bước 1. S ←10, n ← 0.
Bước 2. Nếu S ≥ 10, chuyển tới bước 4.
Bước 3. n ← n+3, S ← S-n và quay lại bước 2.
Bước 4. Thông báo S và kết thúc thuật toán.
Lời giải chi tiết
- Thuật toán 1 :
- Máy tính sẽ thực hiện 10 vòng lặp , khi kết thúc thuật toán giá trị của S là S = 5.0
- Đoạn chương trình Pascal tương ứng:
- Thuật toán 2 :
- Máy tính sẽ không thực hiện vòng lặp nào do điều kiện không thỏa mãn, khi kết thúc thuật toán giá trị của S là S = 10.
Bạn đang xem tài liệu "Tin học 8 - Tiết 13, 14 - Bài 4: Bài toán và thuật toán [tiếp]", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
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]
- Mục tiêu
- 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.
- Kỹ năng
- Hiểu và nhận biết được Input và Output trong mỗi bài toán.
- 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
- Chuẩn bị của giáo viên: SGK, Giáo án, Tài liệu tham khảo.
- 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
- Ổn định tổ chức
- 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.
- 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.
- Một số ví dụ về 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
- 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 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]
- 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
- 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: Tài liệu đính kèm:
- Tuần 7.doc