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ô giáo
Giáo Viên: Đoàn Đức Trọng
Trường THCS Thuỵ Phong
Năm Học 2010 - 1011
Giáo Viên: Đoàn Đức Trọng
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
3. Thuật toán và mô tả thuật toán
2. Quá trình giải bài toán trên máy tính?
1. Bài toán và xác định bài toán là gì?
4. Một số ví dụ về thuật toán
Tin học 8
Tiết 26
1. Bài toán và xác định bài toán
Bài toán là gì 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
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
2. Quá trình giải bài toán trên máy tính?
Để giải quyết một bài toán cụ thể , ta cần .
Điều kiện cho trước
Kết quả thu được
Xác định bài toán
Điều kiện cho trước: Một cạnh và đường cao tương ứng với cạnh đó
Kết quả thu được: Diện tích hình tam giá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.
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
Bài toán: Tính diện tích của một tam giác biết một cạnh và đường cao tương ứng với cạnh đó.
1. Bài toán và xác định bài toán
xác định bài toán
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 của con người thôi!!!!
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
1. Bài toán và xác định bài toán
2. Quá trình giải bài toán trên máy tính?
Để máy tính có thể
giải các bài toán ta phải làm gì?
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
1. Bài toán và xác định bài toán
2. Quá trình giải bài toán trên máy tính?
? Để máy tính có thể giải các bài toán, ta cần hướng dẫn máy tính thực hiện một dãy hữu hạn các thao tác để từ các điều kiện cho trước ta nhận được kết quả cần thu được.
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
1. Bài toán và xác định bài toán
2. Quá trình giải bài toán trên máy tính?
Dãy hữu hạn các thao tác để giải một bài toán
thường được gọi là thuật toán
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ớ!
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
Xác định bài toán: xác định điều kiện ban đầu (input) và kết quả cần xác định (output).
Xây dựng thuật toán: Lựa chọn và mô tả các thao tác sẽ thực hiệ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 sao cho máy tính có thể hiểu và thực hiện được.
1
2
3
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
1. Bài toán và xác định bài toán
2. Quá trình giải bài toán trên máy tính?
Quá trình giải bài toán trên máy tính gồm các bước sau:
VD1
Các bước thực hiện để pha trà mời khách ntn nhỉ ?
Bước 1: Tráng ấm chén bằng nước sôi;
Bước 2: Cho một nhúm trà vào ấm;
Bước 3: Tráng trà;
Bước 4: Rót nước sôi vào ấm và đợi trong 3 - 4 phút;
Bước 5: Rót trà ra chén để mời khách;
3. Thuật toán và mô tả thuật toán
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
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
1. Bài toán và xác định bài toán
2. Quá trình giải bài toán trên máy tính?
INPUT: Trứng, dầu ăn, muối và hành.
OUTPUT: Trứng tráng.
Ví dụ 2: Thuật toán "Làm món 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 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.
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
3. Thuật toán và mô tả thuật toán
1. Bài toán và xác định bài toán
2. Quá trình giải bài toán trên máy tính?
VD3
Thuật toán giải phương trình bậc nhất dạng tổng quát: bx + c = 0
Bước 1: Nếu b = 0 chuyển tới bước 3 (kiểm tra c);
Bước 2: Tính nghiệm của phương trình x =
rồi chuyển tới bước 4;
Bước 3: Nếu c? 0 thông báo phương trình vô nghiệm, ngược lại (c = 0) thông báo phương trình vô số nghiệm.
Bước 4: Kết thúc thuật toán.
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
3. Thuật toán và mô tả thuật toán
1. Bài toán và xác định bài toán
2. Quá trình giải bài toán trên máy tính?
Các bước của ba thuật toán trên có thay đổi trình tự được không ?
Thuật toán là dãy 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.
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
3. Thuật toán và mô tả thuật toán
1. Bài toán và xác định 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àm món 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 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.
Ví dụ 1. 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
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
Ví dụ 2: Tính tổng của 100 số tự nhiên đầu tiên
liên tiếp S = 1 + 2 + 3 + 4 + ... + 100
Ví dụ 3: Đổi giá trị hai biến x=a và y=b.
Ví dụ 4: Tìm số lớn nhất trong dãy A các số a1, a2,..., an.
Hoạt động nhóm
Hãy xác định bài toán và mô tả thuật toán các ví dụ sau:
Bài toán: Đổi nước ở hai cốc này cho nhau
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à cốc B có thể tích như nhau)
Cốc A
Cốc B
Làm cách nào đây?
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
4. Một số ví dụ về thuật toán
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
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
4. Một số ví dụ về thuật toán
Bài toán: Đổi nước ở hai cốc này cho nhau
2. Đổ nước màu đỏ ở cốc A sang cốc C
Cốc A
Cốc B
Cốc C
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
4. Một số ví dụ về thuật toán
Bài toán: Đổi nước ở hai cốc này cho nhau
3. Đổ nước màu xanh ở cốc B sang cốc A
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
Cốc A
Cốc B
Cốc C
4. Một số ví dụ về thuật toán
Bài toán: Đổi nước ở hai cốc này cho nhau
4. Đổ nước màu đỏ ở cốc C sang cốc B
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
Cốc A
Cốc B
Cốc C
4. Một số ví dụ về thuật toán
Bài toán: Đổi nước ở hai cốc này cho nhau
Cốc A
Cốc B
Cốc C
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
4. Một số ví dụ về thuật toán
Bài toán: Đổi nước ở hai cốc này cho nhau
Cốc A
Cốc B
Ví dụ 3: Đổi giá trị hai biến x =a và y =b
Input: Hai biến x và y có giá trị tương ứng là a, b
Output: Hai biến x và y có giá trị tương ứng là b, a
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à giá trị ban đầu a của biến x}
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
1. xác định bài toán
2. Mô tả thuật toán
4. Một số ví dụ về thuật toán
Ví dụ 1. 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:
hình A
b
a
Xác định Input và Output của bài toán
4. Một số ví dụ về thuật toán
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
b
1. xác định bài toán
- OUTPUT : Diện tích của hình A.
- INPUT: Số a là 1/2 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.
1
Tính S1 2a ? b {(Tính S hình CN)};
2
Tính S2 ? a2/2 {(S hình bán nguyệt)};
3
Tính S S1 + S2 và kết thúc.
Lưu ý: Trong biểu diễn thuật toán kí hiệu ? để chỉ phép gán một giá trị cho biến.
VD S ? 0 là gán giá trị 0 cho biến S
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
2. Mô tả thuật toán
a
a
b
4. Một số ví dụ về thuật toán
Ví dụ 1.
Xác định Input và Output của bài toán
- OUTPUT : Tổng của dãy số trên.
- INPUT: Dãy 100 số tự nhiên đầu tiên: 1, 2, ... 100.
Ví dụ 2: Tính tổng của 100 số tự nhiên đầu tiên
liên tiếp S = 1 + 2 + 3 + 4 + ... + 100
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
4. Một số ví dụ về thuật toán
1. xác định bài toán
Nhận xét:
S = 0
S1 = S + 1
S2 = S1 + 2
S3 = S2 + 3


.....
S100 = S99 + 100
Bắt đầu từ S1 việc tính S được lặp đi lặp lại 100 lần theo quy luật
Ssau = Strước+ i
với i tăng lần lượt từ 1 đến100
. . . . . . . . . . . . . . . . . . . .
2. Tìm thuật toán
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
Bước 1: S ? 0; i ? 0;
Bước 3: Nếu i <= 100 thì S ? S + i; và quay lại bước 2. trong trường hợp ngược lại thông báo kết quả rồi kết thúc thuật toán.
Bước 2: i ? i + 1
Thuật toán tính tổng
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
i := i + 1
S  S + i
i
S
3
Bài toán: Tìm quả bóng lớn nhất
Người ta đặt 5 quả bóng có kích thước khác nhau trong hộp đã được đậy nắp như hình bên.Chỉ dùng tay hãy tìm ra quả bóng có kích thước lớn nhất .
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
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
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
Ví dụ 4: Tìm số lớn nhất trong dãy A các số a1, a2,..., an.
INPUT: Số nguyên dương N và dãy N số nguyên
a1,a2,.aN. (ai với i: 1?n)
OUTPUT: Số lớn nhất (Max) của dãy số.

Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
4. Một số ví dụ về thuật toán
1. xác định bài toán
ý tưởng:
- Đặt giá trị Max= a1
- Lần lượt cho i chạy từ 2 đến N, so sánh
giá trị ai với giá trị Max, nếu ai> Max thì
Max nhận giá trị mới là ai.
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
tìm max
Bước 1: Max ? a1 ; i ? 1
Bước 3: Nếu i > N, chuyển đến bước 5
Thuật toán tìm max
Bước 2: i ?i +1
Bước 4: Nếu ai > Max thì Max ? ai rồi quay lại bước 2
trường hợp ngược lại giữ nguyên Max và quay
lại bước 2
Bước 5: Kết thúc thuật toán
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
Bài tập: 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"
Bước 1: So sánh a và b. Nếu a>b, cho kết quả "a lớn hơn b"
Bước 2: Nếu aInput: Hai số thực a và b
Output: Kết quả so sánh
Hãy tìm chỗ chưa đúng trong thuật toán sau
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
củng cố
Ta thấy, sau bước 1 ta được kết quả
Nhưng trong bước hai, khi kiểm tra aThử lại với a=6 và b=5
? a lớn hơn b
? a = b
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
Bước 1: So sánh a và b. Nếu a>b, cho kết quả "a lớn hơn b" và chuyển đến bước 3
Bước 2: Nếu aBước 3: Kết thúc thuật toán
Thuật toán so sánh 2 số thực
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5
Để viết được câu lệnh Nếu...thì... Mời các em sẽ học ở bài sau. Bài 6 Câu Lệnh Điều Kiện
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.
Tõ BµI TO¸N §ÕN CH¦¥NG TR×NH
bài 5

L�m b�i t�p 1, 2, 3, 4, 5, 6 trong SGK.

Chu�n b� b�i 6: C�u LƯnh DiỊu KiƯn
DẶN DÒ
Chúc các Thầy cô mạnh khoẻ
Giáo Viên: Đoàn Đức Trọng
Trường THCS Thuỵ Phong
Năm Học 2010 - 1011