Bài 5. Từ bài toán đến chương trình

BÀI 5. TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH

1. Bài toán và chương trình

- Bài toán là một công việc hay một nhiệm vụ cần phải giải quyết.

- Chẳng hạn, với bài toán ghi ra màn hình tổng của hai số a và b được gõ vào từ bàn phím, chương trình có thể gồm các lệnh như hình sau đây:

Tính tổng;

Bắt đầu;      

     Nhập số a;      

     Nhập số b;      

     Tính tổng a + b;      

     Ghi kết quả a + b ra màn hình;

Kết thúc;

2. Bài toán và cách xác định bài toán

- Để phát biểu một bài toán cụ thể, người ta cần xác định rõ các điều kiện cho trước và kết quả cần thu được.

a. Ví dụ 1: Tính diện tích hình tam giác:

• Điều kiện cho trước: Một cạnh và chiều cao tương ứng với cạnh đó;
• Kết quả cần thu được: Diện tích hình tam giác.

b. Ví dụ 2: Xét bài toán nấu một món ăn

• Điều kiện cho trước: Các thực phẩm hiện có (trứng, mỡ, mắm, muối, rau.)
• Kết quả cần thu được: Một món ăn.

3. Quá trình giải bài toán trên máy tính

- Các bước để nhờ máy giải một bài toán:

• Bước 1: Xác định bài toán là xác định (thông tin vào – INPUT) và kết quả cần xác định (thông tin ra – OUTPUT).
• Bước 2: Thiết lập phương án giải quyết (xây dựng thuật toán) là tìm, lựa chọn thuật toán và mô tả nó bằng ngôn ngữ thông thường.
• Bước 3: Viết chương trình (lập trình) là diễn đạt thuật toán bằng một ngôn ngữ lập trình sao cho máy tính có thể hiểu và thực hiện.​

4. Thuật toán và mô tả thuật toán

- Mô tả thuật toán là liệt kê các bước cần thiết để giải một bài toán.

- Ví dụ 1: Hãy xác định yêu cầu và mô tả việc nấu cơm dưới dạng thuật toán
Giải

• INPUT: Gạo, nước, nồi cơm điện.
• OUTPUT: Bát cơm ngon.
• Mô tả thuật toán:
  • Bước 1. Vo gạo bằng nước.
  • Bước 2. Cho gạo vào nồi.
  • Bước 3. Cho nước ngập gạo.
  • Bước 4. Cắm điện.
  • Bước 5. Bát cơm ngon.

- Ví dụ 2: Bài toán "Chuẩn bị món trứng tráng"

• INPUT: Trứng, dầu ăn, muối và hành.
• OUTPUT: Trứng tráng.
• Thuật toán:
  • Bước 1. Đập trứng, tách vỏ và cho trứng vào bát.
  • Bước 2. Cho ít muối và hành lá thái nhỏ. Dùng đũa khuấy mạnh cho đến khi đều.
  • Bước 3. Cho một thìa dầu ăn vào chảo, đun nóng đều rồi đổ trứng vào, đun trong khoảng 1 phút.
  • Bước 4. Lật mặt trên của miếng trứng úp xuống dưới, đun tiếp trong khoảng 1 phút.
  • Bước 5. Lấy trứng ra đĩa.

=> Thuật toán là dãy các thao tác cần thực hiện theo một trình tự xác định để thu được kết quả cần tìm từ những điều kiện cho trước.

5. Một số ví dụ về thuật toán

a. Ví dụ 1: Tính tổng của 100 số tự nhiên đầu tiên

1. Xác định bài toán:

• INPUT: Dãy 100 số tự nhiên đầu tiên (từ 1 đến 100).
• OUTPUT: Giá trị SUM = 1 + 2 + ...+ 100.

2. Mô tả thuật toán:

• Bước 1: Gán SUM \(\leftarrow\) 0; i \(\leftarrow\) 1.
• Bước 2: Gán i \(\leftarrow\) i + 1.
• Bước 3: Nếu i ≤ 100, thì SUM \(\leftarrow\) SUM + i và chuyển lên bước 2. Trong trường hợp ngược lại (i > 100), kết thúc thuật toán.

b. Ví dụ 2: Tìm số lớn nhất trong dãy A các số a₁, a₂, ..., a_n cho trước.

- Xác định bài toán:

• INPUT: Dãy A các số a₁, a₂, ..., a_n (n \(\ge\) 1).
• OUTPUT: Giá trị S_MAX = max {a₁, a₂, ..., a_n}.

- Mô tả thuật toán:

• Bước 1: Nhập số n và dãy A; gán S_MAX \(\leftarrow\) a₁; i \(\leftarrow\) 0;
• Bước 2: i \(\leftarrow\) i + 1;
• Bước 3: Nếu i > n, kết thúc thuật toán (khi đó S_MAX là giá trị phần tử lớn nhất của dãy A). Trong trường hợp ngược lại (i ≠ n), thực hiện bước 4.
• Bước 4: Nếu a_i > S_MAX, thay đổi giá trị S_MAX: S_MAX \(\leftarrow\) a_i rồi chuyển về bước 2. Trong trường hợp ngược lại (S_MAX \(\ge\) a_i), giữ nguyên S_MAX và chuyển về bước 2.​