Bài 4. Bài toán và thuật toán

Tiết 8,9,10,11,12

Bài 4:
Bài Toán Và Thuật Toán
TIN HỌC 10
1. Khái niệm bài toán
 Lµ viÖc nµo ®ã ta muèn m¸y thùc hiÖn ®Ó tõ th«ng tin ®­ưa vµo (INPUT) t×m ®­ưîc th«ng tin ra (OUTPUT).
Bài 4. Bài toán và thuật Toán
Vdụ 1:Tìm ưuớc số chung lớn nhất của hai số nguyên dưuơng
M , N.
INPUT: Hai số nguyên dưuơng M và N.
OUTPUT: ưUớc số chung lớn nhất của M và N.
Ví dụ 2: Giải phưuơng trình bậc nhất ax + b = 0.
a,b nh?p t? b�n phớm
?Input: Các hệ số a, b.
? Output: Nghiệm x của thõa mãn phuưương trình
ax + b = 0.
Ví dụ 3: Quản lí điểm trong h?c sinh trong máy tính.
Ví dụ 4: Bài toán xếp loại học tập của một lớp.
INPUT: Bảng điểm của học sinh trong lớp.
OUTPUT: Bảng xếp loại học lực của học sinh.
?Input: SBD, Họ và tên, Văn, Toán, Lí, Anh.
? Output: Tổng điểm, Kết quả của học sinh.
22
? Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác đưuợc sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận đưuợc Output cần tìm.
Có hai cách thể hiện một thuật toán:
? Liệt kê: t/bày các thao tác của thuật toán theo từng bưuớc
? Sơ đồ khối dùng 1 số hình khối để biểu diễn thuật toán :
2. Khái niệm thuật toán

Dùng để nhập và xuất dữ liệu.

Dùng để gán giá trị và tính toán.

Xét điều kiện rẽ nhánh theo một trong hai điều kiện đúng, sai.

đ
S
3. Một số ví dụ về thuật toán
Xét ví dụ 2: Giải phuương trình bậc nh?t ax + b = 0.
B1: Nhập a, b;
B2: Nếu a=0 và b=0 => Phuương trình vô số nghiệm, kthuc;
B3: Nếu a=0 và b?0 => Phuương trình vô nghiệm, kthuc;
B4: Phuương trình có nghiệm -b/a,kthuc;
S
s
B1
B2
B3
B4
Đ
đ
B1: Nhập a, b, c;
B2: Tính ? = b2 - 4ac;
B3: Nếu ? < 0 => PT vô nghiệm => kt;
B4: Nếu ? = 0 => PT có nghiệm kép x = -b/2a =>kthuc;
B5: PT có hai nghiệm x1, x2 = (-b ? ??)/2a , kthuc
Thuật toán giải p/trình bậc hai ax2+bx+c=0 (a ? 0).
đ
s
2
B1
B2
B3
B4
B5
s
đ
a,b,c= 1 3 5
D = 3*3 - 4*5 = - 11
-11 < 0
PT vô nghiệm, KT
S
PT có 2 nghiệm
x1, x2 = (-b ??? )/2a, Kt
Đ
S
D = b*b - 4*a*c
nhËp vµo a,b,c
 < 0
Mô phỏng thuật toán giải phuương trình bậc hai
Bộ TEST 1:
a,b,c= 1 2 1
D = 2*2 - 4*1*1 = 0
PT vô nghiệm
PT có nghiệm x=-b/2a
S
PT có 2 nghiệm
x1, x2 = (-b ??? )/2a
Đ
S
D = b*b - 4*a*c
nhËp vµo a,b,c
 < 0
Mô phỏng thuật toán giải phuương trình bậc hai
Bộ TEST 2:
Đ
 = 0
PT có nghiệm kép x=-1
a,b,c= 1 -5 6
D = 25 - 24 = 1
PT vô nghiệm, Kt
PT có nghiệm x=-b/2a, Kt
S
PT có 2 nghiệm
x1, x2 = (-b ??? )/2a,KT
Đ
S
D = b*b - 4*a*c
nhËp vµo a,b,c
 < 0
Mô phỏng thuật toán giải phuương trình bậc hai
Bộ TEST 3:
Đ
 = 0
PT có nghiệm x1 = 3
x2 = 2, KT
a,b,c= 1 -5 6
D = 25 - 24 = 1
PT vô nghiệm, Kt
PT có nghiệm x=-b/2a, Kt
S
PT có 2 nghiệm
x1, x2 = (-b ??? )/2a,KT
Đ
S
D = b*b - 4*a*c
nhËp vµo a,b,c
 < 0
Mô phỏng thuật toán giải phuương trình bậc hai
Bộ TEST 3:
Đ
 = 0
PT có nghiệm x1 = 3
x2 = 2, KT
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!
Thuật toán tìm max
Thuật toán tìm số lớn nhất trong
một dãy số nguyên
Xác định bài toán:
INPUT: Số nguyên dưuơ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ưuởng:
- Đặt giá trị Max = a1. {g?i i l� v? trớ c?n so sỏnh}

- Lần luượ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.
 Bµi to¸n: Cho dãy A gồm N số nguyên a1, a2 ,…, aN. Cần tìm giá trị lớn nhất Max trong dãy A

Đ
S
Đ
S
B1: Nhập N và dãy a1,.,aN;
B2: Max ? a1; i ? 2;
B3: Nếu i > N thì đưa ra giá trị
Max rồi kết thúc;
B4 : Nếu ai > Max thì Max ? ai;
B5: i ? i + 1, quay lại B3.
Sơ đồ khối - Liệt kê
B1: Nhập N và dãy a1,.,aN;
B2: Max ? a1; i ? 2;
B5: Nếu i > N thì đưa ra giá trị
Max rồi kết thúc;
B3 : Nếu ai > Max thì Max ? ai;
B4: i ? i + 1.
Sơ đồ khối - Liệt kê
B6: Quay lại B3.
Đ
S
Đ
S
Nhập N và dãy a1,.,aN
Max ? a1 ; i ? 2
I > N ?
ai> Max ?
Max ai
i  i+1
Đuưa ra Max rồi kết thúc
Max
i
A
7
7
5
5
5
5
4
3
2
6
7
4
1
5
N=5 ; A [ 5 1 4 7 6 ]
Max ? 5 ; i ? 2
2 > 5 ?
1> 5 ?
i  2+1
3 > 5 ?
4> 5 ?
i 3+1
4 > 5 ?
7 > 5 ?
Max 7
4
i 4+1
5 > 5 ?
7 > 7 ?
i 5+1
6 > 5 ?
Số lớn nhất của dãy là 7
Mô phỏng
thuật toán
Với i = 2
Với i = 3
Với i = 4
Với i = 5
Đ
S
Đ
S
Nhập N và dãy a1,.,aN
Max ? a1 ; i ? 2
I > N ?
ai> Max ?
Max ai
i  i+1
Đưua ra Max rồi kết thúc
Max
i
A
7
7
5
5
5
5
4
3
2
6
7
4
1
5
N=5 ; A [ 5 1 4 7 6 ]
Max ? 5 ; i ? 2
2 > 5 ?
1> 5 ?
i  2+1
3 > 5 ?
4> 5 ?
i 3+1
4 > 5 ?
7 > 5 ?
Max 7
4
i 4+1
5 > 5 ?
7 > 7 ?
i 5+1
6 > 5 ?
Số lớn nhất của dãy là 7
Xác định bài toán:
INPUT: Dãy A gồm N số nguyên a1, a2,., aN khác nhau và số nguyên k.
OUTPUT: Chỉ số i mà ai = k hoặc thông báo
không có số hạng nào của A bằng k.
Thuật toán tìm kiếm

ý tưuởng: Lần luượt từ số hạng thứ nhất, ta so sánh g/tr? số hạng đang xét với khoá (k) cho đến khi có sự trùng nhau, nếu đã xét tới số hạng cuối cùng mà không có sự trùng nhau thì có nghĩa là dãy A không có số hạng nào có g/trị bằng k.
 Bµi to¸n: Cho dãy A gồm N số nguyên khác nhau: a1, a2 ,…, aN và số nguyên k. Cần biết có hay không chỉ số i(1≤ i ≤N) mà ai=k. Nếu có hãy cho biết chỉ số đó.

5
4
3
2
1
I
8
9
2
4
1
7
5
A
Mô phỏng thuật toán tìm kiếm tuần tự
? Với k = 2 và dãy A gồm 7 số hạng nhưu sau:
Tại vị trí i = 5 có a5 = 2 = k
? Với k = 2 và dãy A gồm 6 số hạng nhuư sau:
Với mọi i từ 1? 6 không có ai có giá trị bằng 6
5
Cách 1: Liệt kê các bước
B1: Nhập N, các số hạng a1, a2,., aN
và s? nguyờn k;
Bư2: i ? 1;
Bư3: Nếu ai = k thì thông báo chỉ số i, rồi kết thúc;
Bư4: i ? i+1;
Bư5: 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;
Bư6: Quay lại B3.
Nhập N, a1, a2,..., aN
và k
i ? 1
ai = k ?
Đuưa ra i
rồi kết thúc
Đ
S
Đ
i ?i + 1
i > N ?
Thông báo dãy A không có số hạng có giá trị bằng k, rồi kết thúc
S
Cách 2
Vẽ sơ đồ khối
i ? 1
ai = k ?
Đuưa ra i
rồi kết thúc
Đ
S
Đ
i ?i + 1
i > N ?
Thông báo dãy A không có số hạng có giá trị bằng k, rồi kết thúc
S
5
4
3
2
1
i
8
9
2
4
1
7
5
A
5
Nhập N, a1, a2,..., aN
và k
N=7 ; A [ 5 7 1 4 2 9 8 ]
k =2
i ? 1
5 = 2 ?
i ?1+ 1
2 > 7 ?
Với i = 1
Với i = 2
7 = 2 ?
i ?2+ 1
3 > 7 ?
Với i =3
1 = 2 ?
i ?3+ 1
4 > 7 ?
Với i =4
4 = 2 ?
i ?4+ 1
5 > 7 ?
Với i =5
2 = 2
T/b 2 thuộc dãy A tại vị trí 5, KT
i ? 1
ai = k ?
Đuưa ra i
rồi kết thúc
Đ
S
Đ
i ?i + 1
i > N ?
Thông báo dãy A không có số hạng có giá trị bằng k, rồi kết thúc
S
5
4
3
2
1
i
9
3
4
1
7
5
A
Nhập N, a1, a2,..., aN
và k
N=6 ; A [ 5 7 1 4 3 9 ]
k =2
i ? 1
5 = 2 ?
i ?1+ 1
2 > 6 ?
Với i = 1
Với i = 2
7 = 2 ?
i ?2+ 1
3 > 6 ?
Với i =3
1 = 2 ?
i ?3+ 1
4 > 6 ?
Với i =4
4 = 2 ?
i ?4+ 1
5 > 6 ?
Với i =5
3 = 2 ?
i ?5+ 1
6
6 > 6 ?
Với i =6
9 = 2 ?
i ?6+ 1
7
T/b dãy A không có số hạng có giá trị bằng 2, rồi kết thúc
7 > 6 ?
7
Thuật toán
Bài toán 4: Cho dóy A g?m N s? nguyờn : a1, a2 ,., aN. Tớnh t?ng cỏc ph?n t? l� s? l? trong dóy trờn

B1: Nhập N, các số hạng a1, a2,., aN

Bư2: i ? 1; S?0
Bư3: Nếu ai khụng chia h?t cho 2 thì S?S+ai, rồi kết thúc;
Bư4: i ? i+1;
Bư5: Nếu i > N thì thông báo t?ng S cỏc s? l? trong dãy A rồi kết thúc;
Bư6: Quay lại B3.
Bài toán 4: Cho dóy A g?m N s? nguyờn : a1, a2 ,., aN. Tớnh tớch cỏc ph?n t? l� s? ch?n trong dóy trờn

Bư2: i ? 1; P?1
Bư3: Nếu ai chia h?t cho 2 thì P?P*ai, rồi kết thúc;
Bư5: Nếu i > N thì thông báo P cỏc s? ch?n trong dãy A rồi kết thúc;
Thuật toán
Bài toán 4: Cho dóy A g?m N s? nguyờn : a1, a2 ,., aN. D?m cỏc ph?n t? l� s? ch?n trong dóy trờn

B1: Nhập N, các số hạng a1, a2,., aN

Bư2: i ? 1; d?0
Bư3: Nếu ai chia h?t cho 2 thì d?d+1, rồi kết thúc;
Bư4: i ? i+1;
Bư5: Nếu i > N thì thông báo t?ng S cỏc s? l? trong dãy A rồi kết thúc;
Bư6: Quay lại B3.
1. Khái niệm bài toán
Bài toán và thuật Toán
2. Khái niệm thuật toán
Thuật toán giải phưuơng trình bậc hai (a ?0).
Thuật toán tìm Max của một dãy số.
Thuật toán sắp xếp bằng tráo đổi.
Thuật toán tìm kiếm tuần tự
C?NG C?
BÀI TOÁN VÀ THUẬT TOÁN
DẶN DÒ
Học bài cũ trước khi đến lớp
Làm lại các bài tập
Ôn tập chuẩn bị ktra định kỳ
Tiết học đến đây là kết thúc.
Cảm ơn sự lắng nghe của các em!
Chúc các em học tốt!