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

Nhiệt liệt chào mừng
các thầy cô tới dự tiết Tin học 6
Người dạy: Nguyễn Thế Đạt
Giáo viên: THCS Hạp Lĩnh – TP Bắc Ninh
Kiểm tra bài cũ:
Bài 5
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
Giáo án điện tử tin học lớp 8
Tiết 19+20+21+22 :
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
tIếT 19 + 20 + 21+22 :
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:
Mô tả thuật toán: Nêu trình tự các bước để giải một bài toán.
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).
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.
Ví dụ 2. Một hình A được ghép từ một hình chữ nhật với chiều rộng 2a, chiều dài b và một hình bán nguyệt bán kính a như hình dưới đây:
4. Một số ví dụ về thuật toán
INPUT: Số a là chiều rộng của hình chữ nhật và là bán kính của hình bán nguyệt, b là chiều dài của hình chữ nhật.
OUTPUT: Diện tích của hình A.


Thuật toán đơn giaỷn để tính diện tích hỡnh A có thể gồm các bước sau:
Bước 1. (S1 ? 2ab) {(Tính diện tích hỡnh chửừ nhật)};
Bước 2. (S2 ? ) {(Tính diện tích hình bán nguyệt)};
Bước 3. (S ? S1 + S2) và kết thúc.



Lưu ý: Trong biểu diễn thuật toán, người ta cũng thường sử dụng kí hiệu ? để chỉ phép gán một biểu thức cho một biến.
Ví dụ 3. Tính tổng của 100 số tự nhiên đầu tiên.
INPUT: Dãy 100 số tự nhiên đầu tiên: 1, 2, ... 100.
OUTPUT: Giá trị của tổng 1 + 2 + ...+ 100.
Bước 1. SUM ? 0.
Bước 2. SUM ? SUM + 1.
...
Bước 101. SUM ? SUM + 100.
Thuật toán đơn giản để tính diện tích hình A có thể gồm các bước sau
Tuy nhiên, việc mô tả thuật toán như trên là quá dài dòng (nhất là khi không chỉ tính tổng của 100 số mà số các số cần tính tổng lớn hơn nhiều).
Thuật toán tìm SUM có thể được mô tả ngắn gọn hơn như sau:
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 thuật toán.
Ví dụ 4. Đổi giá trị của hai biến x và y.
INPUT: Hai biến x, y có giá trị tương ứng là a và b.
OUTPUT: Hai biến x, y có giá trị tương ứng là b và a.
Ta có thuật toán sau:
Bước 1. z ? x {Sau bước này giá trị của z sẽ bằng a}
Bước 2. x ? y {Sau bước này giá trị của x sẽ bằng b}
Bước 3. y ? z {Sau bước này giá trị của y sẽ bằng giá trị của z, chính là a, giá trị ban đầu của biến x}
Ví dụ 5. Cho hai số thực a và b. Hãy cho biết kết quả so sánh hai số đó dưới dạng "a lớn hơn b", "a nhỏ hơn b" hoặc "a bằng b".
Thuật toán như sau:
Bước 1. Nếu a > b, kết quả là "a lớn hơn b" và chuyển đến bước 3.
Bước 2. Nếu a < b, kết quả là "a nhỏ hơn b"; ngược lại, kết quả là "a bằng b".
Bước 3. Kết thúc thuật toán.
Ví dụ 6. Tìm số lớn nhất trong dãy A các số a1, a2, ..., an cho trước.
Ta có thuật toán sau:
INPUT: Dãy A các số a1, a2, ..., an (n ? 1).
OUTPUT: Giá trị MAX = max{a1, a2, ..., an}.
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. Trong trường hợp ngược lại (MAX ? ai), giữ nguyên MAX . Quay lại bước�2.
Bước 5. Kết thúc thuật toán.