Bài 5. Từ bài toán đến chương trình
Thời lượng: 4 tiết
1.Mục đích, yêu cầu
- Biết khái niệm bài toán, thuật toán;
- Biết các bước giải bài toán trên máy tính;
- Xác định được Input, Output của một bài toán đơn giản;
- Biết chương trình là thể hiện của thuật toán trên một ngôn ngữ cụ thể;
- Biết mô tả thuật toán bằng phương pháp liệt kê các bước;
- Hiểu thuật toán tính tổng của N số tự nhiên đầu tiên, tìm số lớn nhất của một dãy số.
2. Những điểm cần lưu ý và gợi ý dạy học
a) Bài toán và thuật toán để giải quyết bài toán là những nội dung rất quan trọng, nếu không nói là quan trọng nhất trong lập trình. Nếu HS nắm vững được những kiến thức này thì sẽ dễ dàng hơn rất nhiều trong việc tiếp thu kiến thức trong các bài sau. Vì lẽ đó các tác giả đề xuất dành thời lượng cho bài 5 là 4 tiết lí thuyết và 2 tiết bài tập. GV cần tận dụng hết thời gian dành cho bài này để truyền đạt cho HS một cách kĩ lưỡng.
b) Khái niệm bài toán và giải bài toán đã trở thành quen thuộc với HS trong các môn học khác như Toán, Vật lí,... Bài toán trong tin học không chỉ là những bài toán trong lĩnh vực toán học mà còn có thể là một nhiệm vụ, một công việc cần giải quyết trong cuộc sống thực tiễn (có khi không liên quan gì đến toán học) như: tính điểm trung bình một môn học, một học kì, nấu món ăn hay điều khiển rô-bốt nhặt rác chẳng hạn.
Để cho HS mở rộng nhận thức về khái niệm bài toán mà các em được biết ở môn học khác, có thể sử dụng lại ví dụ về bài toán điều khiển rô-bốt nhặt rác HS đã học ở bài 1. Ví dụ này cho thấy bài toán có thể còn là một công việc, một nhiệm vụ gắn liền với cuộc sống hằng ngày. Do đã được tiếp cận với ví dụ này ở bài học đầu tiên nên việc tìm ra điều kiện cho trước và kết quả thu được của bài toán này sẽ dễ dàng hơn với HS.
Để dẫn dắt đến khái niệm xác định bài toán, GV có thể dựa vào giả thiết và kết luận của một bài toán trong môn Toán để dẫn dắt HS xác định Input, Output của bài toán trong Tin học. Trong môn Toán, thường trước khi bắt đầu giải một bài toán các em đã quen với việc tìm giả thiết và kết luận của bài toán. Trong tin học, phần giả thiết là các điều kiện cho trước (Input), phần kết luận là kết quả cần thu được (Output).
Có thể sử dụng một bài toán đơn giản, quen thuộc với HS để HS dễ dàng tìm ra được điều kiện cho trước (giả thiết) và kết quả cần thu được (kết luận) của bài toán này (không nhất thiết cứ phải lấy ví dụ trong SGK).
c) Để máy tính có thể "giải" được bài toán thì con người cũng phải chỉ dẫn cho máy tính. Tuy nhiên, sự chỉ dẫn của con người để máy tính thực hiện phải rất cụ thể, chi tiết và đặc biệt là máy tính phải "hiểu" được những chỉ dẫn này. Có thể đặt câu hỏi với HS: Máy tính có "giải" được bài toán không? Có thể sử dụng ví dụ về rô-bốt nhặt rác để HS thảo luận tìm ra câu trả lời. Việc viết chương trình điều khiển máy tính rẽ phải, tiến, rẽ trái, nhặt rác,... là do con người nghĩ ra, máy tính chỉ thực hiện những thao tác theo chỉ dẫn của con người.
Như vậy, con người tìm ra cách thức, chỉ ra các thao tác và trình tự thực hiện các thao tác để giải quyết công việc, máy tính chỉ biết thực hiện các thao tác theo chỉ dẫn. Máy tính không tự giải được bài toán.
Tập hợp các bước để điều khiển rô-bốt nhặt rác chính là một thuật toán.
d) Có thể mô tả thuật toán bằng cách liệt kê các bước như giới thiệu trong SGK hoặc bằng sơ đồ khối. Tuy nhiên, GV không cần giới thiệu thêm về cách mô tả bằng sơ đồ khối.
HS đã biết máy tính chỉ có thể hiểu được ngôn ngữ máy. Ngôn ngữ lập trình là ngôn ngữ con người sử dụng để viết chương trình. Vì vậy, có thể gợi ý để HS suy luận dẫn đến phải mô tả thuật toán bằng ngôn ngữ lập trình, cụ thể: cách mô tả thuật toán với ngôn ngữ tự nhiên thì chỉ có con người mới hiểu, máy tính không hiểu được. Để máy tính có thể hiểu và có thể thực hiện được thuật toán thì cần mô tả thuật toán bằng ngôn ngữ lập trình. Việc mô tả thuật toán bằng một ngôn ngữ lập trình để máy tính có thể hiểu, thực hiện được chính là viết chương trình.
Để đi từ bài toán đến chương trình, SGK nêu ba bước: Xác định bài toán, mô tả thuật toán, viết chương trình. Đây là phương án chia bước đơn giản, HS dễ hiểu, dễ tiếp thu. Mặc dù có một số cách chia bước khác, tuy vậy để tránh làm phức tạp, GV không cần giới thiệu thêm hay phân tích sâu về các bước ở đây.
e) Nội dung mục 4 là quan trọng và tương đối khó với HS. Cần dành thời gian thích đáng cho mục này. Nên sử dụng tiết bài tập để bổ sung thêm thời lượng dạy học cho nội dung này. Mục tiêu của các ví dụ ở mục 4 là rèn luyện kĩ năng xác định Input, Output và mô tả thuật toán bằng cách liệt kê các bước cùng với việc giới thiệu thuật toán. Các thuật toán giới thiệu ở mục này là những thuật toán cơ bản HS cần tiếp thu. Trong đó, thuật toán tìm số lớn nhất của dãy số là thuật toán được yêu cầu cụ thể trong chuẩn kiến thức kĩ năng. Hơn nữa, các ví dụ trong mục này còn đề cập đến những thuật toán liên quan đến các cấu trúc rẽ nhánh, cấu trúc lặp và một số bài toán ở các bài sau.
Lưu ý rằng tất cả các thuật toán nêu trong mục này và trong phần câu hỏi và bài tập đều được sử dụng làm ví dụ minh hoạ hoặc để giải các câu hỏi và bài tập trong các bài sau. Do vậy việc rèn luyện kĩ với các ví dụ này và giải một số bài tập sẽ tạo điều kiện thuận lợi để HS tiếp thu các nội dung tiếp theo.
Để giúp HS hiểu rõ về thuật toán, GV có thể mô phỏng thuật toán với một bộ dữ liệu cụ thể. Ví dụ:
Mô phỏng thuật toán tính tổng N số tự nhiên đầu tiên, với N = 10 (trong SGK, N = 100).
| i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
i N
≤ |
Đúng |
Đúng |
Đúng |
Đúng |
Đúng |
Đúng |
Đúng |
Đúng |
Đúng |
Đúng |
Sai |
| SUM |
1 |
3 |
6 |
10 |
15 |
21 |
28 |
36 |
45 |
55 |
Kết thúc |
Mô phỏng thuật toán tìm số lớn nhất trong dãy số cho trước:
| Dãy số |
5 |
3 |
4 |
7 |
6 |
3 |
15 |
9 |
11 |
|
| i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| i > n |
Sai |
Sai |
Sai |
Sai |
Sai |
Sai |
Sai |
Sai |
Sai |
Đúng |
| ai > MAX |
|
Sai |
Sai |
Đúng |
Sai |
Sai |
Đúng |
Sai |
Sai |
Kết thúc |
| MAX |
5 |
5 |
5 |
7 |
7 |
7 |
15 |
15 |
15 |
3. Hướng dẫn trả lời câu hỏi và bài tập
Bài 1. Đáp án:
INPUT: Danh sách họ tên của HS trong lớp.
OUTPUT: Số HS có họ Trần.
INPUT: Dãy n số.
OUTPUT: Tổng của các phần tử lớn hơn 0.
INPUT: Dãy n số.
OUTPUT: Số các số có giá trị nhỏ nhất.
Bài 2. Sau ba bước, x có giá trị ban đầu của y và y có giá trị ban đầu của x, tức là giá trị của hai biến x và y được tráo đổi cho nhau.
Bài 3. Mô tả thuật toán:
INPUT: Ba số dương a > 0, b > 0 và c > 0.
OUTPUT: Thông báo "a, b và c có thể là độ dài ba cạnh của một tam giác" hoặc thông báo "a, b và c không thể là độ dài ba cạnh của một tam giác".
Bước 1. Nếu a + b ≤ c, chuyển tới bước 5.
Bước 2. Nếu b + c ≤ a, chuyển tới bước 5.
Bước 3. Nếu a + c ≤ b, chuyển tới bước 5.
Bước 4. Thông báo "a, b và c có thể là độ dài ba cạnh của một tam giác" và kết thúc thuật toán.
Bước 5. Thông báo "a, b và c không thể là độ dài ba cạnh của một tam giác" và kết thúc thuật toán.
Bài 4. Có thể giải bài toán này bằng cách sử dụng một biến phụ hoặc không dùng biến phụ.
Thuật toán 1. Sử dụng biến phụ z.
INPUT: Hai biến x và y.
OUTPUT: Hai biến x và y có giá trị không giảm.
Bước 1. Nếu x ≤ y, chuyển tới bước 5.
Bước 2. z ← x.
Bước 3. x ←y.
Bước 4. y← z.
Bước 5. Kết thúc thuật toán.
Thuật toán 2. Không sử dụng biến phụ (xem bài tập 2 ở trên).
INPUT: Hai biến x và y.
OUTPUT: Hai biến x và y có giá trị tăng dần.
Bước 1. Nếu x ≤ y, chuyển tới bước 5.
Bước 2. x x + y.
Bước 3. y x - y.
Bước 4. x x - y.
Bước 5. Kết thúc thuật toán.
Bài 5. Đây là thuật toán tính tổng của các số tự nhiên từ 1 đến 100. Để HS tập trung vào hiểu thuật toán hơn là dành thời gian cho việc tính toán đơn thuần, GV có thể thay cộng từ 1 đến 100 bằng cộng từ 1 đến 5 hoặc từ 1 đến 10.
Bài 6. Mô tả thuật toán:
INPUT: n và dãy n số a1, a2, ..., an.
OUTPUT: Tổng S = a1 + a2 + ... + an.
Bước 1. S ← 0; i ←1.
Bước 2. S ← S + ai; i ← i + 1.
Bước 3. Nếu i ≤ n, quay lại bước 2.
Bước 4. Thông báo giá trị S và kết thúc thuật toán.