SKKN Bài toán và thuật toán_SGK Tin học 10

Mục lục
 Mục
 Trang
A. PHẦN MỞ ĐẦU
2
1. Lý do chọn đề tài
2
2. Mục đích của đề tài
3
3. Phương pháp và đối tượng nghiên cứu
3
4. Điểm mới trong kết quả nghiên cứu
3
B. NỘI DUNG
4
I. Cơ sở lý luận
4
II. Cơ sở thực tiễn
4
1. Thuật toán tìm giá trị lớn nhất của một dãy số
4
2. Thuật toán Kiểm tra tính nguyên tố của một số nguyên dương
5
3. Thuật toán Sắp xếp bằng phương pháp tráo đổi
6
C. KẾT QUẢ SAU KHI THỰC HIỆN NHƯ SAU
11
D. KẾT LUẬN VÀ ĐỀ XUẤT
12
E. TÀI LIỆU THAM KHẢO
13
A. PHẦN MỞ ĐẦU
1. LÝ DO CHỌN ĐỀ TÀI
	Công nghệ thông tin là một ngành khoa học đang phát triển rất mạnh mẽ. Sự bùng nổ thông tin trong thời đại ngày nay, tốc độ phát triển của công nghệ thông tin đi đôi với sự phát triển của xã hội văn minh, hiện đại.
	Do đó người thầy cần phải tìm ra phương pháp dạy học tích cực hơn để tăng hiệu quả dạy và học. Dạy học sinh cách chủ động, phương pháp học, cách học những điều mà thực tế đòi hỏi thay vì chuyển tải một lượng kiến thức quá nhiều đến mức chúng không thể nhớ nổi hoặc có nhớ lúc học, còn lúc cần vận dụng thì dể quên.
	Môn Tin học là một môn học mới mẻ của học sinh THPT, học sinh chưa có khái niệm về công nghệ thông tin, khái niệm thuật toán trong các ngôn ngữ lập trình, vì vậy rất khó cho việc dạy và học.
Nhiều học sinh, phụ huynh còn nhiều bở ngỡ với môn tin học, chưa có định hướng và phương pháp tích cực để học tốt môn tin học.
Có nhiều học sinh nhầm tưởng với việc học tin học là sử dụng thành thạo máy tính, nhưng chưa thực sự hiểu về lập trình.
Trong quá trình giảng dạy môn Tin học 10, khi dạy Bài 4 “BÀI TOÁN VÀ THUẬT TOÁN_ SGK Tin học 10”. Trong bài này, học sinh cần nắm được khái niệm thuật toán, các tính chất của thuật toán, cách biểu diễn thuật toán, hiểu được một số thuật toán thông dụng. Đồng thời học sinh nắm bắt được phương pháp giải một bài toán trong tin học. Hiểu và hình dung các bước của thuật toán để giải một bài toán trong tin học. 
Vậy làm thế nào để học sinh hiểu rõ và viết được thuật toán cho các bài toán cơ bản ? đây là một việc không hề dễ đối với các em học sinh.
Vì vậy tôi sử dụng phương pháp. 
“MÔ PHỎNG TRỰC QUAN GIÚP HỌC SINH HIỂU MỘT SỐ THUẬT TOÁN THÔNG DỤNG KHI DẠY BÀI 4 SGK TIN HỌC 10 ”. 
2. MỤC ĐÍCH CỦA ĐỀ TÀI
Trong tin học, để giải một bài toán có thể có nhiều phương pháp khác nhau, hay một bài toán có thể được giải quyết bởi nhiều thuật toán khác nhau. Nhưng việc quan trọng là phải tìm ra một thuật toán tối ưu nhất 
Việc giúp cho học sinh hiểu sâu tầm quan trọng của thuật toán, nắm chắc và có khả năng hiểu, tự mình viết được một số thuật toán cơ bản là nhiệm vụ quan trọng của giáo viên.
Đề tài này nhằm mục đích giúp cho các em học sinh có thể hiểu và nắm chắc một số thuật toán cơ bản trong tin học một cách nhanh và hiệu quả bằng việc học thông qua các mô phỏng thuật toán trực quan.
3. PHƯƠNG PHÁP VÀ ĐỐI TƯỢNG 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ụ 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 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, ứng dụng, sưu tầm, phân tích kết quả thực nghiệm sư phạm, phù hợp với bài học và môn học.
Trong nội dung sáng kiến này tôi tập trung vào đối tượng là học sinh 3 lớp: 11A1, 11A2,11A9 - Trường THPT Nông Cống 1( Trong đó có 2 lớp Ban khoa học tự nhiên, 1 lớp Ban khoa học xã hội)
4. ĐIỂM MỚI TRONG KẾT QUẢ NGHIÊN CỨU
Sử dụng các phần mềm có sẵn như Powerpoint cùng các chức năng của nó để xây dựng các mô phỏng trực quan theo các bước của thuật toán từ đó giúp học sinh nắm bắt sâu hơn về các thuật toán thông dụng trong tin học.
B. PHẦN NỘI DUNG
I. CƠ SỞ LÍ LUẬN 
Học sinh đã nắm bắt được các khái niệm như khái niệm bài toán, khái niệm thuật toán và phương pháp biểu diễn thuật toán, bắt đầu học và hiểu được một số thuật toán thông dụng.
II. CƠ SỞ THỰC TIỄN
1. Thuật toán tìm giá trị lớn nhất của một dãy số.
Bài toán: 
Cho một dãy số nguyên gồm N số a1,a2an. (N<250, ai<500)
Yêu cầu: Tìm giá trị lớn nhất của dãy số nguyên trên
Cho học sinh xác định bài toán:
Input: số nguyên N và dãy gồm N số nguyên a1,a2..an.
Output: giá trị lớn nhất (max) của dãy số.
THUẬT TOÁN TÌM GIÁ TRỊ LỚN NHẤT CỦA MỘT DÃY SỐ NGUYÊN
X¸c ®Þnh bµi to¸n:
INPUT: Sè nguyªn dư¬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è.
Giáo viên hướng dẫn, học sinh đưa ra ý tưởng giải quyết bài toán.
	Trước khi cho học sinh tìm hiểu tìm hiểu thuật toán của bài này, giáo viên có thể đưa ra ý tưởng tìm số lớn nhất trong 12 số như sau:
- Thông thường trong lớp mỗi bên có 6 dạy bàn
- Vậy hai bên có 12 dãy bàn
- Giáo viên đặt ngẫu nhiên 12 con số khác nhau ở mỗi đầu bàn và yêu cầu học sinh đưa ra cách tìm số lớn nhất trong 12 số đó:
	Vậy ta tìm theo quy luật nào?
	- Bước 1: Giã sử số ở bàn đầu tiên là số lớn nhất
	- Bước 2: Ta so sánh với số ở bàn thứ hai; nếu số ở bàn thứ hai lớn hơn thì ta đổi cho số ở bàn số 1; ngược lại thì bỏ qua; cứ tiếp tục như vậy ta so sánh đến số cuối cùng sẽ thu được số có giá trị lớn nhất trong dãy.
Trên đó là hai bước cơ bản để định hướng cho học sinh biết cách tìm ra số lớn nhất trong một dãy số.
THUẬT TOÁN TÌM GIÁ TRỊ LỚN NHẤT CỦA MỘT DÃY SỐ NGUYÊN
ý t­ëng:
- 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 Kiểm tra tính nguyên tố của một số nguyên dương.
Phát biểu bài toán: Cho số nguyên dương N (0<N<32767)
Yêu cầu: Kiểm tra N có phải là số nguyên tố không?
THUẬT TOÁN KIỂM TRA TÍNH NGUYÊN TỐ CỦA MỘT SỐ NGUYÊN 
XÁC ĐỊNH BÀI TOÁN:
INPUT: N là số nguyên dương (0<N<=32765).
OUTPUT: “N là nguyên tố” hoặc “N không là nguyên tố”.
Giáo viên hướng dẫn học sinh xác định bài toán và nêu ý tưởng để giải quyết bài toán:
Ý TƯỞNG:
Giáo viên: Hãy nêu định nghĩa số nguyên tố và cho biết phương pháp để kiểm tra tính nguyên tố của số nguyên dương N bất kì?
Học sinh nêu ý tưởng:
Nếu N=1 Thì 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 phần nguyên căn bậc hai của N thì N là số nsguyên tố.
Thuật toán Sắp xếp bằng phương pháp tráo đổi
Phát biểu bài toán: Cho dãy số nguyên gồm N số nguyên a1,a2an. (N<250, ai<500)
Yêu cầu: Hãy sắp xếp dãy số trên thành dãy số tăng dần.
Giáo viên hướng dẫn học sinh xác định bài toán và nêu ý tưởng:
* Giáo viên có thể đưa ra một ví vụ minh họa như: Có hai cốc nước đầy mầu khác nhau, em hãy tìm cách đỗ nước từ cốc này sang cốc kia
GV hướng dẫn: Ta phải sử dụng cốc trung gian
THUẬT TOÁN SẮP XẾP BẰNG TRÁO ĐỔI 
XÁC ĐỊNH BÀI TOÁN:
INPUT: Dãy số A gồm N số nguyên a1,a2,an.
OUTPUT: Dãy A được sắp xếp thành dãy tăng dần.
THUẬT TOÁN SẮP XẾP BẰNG TRÁO ĐỔI 
Ý TƯỞNG:
Với mỗi cặp số hạng đứng liền kề trong dãy, ta xét:
	Nếu số trước lớn hơn số sau thì hoán đổi vị trí chúng cho nhau.
	Lặp lại công việc đó, cho đến khi không có sự đổi chổ nào xảy ra nữa.
(sau mỗi lần đổi chổ, giá trị lớn nhất của dãy A sẽ được chuyển dần về cuối dãy).
II. GIẢI QUYẾT VẤN ĐỀ 
Các thuật toán cần được diễn đạt bằng cách viết theo các bước tuần tự hoặc vẽ sơ đồ khối, sau đó dùng các mô phỏng trực quan trên những ví dụ cụ thể.
Thuật toán tìm giá trị lớn nhất của một dãy số.
Mô phỏng trên ví dụ cụ thể như sau
Tìm ra kết quả (output)
Thuật toán kiểm tra tính nguyên tố của một số nguyên dương.
Biểu diễn thuật toán bằng cách vẽ sơ đồ khối
Trực quan bằng Powerpoint
Xây dựng ví dụ với nhiều bộ input khác nhau
3. Thuật toán sắp xếp bằng phương pháp tráo đổi
Cách 2: Sơ đồ khối
C. KẾT QUẢ SAU KHI THỰC HIỆN NHƯ SAU
Đề tài được áp dụng khi giảng dạy với đối tượng là học sinh các lớp 11A1, 11A4,11A9 trường THPT Nông Cống 1; với kết quả là
GIỎI
KHÁ
TB
YẾU
SL
TL
SL
TL
SL
TL
SL
TL
11A1
20
43,5%
26
56,5%
0
0
0
0
11A2
15
32,6%
25
54,3%
6
13,1%
0
0
11A9
2
5,2%
27
69,2%
10
25,6%
Kết quả này phản ánh đúng thực tế năng lực của từng loại đối tượng học sinh( Lớp 11A1, 11A4 là lớp khối A; lớp 11A9 lớp khối C)
	Trên đây tôi xin trình bày một số thuật toán theo phương pháp mô phỏng trực quan nhằm giúp học sinh có thể hiểu về thuật toán và xây dựng thuật toán dễ dàng hơn; 
	Bài toán còn nhiều, thuật toán thì đa dạng mong bạn đọc, đồng nghiệp góp ý và xây dựng thêm.
D. KẾT LUẬN VÀ ĐỀ XUẤT
	Sau khi thực hiện nghiên cứu và thử nghiệm trong năm học 2017- 2018 tôi thấy cần có thời gian nhiều hơn để thử nghiệm, vì vẫn còn có một số học sinh chưa đạt yêu cầu. 
Tin học là một môn học mới mẻ của học sinh THPT và không thuộc môn khối của học sinh, do đó đa số học sinh trong trường không chú tâm học, vì vậy rất khó cho việc dạy và học.
 Cần phải có thời gian nhiều hơn cho lý thuyết và thực hành, vì theo phân phối chương trình như hiện thời gian giảng dạy còn ít, học sinh chưa nắm bắt được lý thuyết cũng như thực hành.
XÁC NHẬN CỦA THỦ TRƯỞNG ĐƠN VỊ
Thanh Hóa, ngày 16 tháng 05 năm 2018
 Tôi xin cam đoan đây là SKKN của mình, không sao chép nội dung của người khác.
 Tác giả
 ĐỖ CẢNH TOÀN
E. TÀI LIỆU THAM KHẢO
1. Sách giáo khoa Tin học 10 - Hồ Sĩ Đàm.
2. Sách giáo viên Tin học 10,11 của Bộ GD&ĐT phát hành
3. Tài liệu bồi dưỡng giáo viên Tin học 10.
4. Chuẩn kiến thức môn Tin học.
5. Giải bài toán trên máy tính như thế nào – Hoàng Kiếm
6. Phương pháp giải các bài toán trong tin học - Trần Đức Huyên
7. Cấu trúc dữ liệu và giải thuật của Đỗ Xuân Lôi
8. Ngôn ngữ lập trình Pascal của Quách Tuấn Ngọc