bài 5) Từ bài toán đến chương trình
2) Quá trình giải bài toán trên máy tính
4)Một số ví dụ về thuật toán
1) Xác định bài toán
3) Thuật toán và mô tả thuật toán
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
xác định bài toán là phát biểu rõ các điều kiện cho trước và kết quả cần thu được
xác định bài toán là bước đầu tiên và là bước rất quan trọng trong việc giải bài toán
VD1: 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 nút giao thông trong giờ cao điểm và nấu một món ăn
c)Nấu một món ăn
b)bài toán vượt qua nghẽn giao thông
a) Để tính diện tích hình tam giác
kết quả: 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
Máy tính hoạt động dưới sự chỉ đạo của con người, để giải quyết 1 bài toán trên máy tình là đưa cho máy tính dãy hữu hạn các thao tác đơn giản mà nó có thể thực hiện để từ các điều kiện cho trước, ta được kết quả cần tìm.
đ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ả: một món ăn
các bước giải bài toán
B2: Mô tả thuật toán, liệt kê các thao tác cần thực hiện.
B3: Viết chương trình, dùng thuật toán vừa viết ra chuyển thành chương trình để máy tính có thể hiểu và thực hiện.
B1: Xác định bài toán, bao gồm xác định điều kiện cho trước và xác định kêt quả cần đạt được
Điều kiện: vị trí điểm nghẽn gaio thông và các con đường đi được để đến vị trí cần tới
Kết quả: đường đi không đi qua điểm tắt nghẽn
- Xét ví dụ: Pha trà mời khách
OUTPUT: Chén trà đã pha để mời khách
INPUT: Trà, nước sôi, ấm và chén.
- B2: Cho trà vào ấm
- B3: Rót nước sôi vào ấm và đợi khoảng 3 đến 4 phút.
- B1: Tráng ấm, chén bằng nước sôi
- B4: Rót trà ra chén để mời khách.
- Khái niệm mô tả thuật toán: là việc liệt kê các bước thực hiện công việc( như ví dụ pha trà). Các bước của thuật toán thực hiện tuần tự từ trên xuống dưới.
- Khái niệm thuật toán: là dãy các thao tác cần thực hiện theo 1 trình tự xác định để thu được kết quả cần thiết từ những điều kiện cho trước.
Ví dụ 1: một hình A được ghép từ hình chữ nhật với chiều rộng 2a, chiều dài b và 1 hình bán nguyệt bán kính a như hình 5.2
INPUT: các 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 HCN
OUTPUT: Diện tích của A
Thuật Toán:
B2: tính S hình bán nguyệt, S2 = πa2/2;
B3: tính S tổng, S = S1 + S2;
B1: tính S hình chữ nhật, S1 = 2a∗b;
Ví dụ 2: 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ị tổng 1 + 2 + … + 100.
Thuật toán:
- B1: SUM 0; I 0.
- B2: SUM SUM + I; I I + 1.
- B3: nếu I ≤ 100, thì quay lại bước 2. Ngược lại, thông báo giá trị SUM và kết thúc thuật toán.
Ví dụ 3: Đổi giá trị của 2 biến x và y.,
INPUT: Hai biến x, y có giá tri tương ứng là a và b
OUTPUT: Hai biến x, y có giá trị tương ứng là b và a
Thuật Toán:
- B2: x := y, khi đó x có giá trị là b
- B3: y := z, khi đó y có giá trị là a.
- B1: z := x, khi đó z có giá trị là a