Tiết 18-20:Bài 5

TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH

1. BÀI TOÁN VÀ XÁC ĐỊNH BÀI TOÁN
Bài toán là gì?
Là công việc hay một nhiệm vụ cần phải giải quyết
Để giải quyết được một bài
toán cụ thể, ta cần phải xác
định rõ điều gì̀?
* Xác định các điều kiện cho trước.
* Kết quả thu được

Xác định bài toán

Ví dụ 1: Xét bài toán
“Tính diện tích hình tam
giác”.

Điều kiện cho trước

Một cạnh và đường cao
tương ứng

Kết quả cần thu được

Diện tích hình tam giác

Ví dụ 2: Xét bài toán “Tìm
đường đi tránh các điểm
nghẽn giao thông”.

Điều kiện cho trước

Kết quả cần thu được

• Vị trí điểm nghẽn giao thông.
• Các con đường có thể đi từ vị
trí hiện tại tới vị trí cần tới
Đường đi từ vị trí hiện tại tới
vị trí cần tới mà không qua
điểm nghẽn giao thông.

2. QUÁ TRÌNH GIẢI BÀI TOÁN TRÊN MÁY TÍNH
Thế nào là giải bài toán trên
máy tính?
Là việc nào đó ta muốn máy tính thực hiện để từ các
điều kiện cho trước ta nhận được kết quả cần thu được
Ví dụ: Tìm ước số chung lớn nhất của hai số nguyên dương M và N
Điều kiện cho trước: hai số nguyên dương M và N.
Kết quả cần thu được: Ước số chung lớn nhất của M và N.

Em hiểu như thế nào là thuật
toáǹ?
* Các bước để giải một bài toán

Quá trình giải bài toán trên
máy tính như thế nào?

1. Xác định bài toán

2. Mô tả thuật toán

3. Viết chương trình

• Xác định thông tin đã cho (INPUT).
• Tìm được
(OUTPUT)

thông

tin

cần

tìm

• Tìm cách giải bài toán
• 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

3.THUẬT TOÁN VÀ MÔ TẢ THUẬT TOÁN
Xét bài toáṇ : Giải phương
trình bậc nhất dạng tổng quát
ax + b = 0
1. Xác định bài toán
• INPUT

Các hệ số a và b

• OUTPUT

Nghiệm của phương trình bậc nhất

2. Mô tả thuật toán
Bước1 : xác định hệ số a, b;
Bước 2 : nếu a = 0 và b = 0  phương trình vô số nghiệm  B5;
Bước 3 : nếu a = 0 và b ≠ 0  phương trình vô nghiệm  B5;
Bước 4 : nếu a ≠ 0  phương trình có nghiệm x = -b/a  B5;
Bước 5 : Kết thúc.

Thuận toán là gì?
* 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 để từ INPUT của bài toán ta nhận được
OUTPUT cần tìm.

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 là 2a,
chiều dài là b và một hình bán nguyệt
bán kính a như hình
b

2a

a

1. Xác định bài toán
• INPUT

Các hệ số b và a

• OUTPUT

Diện tích S của hình A

2. Mô tả thuật toán
Bước1 : xác định hệ số b, a;
Bước 2 : Tính S1 ← 2ab;
2

a
Bước 3 : Tính S2 ←
2

Bước 4 : S ← S1 + S2
Bước 5 : Kết thúc.

;

Ví dụ 2: Tính tổng của 100 số
tự nhiên đầu tiên

1. Xác định bài toán
• INPUT

Dãy 100 số tự nhiên đầu tiên: 1, 2, …, 100

• OUTPUT

Giá trị của tổng 1+2+…+100

2. Mô tả thuật toán
Bước1 : SUM ← 0; i ← 0;
Bước 2 : i ← i + 1;
Bước 3 : Nếu i ≤ 100, thì SUM ← SUM + i và quay lại bước 2 ;
Bước 4 : Thông báo kết quả và kết thúc bài toán.

Ví dụ 3: Đổi giá trị của hai biến x và y
1. Xác định bài toán
• INPUT

Hai biến x và y có giá trị tương ứng là a và b

• OUTPUT

Hai biến x và y có giá trị tương ứng là b và a

2. Mô tả thuật toán
Bước1 : z ← x;
Bước 2 : x ← y;
Bước 3 : y ← z;

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”, “a bằng b”,
1. Xác định bài toán
• INPUT

Hai số thực a và b

• OUTPUT

Kết quả so sánh

2. Mô tả thuật toán
Bước1 : Nếu a > b, kết quả là “a lớn hơn b”;
Bước 2 : Nếu a < b, kết quả là “a nhỏ hơn b”; ngược lại là
“a bằng b”;
Bước 3 : Kết thúc thuật toán;

Ví dụ 5: Tìm số lớn nhất trong dãy
số A các số a1, a2, …,an

Quả này
lớn nhất

MAX

Quả này
mới lớn
nhất ?

Ồ ! Quả
Tìm
ra quả
nàynhất
lớn rồi
lớn
hơn

1. Xác định bài toán
• INPUT

dãy số A các số a1, a2, …,an (n≥1)

• OUTPUT

Giá trị MAX = max{a1, a2, …,an}

2. Mô tả thuật toán
Bước1 : MAX ← a1; i ← 1;
Bước 2 : i ← i + 1;
Bước 3 : Nếu i > n, thì chuyển đến bước 5;
Bước 4 : Nếu ai > MAX, MAX ← ai, Quay lại bước 2;
Bước 5 : Kết thúc thuật toán;

GHI NHỚ
1. 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 – INPUT) và các kết quả cần thu
được (thông tin ra – OUTPUT).
2. Giải bài toán trên máy tính 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à nó có
thể thực hiện được để cho ta kết quả.
3. 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; mô tả thuật toán; viết chương
trình.
4. Thuật toán là dãu hữu hạn các thao tác cần thực hiện
theo một trình tự xác định để nhận được kết quả cần
tìm từ những điều kiện cho trước.

DẶN DÒ

1. Trả lời câu hỏi 1, 2, 3, 4, 5, 6 _ trang 45
_ sách giáo khoa .