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
a) biết 2x – 6 = 0
b) của các số tự nhiên từ 1 đến 100.
c) điểm, cửu chương…
d) Rôbốt
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
Tìm x
Tính tổng
Lập bảng
lập bảng
nhặt rác
Bài toán
1. Bài toán và xác định bài toán

Bài toán: Tính diện tích hình chữ
nhật có chiều dài a, chiều rộng b.
Điều kiện cho trước: chiều dài a, chiều rộng b

Kết quả thu được: diện tích hình chữ nhật

Bài toán: Rôbốt nhặt rác bỏ vào thùng rác
Thông tin vào (Input):
Thông tin ra (Output):

Để giải bài toán này trước tiên em cần phải xác định cái gì?
(thông tin vào-Input)
(thông tin ra-Output)
rác bỏ vào thùng rác
Rôbốt, rác, thùng rác
Xác định bài toán:
+ Xác định rõ các điều kiện cho trước
( thông tin vào – Input)
+ Xác định kết quả cần thu được
( thông tin ra – Output)
Trước khi giải một bài toán em cần phải xác định được bài toán.
a
b
Cách thức xác định bài toán
1. Bài toán và xác định bài toán
VD1: Tớnh di?m trung bỡnh c?a 3 mụn Toỏn, Lý, Tin
- Thông tin vào (Input):
Điểm của 3 môn Toán, Lý, Tin
- Thông tin ra (Output):
Điểm trung bình c?a 3 môn Toỏn, Lý, Tin
VD2: Bài toán "Gi?c ỏo qu?n"
- Thông tin vào (Input):
Áo quần bẩn, vật dụng hiện có (xà phòng, nước,…)
- Thụng tin ra (Output):
Áo quần sạch
1. Bài toán và xác định bài toán
Từ điều kiện cho trước(Input) làm thế nào để tìm ra kết quả cần thu được(Output) ?
Tìm ra cách giải
* Để Rôbốt nhặt rác bỏ vào thùng rác ta có các bước giải:
Rẽ phải 2 bước
Tiến tới 1 bước
Nhặt rác
Rẽ phải 2 bước
Bỏ rác vào thùng
?
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
Máy tính có thể tự động trực tiếp thực hiện được không ?
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 cú th? hi?u v� th?c hi?n du?c. Ngụn ng? dú g?i l� ngụn ng? l?p trỡnh.
Thuật toán
2. Quá trình giải bài toán trên máy tính
Để giải một bài toán hoàn chỉnh trên máy tính em cần thực hiện các bước nào ?
?
Quá trình giải bài toán trên máy tính: 3 bước

- Xác định bài toán: xác định Input, Output

- Mô tả thuật toán : trình tự các bước giải

- Viết chương trình: bằng ngôn ngữ lập trình
2. Quá trình giải bài toán trên máy tính
Ví dụ
Tính tổng của N số tự nhiên đầu tiên:
S= 1+2+ … + n

Thông tin vào (Input):
Thông tin ra (Output):
1,2,..,n
Tổng của 1 + 2 +…+ n
3. Thuật toán và mô tả thuật toán
- Mô tả thực toán là liệt kê các bước cần thiết để giải một một bài toán
Bài toán: “Việc 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ước 1: Tráng ấm, chén bằng nước sôi.
Bước 2: Cho trà vào ấm.
Bước 3: Rót nước sôi vào ấm và đợi khoảng 3 đến 4 phút.
Bước 4: Rót trà ra chén để mời khách.
Bài toán: “Giải phương trình bậc nhất dạng tổng quát bx + c =0”
INPUT: Các số b và c.
OUTPUT: Nghiệm của phương trình bậc nhất.
Bước 1: Nếu b=0 chuyển tới bước 3.
Bước 2: Tính nghiệm của phương trình x= - và chuyển tới bước 4
Bước 3: Nếu c  0, thông báo phương trình đã cho vô nghiệm. Ngược lại (c=0), thông báo phương trình có vô số nghiệm.
Bước 4: Kết thúc.

3. Thuật toán và mô tả thuật toán
3. Thuật toán và mô tả thuật toán
Bài toán: “Làm món trứng tráng”
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 một chút muối và hành tươi thái nhỏ vào bát trứng. 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 tiếp trong khoảng một 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.
?
Vậy thuật toán là gì?
Thuật toán là dãy hữu hạn 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 thiết từ những điềukiện cho trước

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 như hình 29 dưới đây:
? Xác định được bài toán và mô tả thuật toán.
+ INPUT: Số a là ½ chiều rộng HCN và là bán kính của hình bán nguyệt, b là chiều dài HCN
+ OUTPUT: Diện tích hình A.
S1=2ab
S=S1+S2
4. Một số ví dụ về thuật toá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ị tổng 1+2+....+100.
4. Một số ví dụ về thuật toán
Bước 1: S  0.
Bước 2: S  S + 1.
...
Bước 101: S  S + 100.
Để mô tả được thuật toán trên ta dùng biến S để lưu giá trị của tổng và thực hiện phép toán : cộng thêm vào biến tổng S lần lược các giá trị 1,2,3,..,100 tức là thao tác “cộng” được lặp đi lặp lại 100 lần . Mặc khác việc cộng thêm số i vào S khi biến i không vượt quá 100.
Vì vậy thuật toán tìm tổng S được mô tả như sau.
Bước 1. S← 0; i← 0
Bước 2. i← i+1;
Bước 3. Nếu i <=100 thì S←S + i và quay lại bước2
Bước 4. Đưa kết quả ra màn hình và kết thúc thuật toán.
4. Một số ví dụ về thuật toán
1
2
3
4
5
6
7
8
4. Một số ví dụ về thuật toán
Để hiểu rõ hơn về thuật toán này, ta có thể minh hoạ bằng bộ dữ liệu cụ thể sau:
Tính tổng N số tự nhiên, với N=5
1
1
Đ
1
2
2
Đ
3
3
3
Đ
6
4
4
Đ
10
5
5
Đ
15
6
Sai
Kết thúc
4. Một số ví dụ về thuật toán
Bài 2 trang 36: Cho chương trình:
Program hoan_doi;
Var x,y,z: integer;
begin
read(x,y);
Writeln(x ,’ ’,y);
z:=x;
x:=y;
y:=z;
Writeln(x ,’ ’,y);
readln
end.
Em hãy cho biết ý nghĩa câu lệnh và cho biết kết quả ra màn hình?
{gán giá trị đã lưu trong biến nhớ x vào biến nhớ z}
{gán giá trị đã lưu trong biến nhớ y vào biến nhớ x}
{gán giá trị đã lưu trong biến nhớ z vào biến nhớ y}
4. Một số ví dụ về thuật toán
Bài toán được xác định
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:
Bước 1. z ← x { giá trị của z sẽ bằng a}
Bước 2 x ←y { giá trị của x sẽ bằng b}
Bước 3 y ←z { giá trị của y sẽ bằng a}
Ví dụ 4: Đổi giá trị của 2 biến x và y.
4. Một số ví dụ về thuật toán
4. Một số ví dụ về thuật toán
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 lớn hơn b”, “a bằng b”.
INPUT: Hai số thực a và b
OUTPUT: Kết quả so sánh.
Mô hình 2:

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” và kết thúc thuật toán.
Bước 3: Kết thúc thuật toán.
Mô hình 1:

Bước 1: Nếu a> b, kết quả là “a lớn hơn b”.
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” và kết thúc thuật toán.
So sánh hai mô hình trên
Ví dụ: Tìm giá trị lớn nhất của 3 số a,b,c
Em tự bài toán xác định và mô thuật toán cho bài toán
-Input: vào 3 số a,b,c.
-Output: Max của 3 số a,b,c
Hdẫn: Ta gán số a cho biến Max sau đó so sánh lần lượt số b và c với Max. Nếu b> Max thì gán b cho max, còn nếu c> Max thì gán c cho max.
Bài toán xác định
4. Một số ví dụ về thuật toán
Ví dụ 6: Tìm số lớn nhất trong dãy A gồm các số a1,a2, ..., an cho trước
Input: dãy A các số a1,a2,...,an (n>=0)
Output: Giá trị Max= Max {a1,a2,...,an }
Ta có thể thực hiện như sau:
+ Đầu tiên gán giá trị a1 cho biến Max .
+Sau đó lần lượt so sánh các số a2,...an của dãy A với Max. Nếu a i > Max thì ta gán a i cho Max.
Do vậy ta có thuật toán như sau:
4. Một số ví dụ về thuật toán
Bước 1. Max← a1; i ← 1.
Bước 2. i← i +1
Bước 3. Nếu i >n thì chuyển đến bước 5.
Bước 4. Nếu a i > Max thì Max ← ai và 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
* Mô tả thuật toán tìm số lớn nhất trong dãy số với n=8,tương ứng với dãy: 5,3,4,7,6,3,15,9
Sai
Sai
Sai
Sai
Sai
Sai
Sai
Sai
Đúng
Sai
Sai
Đúng
Sai
Sai
Đúng
Sai
Kết thúc
5
5
5
7
7
7
15
15
1
2
3
4
5
6
7
8
9
GHI NH?
Xác định bài toán là việc xác định các điều kiện ban đầu (thông tin vào - INPUT) và các kết quả cần thu được (thông tin ra - OUTPUT).
Giải bài toán trên máy tính nghĩa là đưa cho máy tính dãy hữu hạn các thao tác đơn giản (thuật toán) mà nó có thể thực hiện được để cho ta kết quả.
Quá trình giải một bài toán trên máy tính gồm các bước: xác định bài toán; xây dựng thuật toán; lập chương trình.
Thuật toán là dãy hữu hạn 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 thu được từ những điều kiện cho trước.