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

TỪ BÀI TOÁN DẾN CHƯƠNG TRÌNH
B�i 5:
Tin học 8
1. Bài toán và xác định bài 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.
Để giải quyết một bài toán cụ thể, 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ả cần thu được.

Ví dụ 1: Tính tổng của hai số a, b nhập từ bàn phím
- Điều kiện cho trước: hai số a, b
- Kết quả cần thu được: tổng của a và b.
Ví dụ 2: Nấu một món ăn
- Điều kiện cho trước: các thực phẩm hiện có.
- Kết quả cần thu được: một món ăn
Ví dụ 3: Lập bảng điểm để quản lý kết quả học tập của học sinh trong lớp.
- Điều kiện cho trước: thông tin của học sinh
- Kết quả cần thu được: kết quả học tập của học sinh.

Máy tính có thể tự giải các bài toán không?
ồ không! Tôi chỉ làm theo sự chỉ dẫn thôi!!!!
Máy tính không thể tự mình tìm ra lời giải của các bài toán. Lời giải của một bài toán cụ thể, tức thuật toán, là tư duy sáng tạo của con người.
Hãy nhớ!
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 theo một trình tự nhất định để thu được kết quả cần thiết từ những điều kiện cho trước.
- 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áy tính thực hiện và cho kết quả.
- Chương trình chỉ là thể hiện của thuật toán trong một ngôn ngữ lập trình cụ thể.
- Quá trình giải bài toán trên máy tính gồm 3 bước:
+ 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: diễn tả cách giải bài toán bằng dãy các thao tác 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, viết chương trình bằng một ngôn ngữ lập trình thích hợp.
3. Thuật toán và mô tả thuật toán:
Khái niệm: Mô tả thuật toán là liệt kê các bước cần thiết để giải một bài toán.
b) Các ví dụ:
Các bước thực hiện để pha trà mời khách ntn ?
Thuật toán 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 một ít trà vào ấm.
Bước 3: Tráng trà
Bước 4: Rót nước sôi vào ấm và đợi 3 – 4 phút
Bước 5: Rót trà ra chén để mời khách.
VD1
Thuật toán “Làm món trứng tráng”

Input: Trứng, dầu ăn, muối, hành
Output: Món trứng tráng
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 quấ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 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.
Bước 1. Đập trứng, tách vỏ và
cho trứng vào bát.
Bài 1: Hãy chỉ ra INPUT và OUTPUT của các bài toán sau:
a) Xác định số học sinh trong lớp cùng mang học Trần.
b) Tính tổng của các phần tử lớn hơn 0 trong dãy n số cho trước.
c) Tìm số các số có giá trị nhỏ nhất trong n số đã cho.
Kiểm tra:
1) Thế nào là mô tả thuật toán?
2) Sắp xếp lại cho đúng thứ tự công việc em thực hiện mỗi sáng các ngày trong tuần.
a) Chào bố mẹ;
b) Đánh răng rửa mặt;
c) Thức dậy;
d) A�n sáng;
e) Đi đến trường.
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:


b
a
a
+ Input: soá a laø nöûa chieàu roäng cuûa hình chöõ nhaät vaø laø baùn kính cuûa hình baùn nguyeät, b laø chieàu daøi hình chöõ nhaät.
+ Output: dieän tích cuûa hình A
+ Thuaät toaùn:
Böôùc 1:S1 2ab;

Böôùc 2: S2 ;

Böôùc 3: S S1 + S2 vaø keát thuùc.

+ Input: soá a laø nöûa chieàu roäng cuûa hình chöõ nhaät vaø laø baùn kính cuûa hình baùn nguyeät, b laø chieàu daøi hình chöõ nhaät.
+ Output: dieän tích cuûa hình A
+ Thuaät toaùn:
Böôùc 1:

Böôùc 2: S2 ;

Böôùc 3: S S1 + S2 vaø keát thuùc.

S = 0
S1 = S + 1
S2 = S1 + 2
S3 = S2 + 3


.....
S100 = S99 + 100
. . . . . . . . . . . .
Ví dụ 3: Tính tổng của 100 số tự nhiên đầu tiên.
+ Input: daõy 100 soá töï nhieân ñaàu tieân: 1, 2, …, 100
+ Output: giaù trò cuûa toång 1 + 2 + … + 100
+ Thuaät toaùn:
Böôùc 1: SUM 0; i 0;
Böôùc 2: i i + 1.
Böôùc 3: neáu i 100, thì SUM SUM + i vaø quay laïi böôùc 2
Böôùc 4: Thoâng baùo keát quaû vaø keát thuùc thuaät toaùn.
+ Input: daõy 100 soá töï nhieân ñaàu tieân: 1, 2, …, 100
+ Output: giaù trò cuûa toång 1 + 2 + … + 100
+ Thuaät toaùn:
Böôùc 1: SUM 0; i 0;
Böôùc 2: i i + 1.
Böôùc 3: neáu i 100, thì SUM SUM + i vaø quay laïi böôùc 2
Böôùc 4: Thoâng baùo keát quaû vaø keát thuùc thuaät toaùn.
Ví dụ với N = 5:


1
1
Đ
1
2
2
3
Đ
3
3
Đ
6
4
4
Đ
10
5
5
Đ
15
6
6
S
Kết thúc
Cốc A chứa nước màu đỏ, cốc B chứa nước màu xanh. Làm cách nào để tráo đổi cốc A có nước màu xanh, cốc B có nước màu đỏ? (Giả thiết cốc A và B có thể tích như nhau)
Cốc A
Cốc B
Làm cách nào đây?
Cốc A
Cốc B
Cốc C
1. Lấy một cốc C rỗng có thể tích như A và B.
2. Đổ nước màu đỏ ở cốc A vào cốc C
3. Đổ nước màu xanh ở cốc B sang cốc A
4. Đổ nước màu đỏ ở cốc C vào cốc B
Cốc A
Cốc B
Cốc C
Ví dụ 4: Đổi giá trị của hai biến x, y

+ Input: hai bieán x, y coù giaù tri töông öùng laø a vaø b
+ Output: hai bieán x, y coù giaù trò töông öùng laø b vaø a
+ Thuaät toaùn:
Böôùc 1: z x {z = a};
Böôùc 2: x y { x = b};
Böôùc 3: y z {y = a}
Ví dụ 5: Cho hai số thực a, 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”
+ Input: hai số thực a và b
+ Output: kết quả so sánh
+ Thuật toán:
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ố
Quả này lớn nhất
Quả này mới lớn nhất
ồ! Quả này lớn hơn
Tìm ra quả lớn nhất rồi!
Cùng tìm thuật toán
+ Input: dãy A các số (n 1)
+ Output: Giá trị MAX = max
+ Thuật toán:
Bước 1: MAX ;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 .Quay lại bước 2
Bước 5: 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ố
Tin học 8
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-ra 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à hướng dẫn 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 thiết từ những điều kiện cho trước.
Bài 2: Giả sử x và y là các biến số. Hãy cho biết kết quả của việc thực hiện thuật toán sau:
Bước 1: x x + y
Bước 2: y x – y
Bước 3: x x – y
Bài 3: Cho trước ba số dương a, b và c. Hãy mô tả thuật toán cho biết ba số đó có thể là độ dài ba cạnh của một tam giác hay không?
Bài 4: Cho hai biến x và y. Hãy mô tả thuật toán đổi giá trị của hai biến nói trên (nếu cần) để x và y theo thứ tự có giá trị không giảm.
Bước 1: SUM 0;i 0
Bước 2: i > 100 thì chuy?n t?i bu?c 4
Bước 3: i i + 1; SUM SUM + i. Quay l?i bu?c 2.
Bước 4: Thông báo giá tr? SUM và kết thúc thuật toán.
Bài 5: Hãy cho biết kết quả của thuật toán sau:
Bài 6: Hãy mô tả thuật toán giải bài toán tính tổng các phần tử của dãy số cho trước.