CHÀO MỪNG CÁC THẦY CÔ
ĐẾN DỰ GIỜ!
Trả lời:
- Input: Số nguyên dương N
- Output: Kết luận “N là số nguyên tố” hoặc “N không là số nguyên tố”
- Ý tưởng:
+ Nếu N= 1 thì N không là số nguyên tố
+ Nếu 1< N< 4 thì N là số nguyên tố
+ Nếu n>4 và không có ước số trong phạm vi từ 2 đến
thì N là số nguyên tố
Bài 4. BÀI TOÁN VÀ THUẬT TOÁN
(Tiết 3)
Kiểm tra bài cũ
Câu hỏi: Xác định Input, Output, ý tưởng của bài toán “Kiểm tra tính nguyên tố của một số nguyên dương”?

Nhận xét gì
về đối tượng
sau khi thay đổi
so với
đối tượng
gốc?
Làm sao máy tính
sắp xếp được
như chúng ta?
Cần nạp chương trình
sắp xếp vào máy
Xây dựng
thuật toán sắp xếp
Xét bài toán sắp xếp sau
Cho dãy A gồm n số nguyên a1, a2,..., an.
Cần sắp xếp các số hạng để dãy A trở thành dãy không giảm (tức là số hạng trước không lớn hơn số hạng sau)
Ví dụ: Dãy A gồm 6 số nguyên: 6, 5, 7, 1, 7, 2
Sau khi sắp xếp ta được dãy không giảm:
1, 2, 5, 6, 7, 7
THUẬT TOÁN SẮP XẾP BẰNG TRÁO ĐỔI
Xác định bài toán:

- Input:
- Output:
Dãy A gồm N số nguyên a1, a2,…, aN.
Dãy A được sắp xếp thành dãy không giảm.
 Với N = 6 và dãy A gồm 6 số hạng như sau :
 Lượt thứ 1
 Lượt thứ 2
 Lượt thứ 3
 Lượt thứ 4
 Lượt thứ 5:
Nhận xét về
cách sắp xếp trên?
 Lượt thứ 6:
NHẬN XÉT
Duyệt từ trái → phải, nếu ai>ai+1 thì đổi chỗ ai và ai+1

Sau mỗi lần đổi chỗ, phần tử lớn nhất sẽ chuyển dần
về cuối dãy

Sau 1 lần duyệt phần tử lớn nhất sẽ nằm cuối dãy

Việc đó được lặp đi lặp lại cho đến khi mọi phần tử
trong dãy được sắp xếp thành dãy không giảm
THUẬT TOÁN SẮP XẾP BẰNG TRÁO ĐỔI
Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau ta đổi vị trí chúng cho nhau. Việc đó được lặp lại cho đến khi không có sự đổi chỗ nào xảy ra nữa.
Ý tưởng:

Ý tưởng?
Ghi chú
Dùng biến i để thực hiện việc so sánh các phần tử kề
nhau từ trái  phải, nếu ai>ai+1 thì đổi chỗ ai và ai+1;
tăng i lên để so sánh với phần tử tiếp theo
Dùng biến M để kiểm tra quá trình sắp xếp; ban đầu
M= N, khi i> M thì kết thúc 1 lần duyệt; sau mỗi lần
duyệt thì số phần tử chưa sắp xếp giảm đi 1 (tức M
giảm 1)

Khi M= 1(chỉ còn 1 phần tử chưa sắp xếp), đưa ra dãy
đã sắp xếp rồi kết thúc
THUẬT TOÁN
a. Cách liệt kê
B1: Nhập N, các số hạng a1, a2,…, aN;
B2: M  N;
B3: Nếu M < 2 thì đưa ra dãy A đã được sắp xếp rồi kết thúc;
B4: M  M – 1; i  0;
B5: i  i +1;
B6: Nếu i > M thì quay lại B3;
B7: Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau;
B8: Quay lại B5.
Chỉ ra tính dừng
của thuật toán?
THUẬT TOÁN
Nhập N và
a1, a2,..., aN
M  N
M < 2 ?
M  M - 1; i 0
i  i + 1
i > M ?
ai > ai+1 ?
Tráo đổi
ai và ai+1
Đưa ra A đã sắp xếp
rồi kết thúc
Đ
Đ
Đ
S
S
S
b. Cách sơ đồ khối
CỦNG CỐ, LUYỆN TẬP
BT 1. Có danh sách các tên sau:
BÌNH, AN, GIANG, DUNG, CÚC
Hãy sắp xếp các tên trên thành dãy không giảm?
Hỏi: Sau lần duyệt thứ nhất, danh sách là:

A. AN, BÌNH, GIANG, DUNG, CÚC
B. AN, BÌNH, DUNG, GIANG, CÚC
C. AN, BÌNH, DUNG, CÚC, GIANG
D. AN, BÌNH, CÚC, DUNG, GIANG
i= 2, 3
M= 4, i= 1
i= 4
i= 5
BÀI TẬP VỀ NHÀ
- Bài 6 trang 44 trong SGK
- Bài 1.41 câu d trong SBT
CẢM ƠN CÁC THẦY CÔ CÙNG CÁC EM
ĐÃ LẮNG NGHE!