SKKN Sử dụng đồ dùng dạy học diễn tả các thuật toán trong bài: bài toán và thuật toán - Tin học 10 bằng sơ đồ khối

MỤC LỤC
A.	Mở đầu	1
I.	Lý do chọn đề tài	1
II.	Mục đích nghiên cứu	1
III.	Đối tượng nghiên cứu	1
VI.	Phương pháp nghiên cứu..	1
B.	Nội dung sáng kiến kinh nghiệm	2
I.	Khái niệm bài toán...........................................................................................2
II. 	Khái niệm thuật toán........................................................................................4
III. Một số ví dụ về thuật toán ...............................................................................8
IV. Bài tập...............................................................................16
C. 	Phần kết luận..........................................................................................18A. MỞ ĐẦU
I. LÝ DO CHỌN ĐỀ TÀI
Cho bài toán (Input và Output) việc đưa ra ý tưởng để giải bài toán là việc không dễ. Nhưng khi đã có ý tưởng biến ý tưởng đó thành thuật toán để giải một bài toán trên máy tính là một việc khó hơn. Công việc này yêu cầu học sinh phải thuần thục trong việc diễn tả thuật toán khi đã có ý tưởng. Nhưng do số tiết tin học lớp 10 là 2 tiết/ 1 tuần (90 phút), để học sinh thuần thục là điều không thể. Các thuật toán đưa ra trong Bài 4: Bài toán và thuật toán học sinh đa số lĩnh hội bằng cách học thuộc lòng thuật toán, một vài học sinh khá giỏi có thể bắt chước các thuật toán đã có để diễn tả thuật toán khác nhưng rất mơ hồ về điều kiện nếu.. thì.. và lặp.
Trường THPT Thạch Thành 3 là trường miền núi, mặt bằng học sinh thấp, vì vậy tôi xin trình bày sáng kiến kinh nghiệm “SỬ DỤNG ĐỒ DÙNG DẠY HỌC DIỄN TẢ CÁC THUẬT TOÁN TRONG BÀI: BÀI TOÁN VÀ THUẬT TOÁN-TIN HỌC 10 BẰNG SƠ ĐỒ KHỐI ” để giúp học sinh diễn tả được thuật toán.
II. MỤC ĐÍCH NGHIÊN CỨU
Xây dựng và mô tả được thuật toán bằng sơ đồ khối để giải bài toán giúp các em hiểu khi giải một bài toán trên máy tính thì phải làm như thế nào.
Khi lên lớp 11, học lập trình giải bài toán việc mô tả thuật toán bằng ngôn ngữ lập trình pascal là việc dễ thực hiện khi đã có thuật toán bằng sơ đồ khối. 
III. ĐỐI TƯỢNG NGHIÊN CỨU
Đa số học sinh chấp nhận hay thừa nhận các thuật toán sách giáo khoa đưa ra. Giáo viên yêu cầu học sinh học thuộc, sau đó kiểm tra yêu cầu học sinh viết lại thuật toán, cách học này là học thuộc lòng. Khi áp dụng để xây dựng một thuật toán khác học sinh chắp vá từ nhiều thuật toán, đôi khi không hiểu bản chất.
Tôi đề xuất một cách diễn tả thuật toán bằng sơ đồ khối sử dụng đồ dùng dạy học tự làm. Ban đầu chỉ cho học sinh chơi trò chơi lắp ghép sao cho đúng thuật toán đơn giản, các hình diễn tả thuật toán bằng sơ đồ khối ( hình thoi ¯, Hình chữ nhật , Hình Ô van ) đã có sẵn các biểu thức. Sau đó độ khó tăng dần bằng cách học sinh tự viết biểu thức vào các hình sau đó lắp ghép thành sơ đồ khối đúng thuật toán với bài toán đã cho. Tổ chức các tiết học bằng thảo luận nhóm. 
 IV. PHƯƠNG PHÁP NGHIÊN CỨU
Viết sáng kiến kinh nghiệm thường xuyên liên tục cũng là nhiệm vụ chính trị của mỗi giáo viên, nhưng cần phải lựa chọn phương pháp nghiên cứu đúng đắn và phù hợp với nhà trường trung học phổ thông. Sáng kiến kinh nghiệm đang trình bày của tôi dựa theo các luận cứ khoa học hướng đối tượng, cụ thể: thuyết trình, quan sát, điều tra khảo sát thực tế, phân tích kết quả thực nghiệm sư phạm, v.v phù hợp với bài học và môn học thuộc lĩnh vực Tin học. 
Nêu vấn đề và giải quyết vấn đề đi từ thực tế hiện thực khánh quan → cụ thể hóa → tổng quát hóa, trừu tượng hoá.
B. NỘI DUNG SÁNG KIẾN KINH NGHIỆM
I. KHÁI NIỆM BÀI TOÁN.
	Phần 1. Khái niệm bài toán trang 32-33 sách giáo khoa - tin học 10 (SGK Tin10) tôi đã thiết kế lại như sau: 
a. Khái niệm bài toán(SGK-Tin10): “ Trong phạm vi tin học, ta có thể quan niệm bài toán là một việc nào đó ta muốn máy tính thực hiện”
Khái niệm trên có một cụm từ khó hiểu: “bài toán là một việc nào đó”. Khi dạy cho học sinh tôi thường tách khái niệm trên thành 2 mức: mức 1: “bài toán là một việc nào đó”, mức 2: “bài toán là một việc nào đó ta muốn máy tính thực hiện”.
Mức 1: bài toán là một việc nào đó”: Để giải thích cho vế 1 tôi đã thực hiện như sau: 
Giáo viên hỏi(?): Trong chương trình cấp 2 một bài toán hình học được cấu tạo bởi các thành phần nào ?
Học sinh (HS): Gồm giả thiết và kết luận.
? Bài toán các môn Lý, hóa, đại số... có cấu tạo như vậy không ?
HS: Gồm giả thiết và kết luận.
? “một việc nào đó” thì có phải là bài toán không ? 
Ví dụ 1: Nêu các thao tác để thực hiện việc “nấu cơm” bằng bếp củi ?
HS:	Bước 1: Chuẩn bị: Nồi, gạo, củi, lửa, nước, bếp;
	Bước 2: Cho gạo, nước vào nồi, bắc lên bếp nấu cho đến khi cạn.
	Bước 3: Dập lửa, để than giữ nhiệt cho nồi cơm.
	Bước 4: Cơm chín.
? Việc “nấu cơm” thì có phải là bài toán không ? 
HS: Là bài toán vì giả thiết: Bước 1: Chuẩn bị: Nồi, gạo, củi, lửa, nước, bếp;
và kết luận: Bước 4: Cơm chín.
? Nêu một công việc mà không phải là bài toán ? khái niệm bài toán ?
HS: Không có, khái niệm bài toán: “bài toán là một việc nào đó”
Mức 2: “bài toán là một việc nào đó ta muốn máy tính thực hiện”.
? Khái niệm bài toán và bài toán trong tin học có gì khác nhau ? Khái niệm bài toán trong tin học ?
HS: Bài toán trong tin học là máy tính thực hiện. Khái niệm: “ Trong phạm vi tin học, ta có thể quan niệm bài toán là một việc nào đó ta muốn máy tính thực hiện”.
b. Input, Output:
Sách giáo khoa viết “Khi dùng máy tính giải bài toán, ta cần quan tâm đến hai yếu tố: “ Đưa vào máy tính thông tin gì (input) và cần lấy ra thông tin gì (output) ” 
Nói như vậy thì hơi trừu tượng, nên cụ thể hóa như sau:
Ví dụ 2: Tìm nghiệm phương trình bậc 2: x2-3x - 10 = 0. (1) 
 ? Giả thiết, kết luận, hãy thực hiện công việc trên bằng máy tính cầm tay ?
	HS: Giả thiết: a=1,b= -3,c= -10; Kết luận: x=5, x= -2; 
 ? Em đã thực hiện như thế nào ? máy tính cho kết quả ở đâu ?
	HS: - Nhập các số a=1,b= -3,c= -10 vào máy tính, 
 - Máy tính đưa kết quả ra màn hình x=5, x= -2.
	Có thể nói rằng khi giải bài toán trên máy tính: giả thiết ~ đưa vào (input), kết luận ~ lấy ra (output), từ ví dụ 2 học sinh có thể hiểu input: Các thông tin đưa vào máy tính, Output: “đưa ra kết quả ” hay “thông báo kết quả” ra màn hình máy tính, đó là “Output: các thông tin cần tìm từ input”. Công việc này tuy cảm thấy đơn giản nhưng giải quyết 1 vấn đề lớn: khi giải bài toán trên máy tính thì làm gì ?
Ta có thể phát biểu bài toán (1) tổng quát như sau:
Ví dụ 3: Tìm nghiệm phương trình bậc 2: ax2+bx + c = 0 ( a0)
Input: Các số thực a,b,c (a0). ( đưa vào máy tính a,b,c)
Output: Tất cả các số thực x thỏa mãn ax2+bx + c = 0 hoặc không có số thực nào thão mãn. (đưa ra nghiệm của phương trình ra màn hình hoặc đưa ra thông báo phương trình vô nghiệm ra màn hình )
Sau khi hiểu được Input và Output học sinh có thể hiểu tại sao trong các thuật toán sách giáo khoa có các thao tác input: “nhập..”, output: “đưa ra.. ” hay “thông báo..” và khi lên lớp 10 học sinh hiểu là: “đưa ra.. ” hay “thông báo..” ra màn hình máy tính.
II. KHÁI NIỆM BÀI TOÁN.
a. Khái niệm:
Xét ví dụ 1: Thao tác để thực hiện bài toán “nấu cơm” bằng bếp củi:
	Bước 1: Chuẩn bị: Nồi, gạo, củi, lửa, nước, bếp;
	Bước 2: Cho gạo, nước vào nồi, bắc lên bếp nấu cho đến khi cạn.
	Bước 3: Dập lửa, để than giữ nhiệt cho nồi cơm.
	Bước 4: Cơm chín.
? Các thao tác trên là vô hạn ( số bước(thao tác) không xác định) hay hữu hạn (số bước(thao tác) xác định) ?
HS: Số bước(thao tác) hữu hạn (cụ thể : 4 bước ).
? Bước 2 tráo đổi cho bước 3 được không ?
HS: Không được.
? Sau khi thực hiện dãy thao tác từ bước 1 đến bước 3 được bước 4 mà cơm bị cháy đen thì các theo tác trên có được coi là đúng đắn không ?
HS: Không phải là dãy thao tác đúng đắn.
Từ bước 1 đến bước 4 là “cách” (phương pháp) để nấu cơm, trong tin học người ta gọi là “thuật toán”
? Nêu khái niệm thuật toán?
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.
b. Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên.
Input : Số nguyên dương N và dãy N số nguyên a1,a2,,aN.
Output: Giá trị lớn nhất Max của dãy.
? Nêu ý tưởng thuật toán ?
Để làm ví dụ này học sinh hay có những thắc mắc: các số a1,a2,,aN thầy phải cho cụ thể thì các em mới đưa ra được thuật toán, hay nói cách khác đa số học sinh hay thực hiện với các số cụ thể. Một vài giáo viên giải thích đây là dạng bài toán biện luận thì học sinh cũng chưa gặp các dạng này. Khi dạy phần này tôi thường đưa ra bài toán thực tế:
Ví dụ 1: Hãy tìm ra người nặng nhất của N=38 học sinh lớp 10C5, biết rằng có một cái bục max để cho 1 người nặng nhất trong những người đã được cân đứng lên đó, có một chiếc cân, mỗi người chỉ được cân 1 lần, sau khi cân song người cuối tìm được người nặng nhất. Nêu cách thực hiện ( ý tưởng ).
HS: 
- Cân người thứ nhất được a1 kg, vì là người đầu tiên được cân nên cho đứng tạm lên bục Max hay Max ← a1; 
- Cân người thứ hai được a2 kg, so sánh số cân a2 với cân của người đang đứng trên bục Max nếu a2> Max thì đưa người có số cân a2 lên bục Max, Max ← a2
- Cân người thứ ba được a3 kg, nếu a3> Max thì đưa người có số cân a3 lên bục Max hay Max ← a3
- Cân người thứ n được an kg, nếu an> Max thì đưa người có số cân an lên bục Max hay Max ← an.
Sau khi cân đến người thứ cuối ta được 1 người nặng nhất trên bục Max.
Ví dụ 2: Tìm giá trị lớn nhất của một dãy số nguyên.
Input : Số nguyên dương N và dãy N số nguyên a1,a2,,aN.
Output: Giá trị lớn nhất Max của dãy.
? Nêu ý tưởng thuật toán ?
	HS: - Khởi tạo giá trị Max ← a1;
- Lần lượt với i từ 2 đến N, so sánh giá trị số hạng ai với giá trị Max, nếu ai > Max thì Max nhận giá trị mới là ai.
? Thuật toán ?
Ngoài cách liệt kê dãy các thao tác, thuật toán có thể diễn tả bằng sơ đồ khối. Trong sơ đồ khối, người ta sử dụng một số khối, đường có mũi tên với:
Hình thoi ¯ thể hiện thao tác so sánh; 
Hình chữ nhật thể hiện các phép tính toán.
Hình Ô van thể hiện các thao tác nhập, xuất dữ liệu.
Các mũi tên → quy định trình tự thực hiện hiện các thao tác
Mô tả đồ dùng dạy học dùng để diễn tả thuật toán bằng sơ đồ khối: Tạo ra các hình 
 ¯, , , →,|, Đúng, Sai vật liệu là nhựa mê ca trắng, một mặt dính thêm nam châm để có thể dính lên bảng từ, mặt còn lại để viết thao tác, phép tính toán. 
 Phân lớp thành 4 nhóm(1,2,3,4) thảo luận nhóm, phát cho mỗi nhóm các hình và mũi tên, trên đó đã có sẵn các thao tác và phép tính toán ( biểu thức ). Yêu cầu học sinh không sử dụng sách giáo khoa hãy sắp xếp các hình để được thuật toán:
Các hình phát cho một nhóm học sinh:
Nhập N và dãy a1,..., aN
Max ¬ ai
i > N ?
Max ¬ a1, i ¬ 2
Đưa ra Max 
 rồi kết thúc
i ¬ i + 1
 Sai
 Sai
 Đúng
 Đúng
ai >max?
Đúng
Đúng
Sai
Nhập N và dãy a1,..., aN
Max ¬ ai
ai >Max?
i > N ?
Max ¬ a1, i ¬ 2
Đưa ra Max 
 rồi kết thúc
i ¬ i + 1
Sai
Hình1: Sản phẩm của HS
Giáo viên(GV): yêu cầu học sinh thảo luận nhóm, hình thức thảo luận lắp ghép để được thuật toán tìm Max, học sinh lắp ghép lên bàn học của nhóm mình.
HS: Thảo luận, lắp ghép. 
GV: Gọi 2 nhóm (1;3), mỗi nhóm 2 học sinh lên bảng lắp ghép sơ đồ khối thuật toán, trình bày thuật toán, nhóm nào nhanh và đúng sẽ được điểm.
HS: Lắp ghép sơ đồ khối thuật toán. 
GV: Yêu cầu các học sinh nhóm 2; nhóm 4 nhận xét sản phẩm của 2 nhóm đã ghép trên bảng.
GV: Phát bộ đồ dùng học tập cho các nhóm, học sinh thảo luận nhóm (4 nhóm): Cho Test 01: N=8, a1= 5, a2 = 1, a3 = 4, a4 = 7, a5 = 6, a6 = 12, a7=15, a8=10. Hãy thay số (viết vào đồ dùng học tập) và thực hiện Test trên sơ đồ khối ? 
	 Ghi chú: - Đồ dùng học tập gồm nhiều bộ, mỗi bộ có nhiều hình. 
	- Các hình này trắng, chưa được viết chữ lên.
	HS: Thảo luận nhóm, nhóm nào song trước sẽ được lên trình bày lấy điểm.
GV: Gọi một nhóm gồm 3 học sinh lên bảng lắp ghép sơ đồ khối thuật toán, trình bày việc thực hiện thuật toán theo Test 01.
HS: Lắp ghép, trình bày. Các nhóm còn lại nhận xét.
Sai
 N=8 và dãy a1=5,a2=1, a3=4 , a4=7, a5=6, a6=12,a7=15, a8=10 
 6 > 7 ?
5 > 8 ?
Max ¬ 5 (a1), i ¬ 2
i ¬ 5 + 1=6
Sai
Sai
 N=8 và dãy a1=5,a2=1, a3=4 , a4=7, a5=6, a6=12,a7=15, a8=10 
 7 > 5 ?
4 > 8 ?
Max ¬ 5 (a1), i ¬ 2
i ¬ 4 + 1= 5
Đúng
Max ¬ 7 (a4)
Sai
 N=8 và dãy a1=5,a2=1, a3=4 , a4=7, a5=6, a6=12,a7=15, a8=10 
 4 > 5 ?
3 > 8 ?
Max ¬ 5 (a1), i ¬ 2
i ¬ 3 + 1=4
Sai
Sai
 N=8 và dãy a1=5,a2=1, a3=4 , a4=7, a5=6, a6=12,a7=15, a8=10 
 1 > 5 ?
2 > 8 ?
Max ¬ 5 (a1), i ¬ 2
i ¬ 2 + 1=3
Sai
Đúng
Đưa ra Max=15 
 rồi kết thúc
9 > 8 ?
Max ¬ 5(a1), i ¬ 2
 N=8 và dãy a1=5,a2=1, a3=4 , a4=7, a5=6, a6=12,a7=15, a8=10 
Sai
 N=8 và dãy a1=5,a2=1, a3=4 , a4=7, a5=6, a6=12,a7=15, a8=10 
 10 > 15 ?
8 > 8 ?
Max ¬ 5 (a1), i ¬ 2
i ¬ 8 + 1=9
Sai
Sai
 N=8 và dãy a1=5,a2=1, a3=4 , a4=7, a5=6, a6=12,a7=15, a8=10 
 15 > 12 ?
7 > 8 ?
Max ¬ 5 (a1), i ¬ 2
i ¬ 7 + 1= 8
Đúng
Max ¬ 15 (a7)
Sai
 N=8 và dãy a1=5,a2=1, a3=4 , a4=7, a5=6, a6=12,a7=15, a8=10 
 12 > 7 ?
6 > 8 ?
Max ¬ 5 (a1), i ¬ 2
i ¬ 6 + 1= 7
Đúng
Max ¬ 12 (a6)
 Hình 2: Sản phẩm của học sinh
Đúng
Đúng
Sai
Nhập N và dãy a1,..., aN
Min ¬ ai
ai <Min?
i > N ?
Min ¬ a1, i ¬ 2
Đưa ra Min 
 rồi kết thúc
i ¬ i + 1
Sai
Hình 3: Sản phẩm của HS
	GV: Hãy viết các thao tác và phép tính toán (biểu thức) vào các hình, lắp ghép thành sơ đồ khối thuật toán tìm số nhỏ nhất Min của 1 dãy số nguyên.
	HS: Viết vào hình, lắp ghép.
GV: Về nhà học sinh chạy thử thuật toán tìm số nhỏ nhất Min với Test 01: N=8, a1= 5, a2 = 1, a3 = 4, a4 = 7, a5 = 6, a6 = 12, a7=15, a8=10, thay số (viết vào đồ dùng học tập) và thực hiện Test trên sơ đồ khối ?
III. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN. 
Ví dụ 1: Bài toán sắp xếp.
	Thuật toán sắp xếp bằng tráo đổi ( Exchange Sort).
. Xác định bài toán:
	Input : Dãy A gồm N số nguyên a1,a2,,aN 
	Output: Dãy A được sắp xếp lại thành dãy không giảm.
. Ý 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 nữa.
Học sinh và kể cả giáo viên có thể hiểu ý tưởng, nhưng khi dạy thì thừa nhận ý tưởng. Theo tôi nên cùng học sinh xây dựng ý tưởng cho sát hơn với thuật toán.
. Ý tưởng: (xây dựng lại ) 
+ Với N=1 dãy A chỉ có 1 số
 VD: a1= 5 → dãy đã được sắp xếp
+ Với N=2 dãy A có 2 số 
 VD: a1= 5 a2= 6 vì a1<a2 → dãy đã được sắp xếp.
 a1= 8 a2= 6 vì a1>a2 → tráo đổi a1 và a2 cho nhau: a1= 6 a2= 8. 
+ Với N=3 dãy A có 3 số 
 VD:	a1= 16 a2= 5 a3= 8 
 vì a1>a2 → Tráo đổi giá trị a1 =16 và a2 =5 cho nhau.
	 a1= 5 a2= 16 a3= 8
 vì a2>a3 → Tráo đổi giá trị a2 =16 và a3 =8 cho nhau.
	a1= 5 a2= 8 a3= 16 → dãy đã được sắp xếp.(nên lờ đi a1< a2 )
	Khi duyệt từ đầu dãy đến cuối dãy ta gọi là 1 lần duyệt, với ví dụ trên ta thấy sau lần duyệt 1 số lớn nhất 16 được đưa về cuối dãy. 
+ Với N>3:
	Ta so sánh từng cặp (a1,a2), (a2,a3), (a3,a4),..., (ai,ai+1),, (aN-1,aN), nếu ai>ai+1 thì tráo đổi giá trị ai và ai+1 cho nhau. 
Việc đó được lặp lại, cho đến khi không có sự tráo đổi nào xảy ra nữa, sau lần duyệt số lớn nhất đưa về cuối dãy, sau lần duyệt 2 giá trị lớn thứ 2 được xếp ở vị trí sát cuối,..vvThực hiện sắp xếp với dãy bỏ số hạng cuối hay các số hạng cần sắp xếp giảm đi 1đơn vị. Khi dãy còn 1 số hạng cần sắp thì dãy đã được sắp xếp.
. Thuật toán: 
 Phân lớp thành 4 nhóm(1,2,3,4) thảo luận nhóm, phát cho mỗi nhóm các hình và mũi tên, trên đó đã có sẵn các thao tác và phép tính toán ( biểu thức ). Yêu cầu học sinh không sử dụng sách giáo khoa hãy sắp xếp các hình để được thuật toán:
Các hình phát cho một nhóm học sinh: Để làm nhiễu, tăng độ khó quá trình lắp ghép các hình được phát không phải của 1 thuật toán mà nhiều thuật toán.
Nhập N và dãy a1,..., aN
Max ¬ ai
i > N ?
Max ¬ a1, i ¬ 2
Đưa ra Max 
 rồi kết thúc
i ¬ i + 1
 Sai
 Sai
 Đúng
 Đúng
ai >max?
Nhập N, dãy a1, a2,, aN
Đưa ra A rồi kết thúc
M ¬ N
i ¬ i +1
M < 2
M ¬ M - 1 ; i ¬ 0
 Sai
 Sai
 Sai
 Đúng
 Đúng
 Đúng
i > M ?
ai >ai+1 ?
Tráo đối ai, ai+1
Hình 4: Sản phẩm của HS
Nhập N, dãy a1, a2,, aN
M ¬ N
M < 2
Tráo đổi ai và ai+1
i ¬ i +1
i > M ?
ai >ai+1 ?
Đúng
Sai
M ¬ M - 1 ; i ¬ 0
Sai
Sai
Đúng
Đúng
Đưa ra dãyA rồi kết thúc
Giáo viên(GV): yêu cầu học sinh thảo luận nhóm, hình thức thảo luận lắp ghép để được thuật toán sắp xếp bằng tráo đổi, học sinh lắp ghép lên bàn học của nhóm mình.
HS: Thảo luận, lắp ghép. 
GV: Gọi 2 nhóm (2;4), mỗi nhóm 2 học sinh lên bảng lắp ghép sơ đồ khối thuật toán, trình bày thuật toán, nhóm nào nhanh và đúng sẽ được điểm.
HS: Lắp ghép sơ đồ khối 
GV: Yêu cầu các học sinh nhóm 1, nhóm 3 nhận xét sản phẩm của 2 nhóm đã ghép trên bảng.
HS: Nhận xét
	Nếu theo ý tưởng thuật toán trong sách giáo khoa thì có những vấn đề học sinh phải không thấy rõ một số lập luận, biểu thức và phép toán trong thuật toán:
	- Không có tính tuần tự: "Với mỗi cặp số hạng đứng liền kề trong dãy" đã được thay "Ta so sánh từng cặp (a1,a2), (a2,a3), (a3,a4),..., (ai,ai+1),, (aN-1,aN)".
	- Tại sao lại: M ¬ M - 1. Cứ duyệt từ đầu dãy đến cuối dãy ta gọi là 1 lần duyệt, với ví dụ trên ta thấy sau lần duyệt 1 số lớn nhất 16 được đưa về cuối dãy.
- M<2 đưa ra dãy A rồi kết thúc: Với N=1 (M=1<2) dãy A chỉ có 1 số 
 VD: a1= 5 → dãy đã được sắp xếp
GV: Phát bộ đồ dùng học tập cho các nhóm, học sinh thảo luận nhóm (4 nhóm): Cho Test 01: N=4, a1= 5, a2 = 1, a3 = 6, a4 = 4. Hãy thay số (viết vào đồ dùng học tập) và thực hiện Test trên sơ đồ khối thuật toán sắp xếp bằng tráo đổi? 
N=4 và dãy a1=5,a2=1, a3=6 , a4=4
M ¬ 4
M=4 < 2
i ¬ 1 +1=2
2 > 3 ?
a2=5>a3=6
Sai
M ¬ 4 - 1=3 ; i ¬ 0
Sai
Sai
N=4 và dãy a1=5,a2=1, a3=6 , a4=4
M ¬ 4
M=4 < 2
Tráo đổi a1 và a2
i ¬ 0+1=1
1 > 3 ?
a1=5 >a2=1 ?
Sai
M ¬ 4 - 1=3 ; i ¬ 0
Sai
Đúng
HS: Thảo luận nhóm, nhóm nào song trước sẽ được lên trình bày lấy điểm.
Dãy sau tráo đổi a1=1,a2=5, a3=6 , a4=4
N=4 và dãy a1=5,a2=1, a3=6 , a4=4
M ¬ 4
M=4 < 2
 i ¬3 +1=4
4 > 3 ?
Sai
M ¬ 4 - 1=3 ; i ¬ 0
Đúng
N=4 và dãy a1=5,a2=1, a3=6 , a4=4
M ¬ 4
M=4 < 2
Tráo đổi a3 và a4
i ¬ 2+1=3
3 > 3 ?
a3=6 >a4=4 ?
Sai
M ¬ 4 - 1=3 ; i ¬ 0
Sai
Đúng
Dãy sau tráo đổi a1=1,a2=5, a3=4 , a4=6
Dãy sau lần duyệt 1: a1=1,a2=5, a3=4 , a4=6
N=4 và dãy a1=5,a2=1, a3=6 , a4=4
M ¬ 4
M=3 < 2
i ¬ 0 +1=1
1 > 2 ?
a1=1>a2=5
Sai
M ¬ 3 - 1=2 ; i ¬ 0
Sai
Sai
N=4 và dãy a1=5,a2=1, a3=6 , a4=4
M ¬ 4
M=3 < 2
Tráo đổi a2 và a3
i ¬ 1+1=2
2 > 2 ?
a2=5 >a3=4 ?
Sai
M ¬ 3 - 1=2 ; i ¬ 0
Sai
Đúng
Dãy sau tráo đổi a1=1,a2=4, a3=5 , a4=6
N=4 và dãy a1=5,a2=1, a3=6 , a4=4
M ¬ 4
M=2 < 2
i ¬ 0 +1=1
1 > 1 ?
a1=1>a2=4
Sai
M ¬ 2 - 1=1 ; i ¬ 0
Sai
Sai
N=4 và dãy a1=5,a2=1, a3=6 , a4=4
M ¬ 4
M=3 < 2
 i ¬2 +1=3
3 > 2 ?
Sai
M ¬ 3 - 1=2 ; i ¬ 0
Đúng
Dãy sau lần duyệt 2: a1=1,a2=4, a3=5 , a4=6
Nhập N, dãy a1, a2,, aN
M ¬ 4
M=1< 2
Đúng
Dãy : a1=1,a2=4, a3=5 , a4=6
N=4 và dãy a1=5,a2=1, a3=6 , a4=4
M ¬ 4
M=2 < 2
 i ¬1 +1=2
2 > 1 ?
Sai
M ¬ 2 - 1=1 ; i ¬ 0
Đúng
Dãy sau lần duyệt 3: a1=1,a2=4, a3=5 , a4=6
Hình 5: Sản phẩm của HS
GV: Hãy viết các thao tác và phép tính toán (biểu thức) vào các hình, lắp ghép thành sơ đồ khối thuật toán sắp xếp lại thành dãy "không tăng" của dãy A gồm N số nguyên a1,a2,,aN. Phát đồ dùng học tập cho học sinh.
HS: Viết vào hình, lắp ghép.
 Nhập N, dãy a1, a2,, aN
M ¬ N
M < 2
Tráo đổi ai và ai+1
i ¬ i +1
i > M ?
ai < ai+1 ?
Đúng
Sai
Đưa ra dãy A rồi kết thúc
M ¬ M - 1 ; i ¬ 0
Sai
Sai
Đúng
Đúng
Hình 6: Sản phẩm của HS
GV: Về nhà hãy viết các thao tác và phép tính toán (biểu thức) vào các hình, lắp ghép thành sơ đồ khối thuật toán sắp xếp lại thành dãy "không tăng", học sinh chạy thử thuật toán với Test 01: N=8, a1= 5, a2 = 1, a3 = 4, a4 = 7, a5 = 6, a6 = 12, a7=15, a8=10, thay số (viết vào đồ dùng học tập) và thực hiện Test trên sơ đồ khối ?
Ví dụ 2: Bài toán tìm kiếm
Cho dãy A gồm N số nguyên khác nhau: a1,a2,,aN và một 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ố đó.
Số nguy