CHÀO MỪNG QUÍ THẦY CÔ TRONG HỘI ĐỒNG SƯ PHẠM NHÀ TRƯỜNG
Đơn Dương, ngày 19 tháng 9 năm 2008
Kiểm tra bài cũ:
Câu 1: Bài toán kiểm tra tính nguyên tố của
một số nguyên dương N.
a/ Hãy xác định bài toán?
b/ Hãy viết thuật toán liệt kê?
Bài 4: Bài toàn và thuật toán (tt)
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.
3. 4 Thuật toán tìm kiếm tuần tự
(Sequential Search)
a/ Xác định bài toán:

Input: Dãy A gồm N số nguyên a1, a2,., aN và
khoỏ k.
b/ Ý t­ëng:
Tỡm ki?m tu?n t? du?c th?c hi?n m?t cỏch t? nhiờn, lần lượt từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khoá (k) cho đến khi g?p m?t s? h?ng b?ng k, nếu đã xét tới số hạng cuối cùng mà không có giỏ tr? n�o b?ng k thì có nghĩa là dãy A không có số hạng nào có giá trị bằng k.
c/ Thuật toán:
Bước 1: Nhập N, các số hạng a1, a2,., aN
và giá trị khoá k;
Bước 2: i ? 1
Bước 3: Nếu ai = k thì thông báo chỉ số i , End
Bước 4: i ? i+1;
Bước 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, End;
Bước 6: Quay lại B3.
* Thuật toán liệt kê:
Nhập N, cỏc s? h?ng a1, a2,.., aN và khoỏ k c?n tỡm
i ? 1
ai = k ?
Đưa ra i v� ai=k
rồi End
Đ
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, End
S
5
4
3
2
1
i
51
25
11
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 10 số hạng như sau:
Tại vị trí i = 5 có a5 = 2 = k
? Với k = 6 và dãy A gồm 10 số hạng như sau:
Với mọi i từ 1? 10 không có a i có giá trị bằng 6
5
1
2
3
4
5
6
7
8
9
10
11
Bài 4: Bài toàn và thuật toán (tt)
3. 5 Thuật toán giải phương trình bậc hai
ax2 + bx + c = 0 (a ? 0)
a/ Xác định bài toán
3. 5 Thuật toán giải phương trình bậc hai
ax2 + bx + c = 0 (a ? 0)
- PT Vô nghiệm
Output:
Input: các số thực a, b, c (a≠0)
- PT Có 1 nghiệm x=-b/2a
- PT Có 2 nghiệm phân biệt
x1, x2= (-b  )/2a


b/ Ý tưởng
3. 5 Thuật toán giải phương trình bậc hai
ax2 + bx + c = 0 (a ? 0)
- Lập Δ = b2 – 4ac
- Nếu  < 0 => PT vô nghiệm, end;
- Nếu  = 0 => PT có nghiệm kép x= -b/2a, end;
- Nếu  > 0 =>PT có 2 nghiệm x1,x2= (-b  )/2a
end;
B6: Kết thúc
B1: Nhập các số thực a, b, c (a  0)
B2: Lập  = b2 – 4ac
B3: Nếu  < 0 => PT vô nghiệm => B6
B4: Nếu  = 0 => PT có nghiệm x = -b/2a => B6
B5: PT có hai nghiệm

x1, x2 = (-b  )/2a => B6
c Thuật toán:
* Thuật toán bằng liệt kê:
Đ
s
* Thu?t toỏn b?ng so d? kh?i:
B1
B2
B3
B4
B5
s
Đ
B6
 = b2 – 4ac
PT Vô nghiệm
a, b, c = 1, 3, 5
D = 3*3 - 4*5*1 = - 11
-11 < 0
PT vô nghiệm

KT
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 phươ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
KT
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 phươ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

PT có nghiệm x = -b/2a
KT
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 phương trình bậc hai
B? TEST 3:
Đ
 = 0
PT có nghiệm x1 = 3
x2 = 2
Bài tập:
Bài 1: Cho dãy các thao tác sau:
Bước 1: Xoá bảng
Bước 2: Vẽ đường tròn
Bước 3: Quay lại bước 1
Có phải là thuật toán không? Vì sao?
Các bước trên không phải là thuật toán vì:
- Không xác định rõ đâu là input đâu là output
- Các bước trên là một vòng lặp vô hạng, không có tính dừng.
Bài toán và thuật toán
a/ Xác định bài toán

b/ Ý tưởng

c/ Thuật toán
Thuật toán liệt kê
Thuật toán bằng sơ đồ
khối
Bài 2: Hãy chỉ ra tính dừng của thuật toán
tìm kiếm tuần tự?
Thuật toán tìm kiếm tuần tự dừng khi
- Đã tìm thấy ai=k hoặc
- i >N đã kiểm tra hết các phần tử trong dãy mà vẫn không có giá trị bằng k.
Chào tạm biệt quí thầy cô

Hẹn gặp lại
see you again!