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
-Bài toán là một công việc hay một nhiệm vụ cần giải quyết.
Bài toán và xác định bài toán
-Để xác định một bài toán
+ Các điều kiện cho trước.
+ Kết quả cần thu được.
Xét bài toán tính diện tích hình tam giác.
Bài toán và xác định bài toán
Giải
? Để tính diện tích hình tam giác:
-Điều kiện cho trước: Một cạnh và đường cao tương ứng với cạnh đó.
-Kết quả cần thu được: Diện tích hình tam giác.
Ví dụ 1:
Xét bài toán nấu một món ăn.
Bài toán và xác định bài toán
Giải
? Để 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.
Ví dụ 2:
Xét bài toán tính tổng hai số a và b.
Bài toán và xác định bài toán
Giải
? Để tính tổng hai số a và b:
-Điều kiện cho trước: Hai số a và b.
-Kết quả cần thu được: Tổng a + b.
Ví dụ 3:
- Dãy hữu hạn các thao tác cần thực hiện để giải một bài toán được gọi là thuật toán.
2. Quá trình giải bài toán trên máy tính
- Các bước giải bài toán trên máy tính:

Xác định bài toán: xác định thông tin đã cho (INPUT) và thông tin cần tìm (OUTPUT).

Mô tả thuật toán: Tìm cách giải bài toán và diễn tả bằng các lệnh cần phải thực hiện.

Viết chương trình: Dựa vào mô tả thuật toán ở trên, ta viết chương trình bằng một ngôn ngữ lập trình mà ta biết.
2. Quá trình giải bài toán trên máy tính
Ví dụ 1: Hãy 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.
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.
3. Thuật toán và mô tả thuật toán
Giải
?Việc làm món trứng tráng có thể mô tả dưới dạng thuật toán như sau:
INPUT: Trứng, dầu ăn, muối và hành.
OUTPUT: Trứng tráng.
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.
3. Thuật toán và mô tả thuật toán
Ví dụ 2: Hãy mô tả việc làm món trứng tráng dưới dạng thuật toán
Ví dụ 1: Tính tổng của 100 số tự nhiên đầu tiên.
4. Một số ví dụ về thuật toán
Giải
? Xác định bài toán:

INPUT: Dãy 100 số tự nhiên đầu tiên.

OUTPUT: SUM = 1+2+.100.
Nhận xét:
S = 0
S1 = S + 1
S2 = S1 + 2
S3 = S2 + 3


.....
S100 = S99 + 100
* Baứi toaựn thửùc hieọn theo quy luaọt:
Ssau = S trửụực + i
. . . . . . . . . . . . . . . . . . . .
4. Một số ví dụ về thuật toán
Ví dụ 1: Tính tổng của 100 số tự nhiên đầu tiên.
4. Một số ví dụ về thuật toán
? Thuật toán
Cách 1:
Bước 1. SUM ? 0.
Bước 2. SUM ? SUM+1.
.
Bước 101. SUM ? SUM+100.
Cách 2:
Bước 1. SUM ? 0; i ?0.
Bước 2. i ? i+1.
Bước 3. Nếu i<=100 thì SUM ? SUM+i và quay lại bước 2.
Bước 4. Thông báo kết quả và kết thúc.
Ví dụ 2. Đổi giá trị của hai biến x và y.
4. Một số ví dụ về thuật toán
Giải
? Xác định bài toán:
INPUT: Hai biến x và y, có giá trị tương ứng là a và b.
OUTPUT: Hai biến x và y, có giá trị tương ứng là b và a.
? Thuật toán:

Bước 1. z ? x
Bước 2. x ? y
Bước 3. y ? z.
4. Một số ví dụ về thuật toán
Ví dụ 2: Đổi giá trị của hai biến x và y.
Ví dụ 3: Tìm số lớn nhất trong dãy A các số a1,a2. an cho trước.
4. Một số ví dụ về thuật toán
Giải
? Xác định bài toán:

INPUT: Dãy A các số a1, a2 . an (n>=1).

OUTPUT: SUM = Giá trị max = max{a1, a2. an}.
4. Một số ví dụ về thuật toán
Quả này lớn nhất
Quả này lớn nhất
Quả này lớn nhất
Tìm ra quả lớn nhất rồi!
Thuật toán:

Bước 1. MAX ? a1; i ? 1
Bước 2. i ? i+1
Bước 3. Nếu i>n, chuyển đến bước 5.
Bước 4. Nếu ai>MAX, MAX ? ai. Quay lại bước 2.
Bước 5. Kết thúc thuật toán.
4. Một số ví dụ về thuật toán
Ví dụ 3: Tìm số lớn nhất trong dãy A các số a1,a2. an cho trước.
? Nhắc lại khái niệm bài toán, thuật toán.

? Nêu các bước giải bài toán trên máy tính.

? Xác định INPUT, OUTPUT của một bài toán.
5. Củng cố
? BÀI TẬP VỀ NHÀ
Xem lại 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.
Làm tất cả các bài tập SGK trang 45.
Xem trước bài mới.