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

TIN HỌC 8
KIỂM TRA KIẾN THỨC CŨ
Câu 1: Biến là gì? Việc khai báo biến gồm mấy phần?
Khai báo 2 biến a, b thuộc kiểu số nguyên trong ngôn ngữ Pascal.
Câu 2: Hằng là gì? Khai báo hằng Pi có giá trị bằng 3.14 trong ngôn ngữ Pascal?
BÀI 5
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
NỘI DUNG BÀI HỌC
Bài toán và xác định bài toán
Quá trình giải bài toán trên máy tính
Thuật toán và mô tả thuật toán
Một số ví dụ về thuật toán
1. Bài toán và xác định bài toán
Bài toán 1: Tính diện tích hình tam giác khi biết một cạnh và chiều cao tương ứng với cạnh đó.
Bài toán 2: Tìm cách khắc phục tắc nghẽn giao thông trong giờ cao điểm.
Bài toán 3: Bài toán nấu một món ăn
Bài toán là gì?
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.
Xác định bài toán tức là xác định các điều kiện cho trước và kết quả cần đạt được
1. Bài toán và xác định bài toán
Ví dụ 1: Tính diện tích hình tam giác khi biết một cạnh và chiều cao tương ứng của cạnh đó.
Điều kiện cho trước:
một cạnh và chiều cao tương ứng
Kết quả cần đạt được:
Diện tích hình tam giác.
1. Bài toán và xác định bài toán
Bài toán 1: bài toán món trứng chiên
Bài toán 2: Tìm đường đi tránh các điểm nghẽn giao thông.
Bài toán 3: Cho 3 số a, b, c. Hãy sắp xếp các số sau theo theo thứ tự tăng dần.
Điều kiện cho trước (Input):
Trứng, mỡ, mắm, muối, rau…
Kết quả cần đạt được (Output):
Món trứng chiên.
1. Bài toán và xác định bài toán
Bài toán 2: Tìm đường đi tránh các điểm nghẽn giao thông từ điểm A đến điểm B.
Điều kiện cho trước (input):
Các đường đi từ AB, các điểm tắc nghẽn giao thông.
Kết quả cần đạt được (output):
Đường đi từ A B không qua điểm tắc nghẽn
Bài toán 3: Cho 3 số nguyên a, b, c. Hãy sắp xếp các số sau theo theo thứ tự tăng dần.
1. Bài toán và xác định bài toán
Điều kiện cho trước (input):
3 nguyên số a, b, c.
Kết quả cần đạt được (output):
3 số a, b,c theo thư tự tăng dần (a ≤ b ≤ c)
2. Quá trình giải bài toán trên máy tính
Bài toán
Máy tính chỉ làm theo sự chỉ dẫn
Con người phải hướng dẫn máy tính thực hiện một dãy các thao tác nào đó để từ điều kiện cho trước ta nhận được kết quả cần đạt được.
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 để giải một bài toán
Ví dụ: Tính tổng 2 số nguyên a và b được nhập từ bàn phím.
Input: 2 số a,b
Mô tả các bước giải bài toán
Output: Tổng a + b;
nhập số a;
nhập số b;
Tính tổng a + b;
In kết quả ra màn hình ;
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 gồm các bước sau:
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
? Xác định thông tin đã cho.
? Thông tin cần tìm .
? 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.
? Dựa vào mô tả thuật toán, ta viết chương trình bằng một ngôn ngữ lập trình.
? Xác định bài toán:
? Mô tả thuật toán:
? Viết chương trình:
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;
Bu?c 3: Rút nu?c sụi v�o ?m v� d?i trong 3 - 4 phỳt;
Bu?c 4: Rút tr� ra chộn d? 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
3. Thuật toán và mô tả thuật toán
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 = 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
INPUT: Tr?ng, d?u an, mu?i v� h�nh.
OUTPUT: Tr?ng trỏng.
Ví dụ 3: 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.
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
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 2 a, 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:
1
Tớnh S1 = a ? 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.
Input:
Output:
Chiều rộng 2a, chiều dài b, bán kính a
Diện tích hình A
4. M?t s? vớ d? v? thu?t toỏn
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 +….+100
Input:
Output:
Dãy 100 số tự nhiên đầu tiên 1, 2, . . .100
Giá trị tổng 1 + 2 + ….+ 100
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
Bước 1: Sum ? 0; i ? 0;
Bước 3: Nếu i <= 100 thì Sum ? Sum + i; và quay lại bước 2.
Bước 2: i ? i + 1
Bước 4: Thông báo kết quả và kết thúc thuật toán
Ví dụ 3: Tính tổng của 100 số tự nhiên đầu tiên liên tiếp
S = 1 + 2 + 3 +….+100
4. M?t s? vớ d? v? thu?t toỏn
Ví dụ 4: Đổi giá trị của 2 biến x và y
Input:
Output:
Hai biến x,y và 2 giá trị tương ứng a,b
Hai biến x, y và 2 giá trị tương ứng b,a
Cốc a
Cốc B
Làm cách nào đây?
4. M?t s? vớ d? v? thu?t toỏn
Cốc A
Cốc B
Cốc C
4. M?t s? vớ d? v? thu?t toỏn
A
A
B
C
4. M?t s? vớ d? v? thu?t toỏn
Ví dụ 4: Đổi giá trị của 2 biến x và y
Input:
Output:
Hai biến x,y và 2 giá trị tương ứng a,b
Hai biến c, y và 2 giá trị tương ứng 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}
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 nhỏ hơn b” hoặc “a=b”
Input: Hai số thực a và b
Output: Kết quả so sánh
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 a Bướ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
3
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 .
Quả này lớn nhất
Quả này mới lớn nhất
ồ! Quả này lớn hơn
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
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
DẶN DÒ
- Ôn lại bài học hôm nay.
- Trả lời các câu hỏi 1 trong SGK trang.
- Xem trước mục 3,4 để học trong tiết sau.
Tiết học đến đây là kết thúc