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

Bài 5
Mục tiêu
Kiến thức:
- Khái niệm bài toán, thuật toán.
- Các bước giải bài toán trên máy tính
- Mô tả thuật toán bằng phương pháp liệt kê
Kĩ năng:
- Biết khái niệm bài toán, thuật toán.
- Xác định được Input, Output của một bài toán đơn giản.
- Biết các bước giải bài toán trên máy tính
- 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ê

M?t b�i toán trong toán học, vật lí,.. hay một nhiệm vụ, một công việc cần giảI quyết trong cuộc sống gọi là một bàI toán trong tin học
Ví dụ 1: Tính tổng các số tự nhiên từ 1 đến 100
Ví dụ 2: Tính quãng đường ô tô đi được trong 3 giờ với vận tốc 60km/h.
Ví dụ 3:Lập bảng điểm của các bạn trong lớp, nấu món ăn hay điều khiển rô bốt nhặt rác.
Đặt vấn đề
1.Bài toán và xác định bài toán
Ví dụ 1: Xét các bài toán tính diện tích hình tam giác, tìm đường đi tránh các điểm tắc nghẽn giao thông trong giờ cao điểm hay nấu một món ăn
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 phải giải quyết
Để giải quyết bài toán cần xác định bài toán, tức là xác định rõ các điều kiện cho trước và kết quả thu được.
Trong môn toán, trước khi giải bài toán các em cần phải xác định giả thiết và kết luận.
Trong tin học, trước khi bắt đầu giải quyết bài toán cũng cần phải xác định điêu kiện cho trước (giả thiết) và kết quả cần thu được (kết luận).
a. Để tính diện tích của một 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
b. Tìm đường đi tránh các điểm nghẽn giao thông
- Điều kiện cho trước:
Vị trí điểm nghẽn và các con đường có thể đi từ vị trí hiện tại tới vị trí cần tới
- Kết quả cần thu được:
Đường đi từ vị trí hiện tại đến vị trí cần tới không qua điểm nghẽn
c. 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ỡ, rau..)
- Kết quả cần thu được:
Một món ăn
Từ điều kiện cho trước làm thế nào để tìm ra kết quả cần thu được ?
Các em cần tìm ra cách giải của bài toán.
2. Quá trình giải bài toán trên máy tính
Thuật toán là 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
Làm thế nào để máy tính hiểu và trực tiếp thực hiện được thuật toán?
? Cần diễn tả thuật toán bằng một ngôn ngữ mà máy tính hiểu và thực hiện được. Ngôn ngữ đó gọi là ngôn ngữ lập trình.
Quá trình giải bài toán trên máy tính gồm các bước sau:
Xác định bài toán: là xác định thông tin đã cho (INPUT) và thông tin cần tìm (OUTPUT).
Mô tả thuật toán: Nêu trình tự các bước để giải một bài toán.
Viết chương trình: Diễn tả thuật toán bằng một ngôn ngữ lập trình để máy có thể hiểu và thực hiện được
3. Thuật toán và mô tả thuật toán
Ví dụ 1: Pha trà mời khách
INPUT: Trà, nước sôi, ấm và chén
OUTPUT: Chén trà đã pha để mời khách
Bước1. Tráng ấm, chén bằng nước sôi
Bước2. Cho trà vào ấm
Bước3. Rót nước sôi vào ấm và đợi khoảng 3 đến 4 phút
Bước4. Rót trà ra chén để mời khách
Việc liệt kê các bước như trên là một cách để mô tả thuật toán, các bước được thực hiện tuần tự theo trình tự đã được chỉ ra.
Ví dụ 2: Giải phương trình bậc nh?t ax + b = 0.
B1: Xác định hệ số a, b;
B2: Nếu a=0 và b=0 => Phương trình vô số nghiệm =>B5;
B3: Nếu a=0 và b?0 => Phương trình vô nghiệm =>B5;
B4: Nếu a?0 => Phương trình có nghiệm x=-b/a =>B5;
B5: Kết thúc.
?Input: Các hệ số a, b.
? Output: Nghiệm của phương trình.

Rõ ràng, theo đúng trình tự các bước trong các thuật toán nêu trên ta có thể pha được chén trà hay tính nghiệm của phương trình đã cho.
Hãy cho biết các bước sau có phải là mô tả một thuật toán không
Bước1. Viết số 2 lên bảng
Bước2. Xóa bảng
Bước3. quay lại bước 1
Câu trả lời là Không.
Lưu ý: số bước thực hiện của một thuật toán phải hữu hạn
Lưu ý: Thuật toán phải được mô tả đủ cụ thể để bất kỳ đối tượng nào, với cùng khả năng và điều kiện như nhau thì khi thực hiện thuật toán đều thu được cùng một kết quả
Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận được Output cần tìm.
Ví dụ 3: Viết thuật toán làm món trứng tráng
INPUT: Trứng, dầu ăn, muối, hành
OUTPUT: Trứng tráng
Học sinh làm việc theo nhóm.
1. Khái niệm bài toán
Từ Bài toán đến chương trình
2. Khái niệm thuật toán
3. Quá trình giải bài toán trên máy tính
4. Mô tả thuật toán bằng phương pháp liệt kê