Sáng kiến kinh nghiệm THCS: Phát triển tư duy thuật toán cho học sinh thcs thông qua việc khai thác một số bài toán cơ bản trong môn Tin học

Chia sẻ: Chubongungoc | Ngày: | Loại File: PDF | Số trang:17

Thêm vào BST

Báo xấu

45
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Sáng kiến kinh nghiệm Tiểu học được hoàn thành với một số biện pháp như sau: Rèn luyện khả năng đặc biệt hóa, khái quát hóa thông qua một số bài toán cơ bản, từ đó vận dụng phép tương tự hóa để giải quyết các bài toán mở rộng, bài toán thực tiễn; Rèn luyện cho học sinh khả năng phân tích, tổng hợp, vận dụng các kiến thức, kỹ năng đã có để giải quyết bài toán theo nhiều thuật giải khác nhau từ đó lựa chọn ra thuật giải tối ưu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Sáng kiến kinh nghiệm THCS: Phát triển tư duy thuật toán cho học sinh thcs thông qua việc khai thác một số bài toán cơ bản trong môn Tin học

CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập – Tự do – Hạnh phúc ĐƠN YÊU CẦU CÔNG NHẬN SÁNG KIẾN PHÁT TRIỂN TƯ DUY THUẬT TOÁN CHO HỌC SINH THCS THÔNG QUA VIỆC KHAI THÁC MỘT SỐ BÀI TOÁN CƠ BẢN TRONG MÔN TIN HỌC Đồng tác giả: 1. Lê Xuân Ngưu - Chức vụ: Giáo viên - Học vị: Đại Học 2. Lưu Thị Thủy - Chức vụ: Hiệu trưởng- Học vị: Đại Học 3. Trần Văn Trường - Chức vụ: Giáo viên - Học vị: Đại Học Đơn vị công tác: Trường THCS Ninh Phong – Phường Ninh Phong – Thành phố Ninh Bình TP. Ninh Bình, tháng 09 năm 2018
CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập - Tự do - Hạnh phúc ĐƠN YÊU CẦU CÔNG NHẬN SÁNG KIẾN Kính gửi: Hội đồng sáng kiến tỉnh Ninh Bình. Chúng tôi gồm: Trình Tỷ Năm độ lệ(%) TT Họ và tên Nơi công tác Chức danh sinh chuyên đóng môn góp 1 Lê Xuân Ngưu 1985 Trường Giáo viên Đại Học 50% THCS Ninh Đại Học 2 Lưu Thị Thủy 1972 Hiệu trưởng 30% Phong - Thành 3 Trần Văn Trường 1980 phố Ninh Bình Giáo viên Đại Học 20% 1. Tên sáng kiến, lĩnh vực áp dụng Là nhóm tác giả đề nghị xét công nhận sáng kiến: PHÁT TRIỂN TƯ DUY THUẬT TOÁN CHO HỌC SINH THCS THÔNG QUAVIỆC KHAI THÁC MỘT SỐ BÀI TOÁN CƠ BẢN TRONG MÔN TIN HỌC Lĩnh vực áp dụng sáng kiến: Dạy học bồi dưỡng đội tuyển tin học cấp trường, thành phố, cấp tỉnh, dạy học đại trà trong các trường trung học cơ sở. Sáng kiến được áp dụng lần đầu trong năm học 2015-2016 2. Nội dung sáng kiến Dạy tin học lập trình là một hoạt động nghiên cứu khá phức tạp bao gồm các hoạt động dạy học về ngôn ngữ lập trình, xác định bài toán và thuật toán, chương trình…trong việc xác định bài toán và thuật toán là một công việc hết sức quan trọng. Muốn xác định được thuật giải tối ưu thì người học phải có tư duy thuật toán tốt. Tư duy thuật toán được đặc trưng bởi các khả năng phân tích một hoạt động thành những thao tác thành phần được thực hiện theo một trình tự xác định mô tả chính xác quá trình tiến hành một hoạt động, khái quát hóa một hoạt động trên những đối tượng riêng lẻ thành một hoạt động trên một lớp đối tượng, so sánh những thuật toán khác nhau cùng thực hiện một công việc và phát triển thuật toán tối ưu. Mỗi bài toán có thể có nhiều thuật giải khác nhau, mỗi thuật giải là một định hướng suy luận riêng, nó thể hiện tư duy thuật toán của mỗi học sinh nên khi đứng trước một bài toán học sinh thường không biết bắt đầu từ hướng nào? phải làm như thế nào? bắt đầu từ đâu? Trong dạy học bồi dưỡng học sinh giỏi hay dạy học đại trà nếu giáo viên bắt đầu từ bài toán khó sẽ rất khó khăn trong việc giảng dạy truyền đạt kiến thức cho học sinh, học sinh cũng sẽ khó tư duy, bài toán trở nên trừu tượng dẫn đến không hiệu quả trong học tập. Mặt khác chúng ta không có nhiều thời gian có thể dạy hết cho học sinh tất cả các bài tập cũng như các em không thể làm hết các bài tập 1
đó. Vì vậy để tạo ra mối quan hệ logic giữa các bài tập, khi hướng dẫn cho học sinh giải một bài toán, giáo viên cần hướng dẫn cho học sinh biết khai thác, vận dụng, mở rộng kết quả những bài toán đơn giản và khai thác bài toán gốc để xây dựng các bài toán mới liên quan. Điều này giúp học sinh rèn luyện tư duy lôgic óc, sáng tạo, tự tìm tòi, suy nghĩ ra những bài toán mới và có những cách giải hay. Muốn có tư duy lập trình tốt thì học sinh cần nắm chắc kiến thức từ cơ bản và đứng trước một bài toán phải có cách tiếp cận, đánh giá và giải quyết các vấn đề của bài toán một cách tối ưu chứ không đơn thuần là tìm ra lời giải cho xong. Bởi trong tin học lập trình không phải cứ tìm ra lời giải là đã giải quyết được bài toán. Qua thực tiễn và nghiên cứu tôi nhận thấy rằng việc rèn luyện tư duy thuật toán là một cách làm hay, phù hợp với xu thế chung, góp phần vào việc đổi mới phương pháp dạy học, rèn luyện kiến thức, kĩ năng, óc sáng tạo và bồi dưỡng năng lực tư duy cho học sinh và ngoài ra còn gây hứng thú, ham thích học toán cho các em. Tuy nhiên, trong thực tế giảng dạy của các giáo viên vẫn truyền đạt kiến thức cho học sinh theo hướng thụ động, việc dạy và rèn luyện kiến thức cho học sinh còn rời rạc, riêng lẻ chưa thấy được sự kết nối, xâu chuỗi các bài toán với nhau thành một hệ thống dẫn đến học sinh chưa có kĩ năng quy lạ về quen, chưa biết cách biến đổi từ một bài toán gốc để phát triển các bài toán mới, tổng quát hóa, đặc biệt hóa, giải thuật bài toán chưa tối ưu… Để góp phần khắc phục tình trạng trên và phát huy được tối đa năng lực tư duy của học sinh, tạo niềm say mê, yêu thích môn học. chúng tôi xin được đưa ra sáng kiến: “ PHÁT TRIỂN TƯ DUY THUẬT TOÁN CHO HỌC SINH THCS THÔNG QUA VIỆC KHAI THÁC MỘT SỐ BÀI TOÁN CƠ BẢN TRONG MÔN TIN HỌC ” nhằm giúp giáo viên đổi mới phương pháp dạy học, học sinh phát triển được năng lực tư duy, óc sáng tạo, sự hứng thú học cho học sinh, nâng cao chất lượng giáo dục, tạo nguồn nhân lực chất lượng cao trong giai đoạn cuộc cách mạng 4.0. 2.1 Giải pháp cũ. Trong nhiều năm đứng lớp, dự giờ đồng nghiệp tôi thấy phương pháp một số giáo viên cho học sinh tiếp cận với các bài toán lập trình theo hướng như sau: - Sau khi học sinh đã biết được ngôn ngữ lập trình, đa số giáo viên thường dạy hoặc cho học sinh làm các bài tập một cách rời rạc, riêng lẻ mà chưa biết khai thác, phát triển, mở rộng bài toán mới từ “bài toán gốc” (bài toán cơ bản) rồi khái quát, xâu chuỗi thành một hệ thống lớp các bài tập có kiến thức liền mạch, logic với nhau (trong thực tế giáo viên thường sưu tầm các bài tập, đề thi sau đó dạy hoặc giao cho học sinh làm các đề tại các thời điểm khác nhau). - Giáo viên thường không rèn luyện cho học sinh tư duy phân tích, giải quyết bài toán bằng nhiều cách khác nhau để tìm ra thuật giải tốt nhất mà đơn thuần chỉ quan tâm đến việc giải quyết bài toán cho xong (không quan tâm đến giới hạn dữ liệu và thời gian chạy chương trình của thuật toán) hoặc giáo viên cho học sinh công nhận thuật giải mà không cần giải thích tại sao phải thực hiện thuật giải này, cở sở thuật 2
toán này xuất phát từ đâu? a) Ưu điểm Giáo viên không mất nhiều thời gian để tổng hợp, sưu tầm các bài tập theo cùng một dạng, việc dạy học theo phương pháp này giúp giáo viên dễ giảng dạy, không đòi hỏi giáo viên có kiến thức sâu rộng về lập trình, áp dụng được cho nhiều đối tượng học sinh. b) Nhược điểm Giáo viên truyền thụ kiến thức cho học sinh một cách độc lập, riêng lẻ không logic với nhau, giữa các bài toán không có sự kế thừa, làm cho học sinh mất nhiều thời gian hình thành tư duy tổng hợp, khái quát hóa, tương tự hóa thuật toán. Giáo viên và học sinh chỉ quan tâm tới việc giải quyết bài toán cho xong mà không quan tâm đến giới hạn thời gian và dữ liệu bài toán, dẫn đến thuật toán không tối ưu, không rèn luyện được khả năng phân tích bài toán với nhiều thuật giải khác nhau để tìm ra lời giải khả thi nhất. (đây là một trong nhưng kỹ năng quan trọng trong lập trình tin học). Việc giáo viên cho học sinh làm theo cách công nhận thuật giải tối ưu mà không giải thích tại sao? xuất phát từ cơ sở nào để có thuật toán này? làm cho học sinh khó hiểu, mất nhiều thời gian học tập, không hình thành được tư duy thuật toán, từ đó dẫn đến học sinh không có động cơ học tập, gây tâm tí chán nản, không yêu thích môn học. 2.2 Giải pháp mới cải tiến Dựa vào những kinh nghiệm giảng dạy, phân tích ưu và nhược điểm về phương pháp dạy học, cách tiếp cận các bài toán lập trình của một số giáo viên đã nêu ở trên, tôi đã nghiên cứu và đưa ra sáng kiến “PHÁT TRIỂN TƯ DUY THUẬT TOÁN CHO HỌC SINH THCS THÔNG QUA VIỆC KHAI THÁC MỘT SỐ BÀI TOÁN CƠ BẢN TRONG MÔN TIN HỌC” nhằm phát huy những ưu điểm và khắc phục những nhược điểm của phương pháp cũ như sau: Giải pháp 1: Rèn luyện khả năng đặc biệt hóa, khái quát hóa thông qua một số bài toán cơ bản, từ đó vận dụng phép tương tự hóa để giải quyết các bài toán mở rộng, bài toán thực tiễn. Đặc biệt hóa là khả năng chuyển từ nhiệm vụ nghiên cứu các tập hợp các đối tượng đã cho, lớn hơn sang nhiệm vụ nghiên cứu tập hợp các đối tự nhỏ hơn. Khái quát hóa là khả năng chuyển từ việc nghiên cứu tập hợp các đối tượng nhỏ sang nghiên cứu những tập hợp đối tượng lớn hơn, từ đó đưa ra thuật giải tổng quát cho bài toán. Giải pháp này yêu cầu học sinh đứng trước một bài toán tổng quát phải biết vận dụng các thao tác đặc biệt hóa, tức là phải biết phân tích đưa bài toán lớn, bài toán tổng quát về giải các bài toán đặc biệt, cơ bản, nhỏ hơn, tìm ra cái chung và cái riêng để đưa ra cách giải cho bài toán tổng quát, từ đó vận dụng phép tương tự để giải quyết các bài toán mở rộng, bài toán thực tiễn. 3
Ví dụ minh họa:  Rèn luyện khả năng đặc biệt hóa, khái quát hóa thuật toán cho học sinh. * Trước tiên giáo viên và học sinh xây dựng thuật của bài toán cơ bản “ Tìm ước chung lớn nhất của hai số nguyên dương a và b” Bài 1. Cho hai số nguyên dương a và b. Hãy tìm ước chung lớn nhất của a và b. Ví dụ a=5; b=10 khi đó ước chung lớn nhất của a và b là 5. Ý tưởng thuật toán : Với a, b là hai số nguyên (a ≥ b), ta thực hiện chia a cho b được thương q, số dư r (r ≥ 0) tức là a = bq + r, khi đó ta có: b nếu r =0 UCLN(a, b)   nếu r ≠0  UCLN(b, r) Chương trình tham khảo: Function UCLN(a, b: longint):longint; var x,y,r: longint; Begin x:= b; y:= a; while y 0 do begin r:= x mod y; x:= y; y:= r; end; UCLN:=x; End; * Giáo viên tạo tình huống có vấn đề bằng cách đưa ra bài toán tổng quát. Bài toán 1.1. Cho một dãy số nguyên dương gồm n phần tử. Hãy tìm ước chung lớn nhất của n số trong dãy. Ví dụ: Cho dãy số gồm 5 phần tử 8; 12; 4; 6 thì ước chung lớn nhất của dãy số là 2. Gặp bài toán này học sinh sẽ thấy bài toán rất quen thuộc, gần tương tự với bài 4
toán cơ bản 1. Tuy nhiên các em sẽ gặp khó khăn về thuật giải với n số. Như vậy giáo viên đã tạo cho học sinh một tình huống có vấn đề mà học sinh cần phải tư duy để vượt qua khó khăn này. Để giảm mức độ khó giáo viên yêu cầu học sinh nêu ý tưởng: Tìm ước chung lớn nhất của 3 số, khi học sinh làm được giáo viên tiếp tục yêu cầu học sinh tìm ước chung lớn nhất của 4 số, 5 số … Lúc này học sinh sẽ rút ra thuật giải tổng quát của bài toán tìm ước chung của N số như sau: Gọi U1 là ước chung lớn nhất của a1 và a2. Bước tiếp theo tìm ước lớn nhất của U 1 với a3, gọi U2 là ước chung lớn nhất của U 1 và a3. Tiếp tục tìm ước chung của U2 với a4…Tìm ước chung lớn nhất của Un-2 với n. Cuối cùng ta được ước chung của dãy gồm n phần tử là Un-1. Chương trình tham khảo: const fi='uclnmax.inp'; fo='uclnnax.out'; var i,ucmax,n:longint; u:array[1..100000] of longint; function UCLN(a,b:longint):longint; var x,y,r: longint; Begin x:= b; y:= a; while y 0 do begin r:= x mod y; x:= y; y:= r; end; ucln:=x; end; BEGIN assign(input,fi); reset(input); readln(n); for i:=1 to n do read(u[i]); assign(output,fo); rewrite(output); ucmax:=ucln(u[1],u[2]); for i:=3 to n do ucmax:=ucln(ucmax,u[i]); write(ucmax); close(input); close(output); END. 5
Nhận xét: Từ bài toán tổng quát (bài 1.1), dựa trên thuật toán của bài toán cơ bản đã biết (bài toán 1) giáo viên đã rèn cho học sinh khả năng đặc biệt hóa, khái quát hóa thuật toán, quy bài toán lạ về bài toán quen thuộc cơ bản, bài toán quen thuộc. Rèn luyện được cho học sinh kỹ năng này sẽ là tiền đề giúp các em học tốt phương pháp quy hoạch động, đệ quy.  Từ bài toán cơ bản đã biết, vận dụng phép tương tự hóa để giải quyết một số bài toán tương tự mở rộng, bài toán thực tiễn. Từ bài toán cơ bản tìm ước chung lớn nhất của 2 số nguyên a và b, giáo viên tiếp tục đưa ra một số bài toán mở rộng tương tự, bài toán thực tiễn để học sinh có thể vận dụng các kiến thức, kỹ năng từ bài toán cơ bản để giải quyết một số bài toán tương tự mở rộng, các bài toán ứng dụng trong thực tiễn, từ đó hình thành tư duy sáng tạo cho các em thông qua việc khai thác một chuỗi các bài tập có liên quan logic với nhau. Sau đây chúng tôi xin giới thiệu một số bài toán tương tự mở rộng và một số bài toán thực tiễn, các bài toán này đều được phát triển từ bài toán gốc “tìm ước chung lớn nhất của 2 số nguyên dương”. Lớp các bài toán này được đính kèm bên dưới phần phụ lục của sáng kiến. Tính mới và sáng tạo của giải pháp 1: Giải pháp này giúp học sinh rèn luyện kỹ năng quy lạ về quen, đưa nặng về nhẹ, chuyển đổi các bài toán phức tạp cồng kềnh thành những bài toán cơ ban đã biết. Với giải pháp mới này, giáo viên đã giúp học sinh tiết kiệm được thời gian để hình thành tư duy thuật toán thông qua lớp bài toán có kiến thức liền mạch, logic với nhau. Giải pháp 2. Rèn luyện cho học sinh khả năng phân tích, tổng hợp, vận dụng các kiến thức, kỹ năng đã có để giải quyết bài toán theo nhiều thuật giải khác nhau từ đó lựa chọn ra thuật giải tối ưu. Đứng trước một bài toán mới lạ phải học sinh phải linh hoạt, mềm dẻo đưa ra nhiều thuật giải khác nhau, không dập khuân, máy móc từ đó phân tích lựa chọn ra thuật giải tối ưu nhất cho bài toán. Rèn luyện được khả năng này giúp học sinh hình thành tư duy một cách sáng tạo, phát hiện ra vấn đề mới của thuật toán. Đây là một trong những kỹ năng quan trọng nhất trong lập trình. Ví dụ minh họa: Bài 2. Kiểm tra tính nguyên tố của một số nguyên. Cho một số nguyên N (với N≤1012). Hãy kiểm tra N có phải là số nguyên tố hay không? Ví dụ: N=11 là số nguyên tố, N=100 không phải là số nguyên tố. Giới hạn thời gian bài toán là 1s. Đối với bài toán 2 học sinh thường mắc những sai lầm sau: + Thứ nhất: Dùng thuật toán vét cạn để giải quyết bài toán một cách đơn thuần, không quan tâm đến giới hạn dữ liệu đầu bài (N≤1012), thời gian chạy chương trình nên dẫn đến thuật toán không tối ưu. Thuật toán vét cạn sau chỉ đảm bảo giới hạn dữ liệu (N≤106). 6
Function KTNT(N:longint):Boolean; Begin KTNT:=False; For i:=2 to n -1 do If N mod i =0 then Begin KTNT:=true; Break; End; End. + Thứ hai: Giáo viên dạy cho học sinh công nhận luôn thuật toán tối ưu (thuật toán đảm bảo chạy được giới hạn dữ liệu đề bài và thời gian nhỏ hơn 1 giây) mà không cần giải thích tại sao phải dùng thuật toán này? Điều này dẫn đến học sinh không hiểu được bản chất thực của thuật toán, do đó không phát huy được tư duy sáng tạo, không khơi dạy được niềm đam mê, hứng thú trong bộ môn tin học. Function KTNT(N:longint):Boolean; Begin KTNT:=False; For i:=2 to trunc(sqrt(n)) do If N mod i =0 then Begin KTNT:=true; Break; End; End. Để khắc phục những lỗi trên giáo viên cần xây dựng các tình huống có vấn đề để học sinh có thể phân tích, lựa chọn thuật giải tối ưu cho bài toán như sau: + Giáo viên xây dựng 2 bộ test N≤106 và 10610 6 học sinh sẽ phát hiện chương trình sẽ chạy thời gian quá 1s không đảm bảo giới hạn về thời gian chạy. Như vậy đây là một tình huống có vấn đề mà học sinh cần tuy duy sáng tạo, phân tích, tổng hợp các kiến thức đã học để đưa ra cách giải khác để giải quyết bài toán. Đến đây giáo viên có thể yêu cầu học sinh nhắc lại và lấy ví dụ về tính chất kiểm tra ước trong toán học mà các em đã được biết trong chương trình toán học lớp 6 như sau: “ Mỗi hợp số n có ít nhất một ước số nguyên tố nhỏ hơn hoặc bằng n ”. Sau khi học sinh biết được tính chất này sẽ tư duy thuật giải mới và cải tiến thuật toán cũ từ giới hạn N≤1012 về giới hạn N≤ 1012 =10 6. Bài toán đã được giải 7
quyết một cách tối ưu theo cách For i:=2 to trunc(sqrt(n)) do… Nhận xét: Với bài toán trên giáo viên đã rèn cho học sinh khả năng phân tích bài toán, đưa ra nhiều cách giải từ đó lựa chọn ra thuật giải tối ưu, điều này giúp học sinh hình thành kỹ năng phát hiện vấn đề, đưa ra thuật toán tối ưu một cách nhanh nhất khi gặp một bài toán khác tương tự như tính tổng, đếm các số nguyên tố trong một dãy số cho trước… Bài 3. Cho số nguyên dương n (n≤1000). Đếm ước nguyên tố của n!. Ví dụ: N=3 thì N!=3! có 4 ước số là 1; 2; 3; 6. Giới hạn thời gian bài toán là 1s. Đối với bài toán này một trong những sai lầm lớn nhất của của giáo viên và học sinh là tính n!, sau đó duyệt trong đoạn từ [1;n!] để thực hiện kiểm tra nguyên tố và đếm, cách này là không khả thi về mặt dữ liệu và thời gian, vì khi tính n! sẽ dẫn đến lỗi tràn dữ liệu với n>20. Tương tự như trên giáo viên cần xây dựng các tình huống cho học sinh phân tích lựa chọn thuật giải như sau: Giáo viên xây dựng bộ test N≤20 và n>20 + Với N>20 học sinh sẽ phát hiện ra lỗi tràn dữ liệu nếu sử dụng thuật tính N!. Khi đó học sinh cần phải tư duy, vận dụng các kiến thức đã có để giải quyết vấn đề trên bằng một thuật giải khác hoặc giáo viên có thể cho học sinh phân tích một số ví dụ để rút ra kết luận “mọi ước nguyên tố của N! đều nhỏ hơn hoặc bằng N” nên chỉ cần duyệt từ khoảng [2;N] để kiểm tra và đếm các số nguyên tố, thuật toán này hoàn toán khả thi về dữ liệu và thời gian. Qua các tình huống và cách phân tích thuật giải bài toán 4 , học sinh sẽ lựa chọn cách tối ưu nhất. Chương trình thuật toán tham khảo: Function Demnt(N:integer):integer; Var i:integer; Begin For i:=2 to N do If KTNT(i) then Inc(Demnt); End; Tương tự như vậy giáo viên có thể khai thác một số lớp các các bài toán có cùng cách giải được khai thác từ bài toán cơ bản để rèn luyện tư duy sáng tạo của học sinh. Sau đây chúng tôi xin giới thiệu lớp bài toán sử dụng thuật toán cơ bản “Phân tích một số nguyên dương thành tích các thừa số nguyên tố ” để tiếp tục rèn luyện cho học sinh khả năng phân tích, tổng hợp thuật toán từ đó lựa chọn thuật giải tối ưu. Lớp các bài toán này được đính kèm bên dưới phần phụ lục của sáng kiến. Tính mới, tính sáng tạo của giải pháp 2. Tính mới và tính sáng tạo của giải pháp 2 được thấy rõ trong việc rèn luyện để hình thành tư duy phân tích, tổng hợp cho học sinh bằng cách đưa ra nhiều thuật giải, từ đó lựa chọn thuật giải tối ưu nhất của bài toán. 8
Giải pháp giúp giáo viên và học sinh hiểu rõ được bản chất của thuật toán, khắc phục được việc chỉ giải bài toán một cách đơn giản là chạy được chương trình hoặc công nhận thuật giải mà không biết thuật toán đã tối ưu hay chưa? Khi học sinh hình thành được tư duy sáng tạo trong thuật toán sẽ giúp các em thích giải quyết những bài toán ở mức độ cao hơn từ đó tạo hứng thú, ham thích học bộ môn lập trình cho các em. 3. Hiệu quả của sáng kiến. 3.1. Hiệu quả kinh tế Trong các năm học 2015-2016, 2016-2017 ; 2017-2018, tỉ lệ học sinh đạt giải rất cao so với các huyện khác trong tỉnh, luôn duy trì đứng thứ nhất toàn đoàn trong suốt 4 năm liên tiếp. Qua đó thể hiện việc áp dụng sáng kiến là khả thi rất cao. Đây chính là tiền đề để các em có động lực vào các lớp chuyên tin, các lớp năng khiếu lập trình. Qua học tập theo phương pháp trên giúp học sinh có kiến thức chuyên sâu, tư duy sáng tạo về lập trình, đây chính là nền tảng vững chắc về chi thức để các em định hướng nghề nghiệp trong tương lai. Đây chính là hiệu quả về mặt tri thức, chất xám của xã hội. Giúp giáo viên và học sinh giảm bớt thời gian học tập và nghiên cứu. Đây chính là hiệu quả về kinh tế về mặt thời gian và tri thức đối với học sinh và giáo viên. 3.2. Hiệu quả xã hội A. Hiệu quả trong công tác bồi dưỡng đội tuyển học sinh giỏi Việc áp dụng sáng kiến vào công tác bồi dưỡng đội tuyển học sinh giỏi đã đạt được những thành tích cao và được thể hiện qua bảng số liệu sau: Số HS Số HS Tỉ lệ % Số lượng giải Năm học Dự thi Đạt giải đạt giải Ba KK Nhất Nhì 2015-2016 06 06 100% 01 05 0 0 2016-2017 07 07 100% 01 05 01 0 2017-2018 09 09 100% 0 03 05 01 B. Hiệu quả trong việc nâng cao trình độ chuyên môn nghiệp vụ, bồi dưỡng tình cảm nghề nghiệp cho đội ngũ giáo viên trong ngành giáo dục, nâng cao uy tín của giáo viên trong công giảng dạy cũng như của ngành giáo dục Trong các năm học chất lượng đại trà luôn đạt và vượt chỉ tiêu về tỉ lệ học sinh khá giỏi, đặc biệt trong ba năm liên tiếp đội tuyển tin học của thành phố Ninh Bình do tôi phụ trách luôn xếp thứ nhất toàn tỉnh, tỉ lệ học sinh đạt giải luôn đạt tỉ lệ cao nhất tỉnh, hàng năm luôn có học sinh của trường đạt giải tin học trẻ cấp thành phố, cấp tỉnh. Đây chính là kết quả khẳng định chất lượng giảng dạy của đội ngũ giáo viên giảng dạy bộ môn tin học trong nhà trường THCS Ninh Phong và của thành phố Ninh 9
Bình, từ đó nâng cao uy tín của ngành giáo dục thành phố Ninh Bình trong công tác giảng dạy, đặc biệt là trong công tác giảng dạy đại trà, bồi dưỡng học sinh giỏi. Qua đó cũng làm cho xã hội, các phụ huynh yên tâm, tin tưởng tuyệt đối vào đội ngũ giáo viên, cũng như ngành giáo dục trong rèn luyện, đào tạo ra những con người có tài đức vẹn toàn để xây dựng quê hương giàu đẹp. C. Hiệu quả trong việc rèn luyện kĩ năng học tập và bồi dưỡng tình cảm của học sinh đối với môn tin học. Qua thực tiễn và nghiên cứu tôi nhận thấy rằng áp dụng sáng kiến vào dạy học theo định hướng khai thác và phát triển bài toán là một cách làm hay, phù hợp với xu thế chung, góp phần vào việc đổi mới phương pháp dạy học, rèn luyện kiến thức, kĩ năng, óc sáng tạo và bồi dưỡng năng lực tư duy cho học sinh và ngoài ra còn gây hứng thú, ham thích học bộ môn tin cho các em. 4. ĐIỀU KIỆN VÀ KHẢ NĂNG ÁP DỤNG 4.1. Khả năng áp dụng sáng kiến * Đối nhà trường: Năm học 2015-2016 có 01 em đạt giải nhì cấp tỉnh; 01 em đạt giải nhì trong cuộc thi tin học trẻ không chuyên cấp tỉnh, tỉ lệ đạt giải là 100%. - Năm học 2016-2017 có 02 em được đi thi tỉnh và đạt 01 giải nhì, 01 giải 3, tỉ lệ đạt giải 100%. - Năm học 2016-2017 có 01 em tham ra thi tin học trẻ không chuyên cấp tỉnh và đạt giải nhất và được chọn đi thi tin học trẻ toàn quốc. - Hằng năm chất lượng dạy học đại trà luôn luôn đạt và vượt chỉ tiêu. * Đối với đội tuyển tin học thành phố Ninh Bình Năm học 2015-2016 đội tuyển tin thành phố Ninh Bình xếp thứ nhất toàn tỉnh, trong 06 em tham gia đội tuyển đạt giải 100%, trong đó có 01 giải nhất và 05 giải nhì. Năm học 2016-2017 đội tuyển tin thành phố Ninh Bình xếp thứ nhất toàn tỉnh, trong 07 em tham gia đội tuyển đạt giải 100%, trong đó có 01 giải nhất và 05 giải nhì, 01 giải 3. Năm học 2017-2018 đội tuyển tin có 09 em dự thi tỉ lệ đạt giải là 100%, toàn đoàn đứng thứ nhất tỉnh, trong đó có 03 giải nhì, 05 em giải ba, 01 em giải khuyến khích. * Sáng kiến được áp dụng trong thử nghiệm trong năm đầu tiên 2015-2016 trong công tác dạy học đại trà và công tác bồi dưỡng học sinh giỏi cấp trường, cấp thành phố, cấp tỉnh đối với bộ môn lập trình tin học và một số bài toán trong chương trình bảng tính excel (tin học 7) và sau đó được áp dụng liên tiếp trong các năm học 2016- 2017; 2017-2018 và đã đạt được những hiệu quả nhất định trong dạy và học như chúng tôi đã trình bày ở trên. Các giáo viên tin dạy chương trình lập trình ở các nhà trường và cấp học khác hoàn toàn có thể áp dụng sáng kiến này trong công tác giảng dạy đại trà, bồi dưỡng học sinh giỏi để rèn luyện tư duy sáng tạo cho học sinh để nâng cao chất lượng giáo 10
dục. Giải pháp nêu trong sáng kiến hoàn toàn phù hợp với việc đổi mới phương pháp dạy học theo đinh hướng năng lực học sinh nên sáng kiến có thể áp dụng cho bộ môn toán học trong chương trình giáo dục phổ thông. 4.2. Điều kiện áp dụng sáng kiến Tuy vậy để áp dụng được sáng kiến ta cần đảm bảo các yêu cầu sau: Giáo viên phải nhiệt huyết, yêu nghề, yêu thích bộ môn lập trình tin học. Giáo viên phải có kiến thức tổng hợp chuyên sâu về bộ môn lập trình để có thể khai thác, phát triển các bài toán cơ bản thành các dạng, lớp bài toán nâng cao để rèn luyện tư duy cho học sinh. Học sinh phải có kiến thức cơ bản về ngôn ngữ lập trình, nắm được một số thuật toán cơ bản trong lập trình tin học. Danh sách những người đã tham gia áp dụng sáng kiến thử. Trình độ Nội dung Năm Chức STT Họ và tên Nơi công tác chuyên công việc sinh danh môn hỗ trợ Áp dụng Trường THCS 1 Giáo sáng kiến Lê Xuân Ngưu 1985 Ninh Phong -TP Đại Học viên vào giảng Ninh Bình dạy Áp dụng Trường THCS 2 Giáo sáng kiến Đoàn Duy Thường 1984 Trương Hán Siêu Thạc Sĩ Viên vào giảng - TP Ninh Bình dạy Chúng tôi xin cam đoan mọi thông tin nêu trong đơn là trung thực, đúng sự thật và hoàn toàn chịu trách nhiệm trước pháp luật. 11
TP. Ninh Bình, ngày 05 tháng 09 năm 2018 NGƯỜI NỘP ĐƠN TÁC GIẢ ĐỒNG TÁC GIẢ Lưu Thị Thuỷ Lê Xuân Ngưu Trần Văn Trường TRƯỜNG THCS NINH PHONG PHÒNG GDĐT THÀNH PHỐ NINH BÌNH XÁC NHẬN XÁC NHẬN Sáng kiến “Phát triển tư duy thuật toán cho học sinh thcs thông qua việc khai thác một số bài toán cơ bản trong môn tin học” đã được áp dụng và mang lại hiệu quả thiết thực tại trường THCS Ninh phong từ năm học 2015-2016 KT. HIỆU TRƯỞNG (Kí, đóng dấu) 12
PHỤ LỤC I. Vận dụng bài toán cơ bản “ Tìm ước chung lớn nhất của hai số nguyên dương” để phát triển và giải một số bài toán mở rộng, bài toán thực tiễn. A. Một số bài toán mở rộng Bài 1. Cho hai số nguyên dương a và b. Hãy kiểm tra hai số a, b có phải là 2 số nguyên tố cùng nhau không? Ví dụ a=3; b=10 là hai số nguyên tố cùng nhau. Bài 2. Cho hai số nguyên dương a và b. Tìm bội chung nhỏ nhất của 2 số nguyên dương a và b. Ví dụ a=2; b=10 bội chung nhỏ nhất là 10. a Bài 3. Cho phân số (b≠0) . Hãy rút gọn phân số trên? Ví dụ a=2; b=10 là thì b 1 phân số rút gọn là . 5 X1 X 2 X Bài 4. Cho dãy gồm N phân số , ,..., n . Y1 Y2 Yn Yêu cầu: Đếm xem có bao nhiêu phân số tối giản. Dữ liệu vào: Từ tệp PSTG.INP gồm N + 1 dòng: + Dòng đầu ghi số N (với N < 103, N  Z+). + N dòng tiếp theo mỗi dòng ghi hai số Xi, Yi ghi cách nhau một dấu cách là tử Xi số và mẫu số của phân số (với 1 ≤ Xi, Yi ≤ 103, Xi, Yi  Z+). Yi Dữ liệu ra: Là tệp PSTG.OUT ghi số lượng các phân số tối giản. Ví dụ: PSTG.INP PSTG.OUT 3 2 23 24 83 B. Một số bài toán thực tiễn. Bài 5. Để kỷ niệm ngày Quốc tế phụ nữ 8-3, công ty bánh kẹo Kinh Đô muốn tặng mỗi nữ nhân viên một phần quà là các loại bánh kẹo. Công ty đã chuẩn bị N loại bánh kẹo khác nhau. Mỗi loại có số gói khác nhau. Em hãy giúp Công ty chia số bánh kẹo đó thành những phần quà giống nhau sao cho số lượng phần quà là nhiều nhất. Dữ liệu vào: File văn bản CHIAQUA.INP gồm 2 dòng, dòng đầu chứa số nguyên dương N là số loại bánh kẹo, dòng thứ hai chứa N số nguyên dương a1, a2, …, a n. (ai là số gói bánh kẹo của loại thứ i). Dữ liệu ra: File văn bản CHIAQUA.OUT chứa 1 số nguyên là kết quả tìm được. Ví dụ 1: 13
CHIAQUA.INP CHIAQUA.OUT 2 2 64 Bài 6. Trong cuộc thi giải toán qua mạng internet mỗi học sinh đều có số điểm tích lũy riêng của mình. Số điểm tích lũy của mỗi học sinh là một số nguyên dương K (0 < K ≤ 2109). Đội tuyển của trường THCS Tài Năng có N học sinh tham gia dự thi (2 ≤ N ≤ 100). Tại buổi gặp mặt trước kỳ thi cấp tỉnh, thầy hiệu trưởng quyết định thưởng cho các học sinh trong đội tuyển Q triệu đồng, biết rằng điểm tích lũy của mỗi học sinh đều chia hết cho Q. Yêu cầu: Hãy tìm số nguyên dương Q lớn nhất. Dữ liệu vào: Cho trong file văn bản PT.INP có cấu trúc như sau: - Dòng 1: Ghi số nguyên dương N là số lượng học sinh. - Dòng 2: Ghi N số nguyên dương lần lượt là điểm tích lũy của N học sinh, các số được ghi cách nhau ít nhất một dấu cách. Dữ liệu ra: Ghi ra file văn bản PT.OUT theo cấu trúc như sau: - Dòng 1: Ghi số nguyên dương Q tìm được. Ví dụ: PT.INP PT.OUT 5 3 15 24 45 36 27 Bài 7. Trong một màn pháo hoa chào đón năm mới 2016 có N loại pháo hoa. Mỗi loại pháo hoa có màu sắc và hình dạng khác nhau sẽ được bắn lên theo những chu kỳ khác nhau. Tính từ khi bắt đầu màn pháo hoa, loại pháo hoa thứ i sẽ được bắn lên vào những giây chia hết cho i. Tuấn là một khán giả do điều kiện thời gian hạn hẹp chỉ có M giây để chiêm ngưỡng màn pháo hoa này, cậu ta muốn nhìn thấy càng nhiều loại pháo hoa được bắn lên cùng một lúc càng tốt. Bạn hãy tính xem Tuấn phải đợi ít nhất bao nhiêu giây trong thời gian cho phép của mình để đạt được điều cậu ta mong muốn. Dữ liệu vào: Trong tệp PHAOHOA.INP ghi hai số nguyên dương N, M (0
vào các thời điểm Ti ; 2xTi; 3xTi… (với i=1, 2,..N). Nếu đứng theo dõi sẽ thấy thời điểm tất cả các bóng đèn đều sáng. Ví dụ: Nếu có 2 đèn mà T1=4 thì tại các thời điểm 4, 8, 12, 20 … bóng 1 sẽ sáng, T2=6 thì các thời điểm 6, 12, 24, 30 … bóng đèn 2 sẽ sáng. Như vậy thời điểm 12 là thời điểm sớm nhất mà cả 2 bóng đèn đều cùng lóe sáng. Cho biết số lượng đèn N và các giá trị Ti, hãy xác định thời điểm sớm nhất mà tất cả N bóng đèn đều sáng. Dữ liệu vào: Trong tệp Dennhay.inp gồm có 2 dòng: Dòng đầu chứ số nguyên dương N (2
đổi x thành tích a. b (với a, b là các số nguyên dương) thì số a lớn nhất là số nào? Ví dụ: Với x = 72 ta có x = 72 =1. 72 =2. 18 =3. 8 =6. 2 . Khi đó số a lớn nhất là 6. Dữ liệu vào: Trong tệp cbh.inp ghi một số nguyên dương x (x≤1014). Dữ liệu ra: Trong tệp cbh.out số a lớn nhất cần tìm. Ví dụ: CBH.INP CBH.OUT 72 6 ------Hết----- 16