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

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 d?nh b�i toỏn
4. M?t s? vớ d? v? thu?t toỏn
1. B�i toỏn v� xỏc d?nh b�i toỏn
Bài toán 1: 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 đó.
Bài toán 2: Lập một bảng điểm để quản lí kết quả học tập của học sinh trong một lớp.
Bài toán 3: Tìm các cách khắc phục tắc nghẽn giao thông trong giờ cao điểm.
? 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.
Bài toán là gì?
 Để giải quyết một bài toán cụ thể, ta cần xác định bài toán:
Điều kiện cho trước
Kết quả thu được
Bài toán 1
Đ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
Bài toán 2
Điều kiện cho trước: Thông tin của học sinh trong lớp (Họ tên, điểm các môn...)
Kết quả thu được: Kết quả học tập của học sinh
? Xỏc d?nh b�i toỏn l� bu?c d?u tiờn v� l� bu?c quan tr?ng trong vi?c gi?i quy?t b�i toỏn
1. Bài toán và xác định bài toán
Máy tính có thể tự giải các bài toán không?
2. Quỏ trỡnh gi?i b�i toỏn trờn mỏy tớnh?
ồ không! Tôi chỉ làm theo sự chỉ dẫn thôi!!!!
1. Bài toán và xác định bài toán
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
? D? mỏy tớnh cú th? gi?i cỏc b�i toỏn, ta c?n hu?ng d?n mỏy tớnh th?c hi?n m?t dóy h?u h?n cỏc thao tỏc d? t? cỏc di?u ki?n cho tru?c ta nh?n du?c k?t qu? c?n thu du?c.
2. Quỏ trỡnh gi?i b�i toỏn trờn mỏy tớnh?
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?
Xỏc d?nh b�i toỏn: xỏc d?nh di?u ki?n cho tru?c (input) v� k?t qu? c?n thu du?c (output).
Mụ t? thu?t toỏn: tỡm cỏch gi?i b�i toỏn v� di?n t? b?ng cỏc l?nh c?n ph?i th?c hi?n.
Vi?t chuong trỡnh: D?a v�o mụ t? thu?t toỏn ? trờn, vi?t chuong trỡnh b?ng m?t ngụn ng? l?p trỡnh dó bi?t.
1
2
3
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
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�, nu?c sụi, ?m v� chộn
Output: Chộn tr� dó pha d? m?i khỏch
INPUT: Tr?ng, d?u an, 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.
3. Thu?t toỏn v� mụ t? thu?t toỏn
VD3
Thuật toán giải phương trình bậc nhất tổng quát
bx + c = 0
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 =-c/b, 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.
3. Thu?t toỏn v� mụ t? thu?t toỏn
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.
3. Thu?t toỏn v� mụ t? 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:
Xác định Input và Output của bài toán
4. M?t s? vớ d? v? thu?t toỏn
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.
- 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.
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, gán giá trị 0 cho biến S
4. M?t s? vớ d? v? thu?t toỏn
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 d?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
4. M?t s? vớ d? v? thu?t 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
. . . . . . . . . . . . . . . . . . . .
4. M?t s? vớ d? v? thu?t toỏn
Bu?c 1: S ? 0; i ? 0;
Bu?c 3: N?u i <= 100 thỡ S ? S + i; v� quay l?i bu?c 2.
Bu?c 2: i ? i + 1
Thuật toán tính tổng
4. M?t s? vớ d? v? thu?t toỏn
Bước 4: Thông báo kết quả và kết thúc thuật toán.
Ví dụ 3: Đổi giá trị hai biến x và y
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 }
4. M?t s? vớ d? v? thu?t toỏn
Ví dụ 4: 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
4. M?t s? vớ d? v? thu?t toỏn
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
4. Một số ví dụ về thuật toán
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
4. Một số ví dụ về thuật toán
Ví dụ 5: Tìm số lớn nhất trong dãy A các số a1, a2,..., an.
INPUT: S? nguyờn duong 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?.

4. M?t s? vớ d? v? thu?t 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.
4. M?t s? vớ d? v? thu?t toỏn
Bu?c 1: Max ? a1 ; i ? 1
Bu?c 3: N?u i > N, chuy?n d?n bu?c 5
Thuật toán tìm max
Bu?c 2: i ?i +1
Bu?c 4: N?u ai > Max thỡ Max ? ai r?i quay l?i bu?c 2
tru?ng h?p ngu?c l?i gi? nguyờn Max v� quay
l?i bu?c 2
Bu?c 5: K?t thỳc thu?t toỏn
4. M?t s? vớ d? v? thu?t toỏ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)
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.
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ả.
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.