1/11
00:38
--- Giải bài toán trên máy tính ---
Bài toán:
Cho tam giác ABC vuông tại A có AB= 4cm; BC=5cm;
Tính AC?
Em tiến hành giải bài toán trên như thế nào?
Đọc kĩ đề xem đề cho biết cái gì và cần tìm cái gì?
Tìm cách giải
Trình bày lời giải
Kiểm tra lại bài làm, chỉnh sửa (chính tả, công thức,...)
Xác định bài toán
Lựa chọn hoặc thiết kế thuật toán
Viết chương trình
Hiệu chỉnh
Viết tài liệu
Vì tam giác ABC vuông tại A
nên theo định lí Pitago ta có:
AB2 + AC2 = BC2
AC2 = BC2 – AB2
AC2= 52 – 42 = 9
AC= 3
Vậy độ dài cạnh AC là 3 dm


Sử dụng định lí Pitago:
AB2 + AC2 = BC2
 AC2 = BC2 – AB2
Đề cho biết:
Tam giác ABC vuông tại A
Độ dài cạnh AB
Độ dài cạnh BC
Cần tìm:
- Độ dài cạnh AC
Vì tam giác ABC vuông tại A
nên theo định lí Pitago ta có:
AB2 + AC2 = BC2
AC2 = BC2 – AB2
AC2= 52 – 42 = 9
AC= 3
Vậy độ dài cạnh AC là 3 cm


Việc giải bài toán trên máy tính tiến hành qua các bước như thế nào?
2/11
00:38
--- Giải bài toán trên máy tính ---
Xác định bài toán
Lựa chọn hoặc thiết kế thuật toán
Viết chương trình
Hiệu chỉnh
Viết tài liệu
§6
GIẢI BÀI TOÁN TRÊN MÁY TÍNH
3/11
00:38
--- Giải bài toán trên máy tính ---
1. Xác định bài toán:
BÀI TOÁN
Xác định BT là việc xác định rõ Input, Output và mối quan hệ giữa chúng
Input
Output
Mối quan hệ
Ví dụ: Cho tam giác ABC vuông tại A có AB= 4cm; BC=5cm; Tính AC?
Input: số thực a, c để chỉ độ dài cạnh AB, BC
Output: số thực b để chỉ độ dài cạnh AC.
a2 + b2 = c2
4/11
00:38
--- Giải bài toán trên máy tính ---
2. Lựa chọn hoặc thiết kế thuật toán:
a. Lựa chọn thuật toán:
Giải hệ phương trình bậc nhất hai ẩn:


Ví dụ:
Phương pháp thế
Từ (2) ta có y= x-6
Thay y = x-6 vào (1) ta có:
2x + 5(x-6)=-2 7x- 30=-2
 x= 4  y = -2
Vậy nghiệm của hệ là (4, -2)
Phương pháp cộng
Nhân 2 vế của (2) với 2 ta có
-2x+2y=-12(3)
Cộng (1) và (3) vế với vế ta có:
7y=-14  y= -2
Thay vào (2) ta có x=4.
Vậy nghiệm của hệ là (4, -2)
5/11
00:38
--- Giải bài toán trên máy tính ---
2. Lựa chọn hoặc thiết kế thuật toán:
a. Lựa chọn thuật toán:
BÀI TOÁN TÌM KIẾM
B1: Nhập dãy, nhập khoá k.
B2: i  1;
B3: Nếu ai =k thì thông báo chỉ số i rồi kết thúc.
B4: i  i+1;
B5: Nếu i>N thì thông báo dãy A không có số hạng nào có giá trị bằng k rồi kết thúc.
B6: Quay lại B3
Ví dụ:
Thuật toán tìm kiếm tuần tự
Thuật toán tìm kiếm nhị phân
Mỗi thuật toán chỉ giải một bài toán, nhưng có thể có nhiều thuật toán khác nhau cùng giải một bài toán.
6/11
00:38
--- Giải bài toán trên máy tính ---
2. Lựa chọn hoặc thiết kế thuật toán:
Khi thiết kế hoặc lựa chọn thuật toán, người ta quan tâm đến các tài nguyên như: thời gian thực hiện, số lượng các ô nhớ,...
thời gian thực hiện
Ngoài ra người ta quan tâm đến là thiết kế hoặc lựa chọn thuật toán sao cho việc viết chương trình ít phức tạp
Khi thiết kế hoặc lựa chọn thuật toán để giải 1 bài toán cụ thể cần căn cứ vào lượng tài nguyên mà thuật toán đòi hỏi và lượng tài nguyên thực tế cho phép
7/11
00:38
--- Giải bài toán trên máy tính ---
2. Lựa chọn hoặc thiết kế thuật toán:
b. Diễn tả thuật toán
Ví dụ: Tìm ước chung lớn nhất (ƯCLN) của 2 số nguyên dương M và N
Xác định bài toán:
Input: Cho M, N;
Output: ƯCLN(M,N)
Ý tưởng:
Nếu M=N thì ƯCLN của M và N là M
Nếu M > N thì
ƯCLN(M,N) = ƯCLN(M-N, N)
Nếu MƯCLN(M,N) = ƯCLN(M, N - M)
Thuật toán:
B1: Nhập M, N;
B2: Nếu M = N thì lấy giá trị chung này làm ƯCLN rồi chuyển đến B5
B3: Nếu M>N thì M  M-N rồi quay lại B2
B4: N  N-M rồi quay lại B2
B5: Đưa ra kết quả ƯCLN rồi kết thúc.
sđk
8/11
00:38
--- Giải bài toán trên máy tính ---
3. Viết chương trình
Lựa chọn cách tổ chức dữ liệu
Sử dụng ngôn ngữ lập trình
Viết chương trình
Ví dụ:
Chương trình cho bài toán tìm ƯCLN viết trên ngôn ngữ lập trình Pascal
Viết chương trình trong ngôn ngữ nào thì phải tuân theo đúng qui định ngữ pháp của ngôn ngữ đó.
Chương trình dịch chỉ có thể phát hiện và thông báo các lỗi về mặt ngữ pháp
9/11
00:38
--- Giải bài toán trên máy tính ---
4. Hiệu chỉnh:
Cần phải thử chương trình bằng cách thực hiện nó với nhiều bộ Input tiêu biểu của bài toán
Những bộ Input và Output tương ứng này gọi là các Test.
Nếu sai sót ta phải sửa lại rồi thử lại.
Hiệu chỉnh
Ví dụ: Kiểm chứng tính đúng đắn của chương trình giải phương trình bậc hai ax2 + bx + c = 0 , ta có thể sử dụng bộ Input như sau:
Biệt số ∆ > 0: a=1, b=-5, c=6
Biệt số ∆ = 0: a=1, b=-4, c=4
Biệt số ∆ > 0: a=1, b=4, c=8
Chương trình đưa ra 2 nghiệm
Chương trình đưa ra 1 nghiệm
Chương trình th.báo vô nghiệm
10/11
00:38
--- Giải bài toán trên máy tính ---
5. Viết tài liệu:
Tài liệu phải:
Mô tả bài toán, thuật toán
Thiết kế chương trình
Kết quả thử nghiệm
Hướng dẫn sử dụng
Bt
11/11
00:38
--- Giải bài toán trên máy tính ---
Củng cố
Như vậy để giải bài toán trên máy tính chúng ta cần thực hiện qua 5 bước:
Xác định bài toán
Lựa chọn hoặc thiết kế thuật toán
Viết chương trình
Hiệu chỉnh
Viết tài liệu
12/11
00:38
--- Giải bài toán trên máy tính ---
Bài tập
Hãy xác định bài toán, lựa chọn hoặc thiết kế thuật toán cho bài toán sau:
- Giải phương trình bậc nhất một ẩn: ax+b=0
b
Input: Các hệ số a, b
Output: thông báo nghiệm của phương trình (1 nghiệm, vô nghiệm hay vô số nghiệm)
Thuật toán:
B1: Nhập các hệ số a, b
B2: Nếu a = 0 và b= 0 thì đưa ra thông báo phương trình có vô số nghiệm rồi kết thúc
B3: Nếu a = 0 và b ≠ 0 thì thông báo phương trình vô nghiệm rồi kết thúc.
B4: Nếu a ≠ 0 thì thông báo phương trình có 1 nghiệm là –b/a rồi kết thúc.
13/11
00:38
--- Giải bài toán trên máy tính ---
Nhập M và N
M = N?
Đưa ra M rồi kết thúc
Đúng
M > N?
M  M-N
Đúng
Sai
Sai
N  N - M
B1
B2
B3
B4
B5
14/11
00:38
--- Giải bài toán trên máy tính ---
2. Lựa chọn hoặc thiết kế thuật toán:
Ví dụ: Tìm ƯCLN (35, 15)
M = 35
N = 15
M > N
M  M- N
M = 35
M = 20
N = 15
Lần duyệt 1
M = 20
M > N
M  M- N
M = 5
N = 15
Lần duyệt 2
M < N
N  N-M
N = 10
M = 5
Lần duyệt 3
N = 15
M < N
N  N-M
N = 10
N = 5
M = 5
Lần duyệt 4
ƯCLN(35, 15) = 5
15/11
00:38
--- Giải bài toán trên máy tính ---
2. Lựa chọn hoặc thiết kế thuật toán:
Ví dụ: Tìm ƯCLN (11, 13)
ƯCLN(11, 13) = 1
M=11
N=13
Lần duyệt 1
N N- M
M=11
N=2
Lần duyệt 2
M M-N
M=9
N=2
Lần duyệt 3
M M-N
M=7
N=2
M=5
N=2
Lần duyệt 5
M M-N
M=3
N=2
Lần duyệt 6
M M-N
M=1
N=2
Lần duyệt 7
N N-M
M=1
N=1