Một số ví dụ về thuật toán lớp 8

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 đó.

1. 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.

2. 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

1. 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:

2. 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)

9. Mục tiêu
10. Kiến thức
11. 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
12. Học sinh chỉ ra được Input và Output của mỗi bài toán đưa ra.
13. Kỹ năng
14. Hiểu và nhận biết được Input và Output trong mỗi bài toán.
15. Thái độ
16. Chú ý nghe giảng, hăng hái phát biểu ý kiến.
17. 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
18. Chuẩn bị của giáo viên: SGK, Giáo án, Tài liệu tham khảo.
19. 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
20. Ổn định tổ chức
21. 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.
22. 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.
23. Một số ví dụ về thuật toán
24. Thuật toán kiểm tra tính nguyên tố của một số nguyên dương
25. Xác định bài toán:
26. Input: N là một số nguyên dương
27. Output: “N là số nguyên tố” hoặc “N không là số nguyên tố”
28. Ý tưởng:
29. Nếu N=1 thì N không là số nguyên tố
30. Nếu 1
31. 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:
32. Thuật toán
33. 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
34. Sơ đồ khối
35. 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)
36. Xác định bài toán
37. Input: Số nguyễn dương N, dãy a1, a2,., aN.
38. Output: Dãy a1, a2,., aN được sắp xếp thành dãy không giảm.
39. Ý 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.
40. Thuật toán
41. 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.
42. Thuật toán Tìm kiếm tuần tự:
43. Xác định bài toán
44. Input: Dãy gồm N số nguyên đôi một khác nhau a1, a2,..., aN và số nguyên k;
45. 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
46. Ý 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.
47. Thuật toán
48. 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.
49. Thuật toán Tìm kiếm nhị phân:
50. Xác định bài toán
51. 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;
52. 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.
53. Ý 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:
54. Nếu aGiua = k thì Giua là chỉ số cần tìm. Việc tìm kiếm kết thúc.
55. 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 đó).
56. 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.
57. Thuật toán (Học sinh về nhà viế thuật toán)
58. Củng cố:
59. Hiểu ý tưởng thuật toán
60. Trình bày thuật toán bằng 2 cách
61. Mô phỏng được hoạt động của thuật toán
62. Bài về nhà:
63. 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ự.
64. 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