Tin học 10
Nhiệt liệt chào mừng quý thầy cô về dự giờ thăm lớp 10A1
Kiểm tra bài cũ
Câu 1. Nêu khái niệm thuật toán. Có những cách biểu diễn thuật toán nào?
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 đượ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 được Output cần tìm.
Có 2 cách biểu diễn cơ bản: liệt kê và sơ đồ khối
Câu 2. Xác định Input và Output của bài toán: Tìm giá trị nhỏ nhất của dãy số nguyên N
Input: Số nguyên dương N và dãy N số nguyên a1, …, aN
Output: Giá trị nhỏ nhất Min của dãy số
Kiểm tra bài cũ
Bài 4. BÀI TOÁN VÀ THUẬT TOÁN (TT)
1.Khái niệm bài toán.
2.Khái niệm thuật toán.
3.Một số ví dụ về thuật toán.
Ví dụ 2 : Bài toán sắp xếp: Sắp xếp bằng tráo đổi (Exchange Sort)
3. Một số ví dụ về thuật toán (tt)
Ví dụ 2 : Bài toán sắp xếp: Sắp xếp bằng tráo đổi (Exchange Sort)
Hình a
Hình b
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.
Sắp xếp bằng tráo đổi
Biểu diễn thuật toán
theo 2 cách :
Liệt kê
Sơ đồ khối
Ý tưởng
Xác định
bài toán
Bước 1
Bước 2
Bước 3
1. Xác định bài toán
Input?
Output?
Input: Dãy A gồm N số nguyên
a1, a2, a3,…,aN ( N>0)
Output: Dãy A được sắp xếp lại thành dãy không giảm.
Dãy ban đầu
Dãy sau khi sắp xếp
Lượt thứ nhất
Lượt thứ hai
Lượt thứ ba
Lượt thứ tư
Lượt thứ năm
2. Ý tưởng
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 chỗ 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 .
2. Ý tưởng

NHẬN XÉT
Sau mỗi lần đổi chỗ, giá trị lớn nhất sẽ chuyển dần về cuối
Sau mỗi lượt có ít nhất một số hạng xếp đúng và không tham gia vào quá trình đổi chỗ nữa
Bước 1: Nhập N, các số hạng a1, a2, a3,…,aN ( N>0)
Bước 2: M  N;
Bước 3: Nếu M < 2 thì đưa ra dãy A đã được sắp xếp rồi kết thúc;
Bước 4: M  M – 1, i  0;
Bước 5: i  i + 1;
Bước 6: Nếu i > M thì quay lại bước 3;
Bước 7: Nếu ai> ai+1 thì đổi chỗ ai và ai+1;
Bước 8: Quay lại bước 5.
3. Biểu diễn thuật toán
a) Cách liệt kê
Nhập N và a1, a2,…aN
MN
M<2?
Đưa ra A rồi kết thúc
MM-1; i 0
ii+1
i>M?
ai>ai+1?
Tráo đổi ai và ai+1
M giảm dần sau mỗi lượt. Sau mỗi lượt có 1 phần tử không tham gia so sánh
Ngừng khi chỉ còn 1 phần tử tham gia vào quá trình
M là số phần tử tham gia so sánh trong lượt
Đ
Đ
S
Đ
S
S
b) Sơ đồ khối
Nhập N và a1, a2,…aN
MN
M<2?
Đưa ra A rồi kết thúc
MM-1;i 0
ii+1
i>M?
ai>ai+1?
Tráo đổi ai và ai+1
6
3
4
2
5
a1 a2 a3 a4 a5
N=5
M=5
i=0
M=4
i=1
i=2
i=3
i=4
M=3
i=5
M=2
M=1
Đ
S
Đ
S
S
Đ
Củng cố
So sánh thuật toán exchange sort và thuật toán selection sort
Bài học kết thúc
Thân chào quý thầy cô và các em
Bài tập tương tự và gợi ý
Quan sát mô phỏng trong việc hình thành ý tưởng sắp xếp mới từ sự kết hợp thuật toán tìm số lớn nhất và thuật toán sắp xếp bằng cách tráo đổi vừa học. Em hãy liệt kê các bước hoặc vẽ sơ đồ khối cho ý tưởng thuật toán này
Ý tưởng :
Mỗi lượt tìm phần tử lớn nhất trong số các phần tử chưa sắp xếp. Đổi chỗ phần tử này với phần tử cuối dãy (phần chưa sắp xếp)
Việc này lặp lại nhiều lượt, cho đến khi dãy
chỉ còn duy nhất 1 phần tử chưa sắp xếp.
Mô phỏng thuật toán
Dãy ban đầu
Dãy sau khi sắp xếp
Max =
2
4
8
5
7