CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập – Tự do – Hạnh phúc
“PHƯƠNG PHÁP GIẢI CÁC BÀI TOÁN VỀ ƯỚC CHUNG LỚN NHẤT
VÀ BỘI CHUNG NHỎ NHẤT TRONG BỒI DƯỠNG HỌC SINH GIỎI
TIN HỌC LỚP 8, 9”
Quảng Bình, tháng 11 năm 2017
CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập – Tự do – Hạnh phúc
“PHƯƠNG PHÁP GIẢI CÁC BÀI TOÁN VỀ ƯỚC CHUNG LỚN NHẤT
VÀ BỘI CHUNG NHỎ NHẤT TRONG BỒI DƯỠNG HỌC SINH GIỎI
TIN HỌC LỚP 8, 9”
Họ tên: Vương Công Quang
Chức vụ: Giáo viên
Đơn vị công tác: Trường THCS Phú Thủy
Quảng Bình, tháng 11 năm 2017
1
MỤC LỤC
MỤC LỤC ............................................................................................................................ 1
MỞ ĐẦU ............................................................................................................................... 2
1. Lý do chọn đề tài ................................................................................................ 2
2. Điểm mới sáng kiến ............................................................................................ 3
3. Phạm vi nghiên cứu ............................................................................................ 3
NỘI DUNG ........................................................................................................................... 3
1. Thực trạng nội dung cần nghiên cứu ................................................................ 3
1.1. Cơ sở khoa học về ước chung lớn nhất và bội chung nhỏ nhất: ................................ 3
1.2. Thực trạng dạy học: ........................................................................................ 4
2. Các giải pháp thực hiện...................................................................................... 5
2.1. Hướng dẫn cho học sinh nắm lại kiến thức cơ bản về ước chung, ước chung lớn
nhất, bội chung nhỏ nhất của hai hay nhiều số ................................................................ 5
2.2. Giới thiệu các thuật toán tìm ước chung lớn nhất và bội chung nhỏ nhất cho học sinh
....................................................................................................................................... 6
2.3. Ví dụ về kết hợp câu lệnh lặp và mảng một chiều để giải một số bài toán về Ước
chung lớn nhất và Bội chung nhỏ nhất ............................................................................ 8
2.4. Áp dụng giải một số bài toán tìm ước chung, ước chung lớn nhất, bội chung nhỏ
nhất .............................................................................................................................. 10
2.5. Hiệu quả của đề tài: ............................................................................................... 14
KẾT LUẬN ........................................................................................................................ 17
1. Ý nghĩa của thuật toán tìm UCLN, BCNN ...................................................... 17
2. Kiến nghị. ....................................................................................................... 18
TÀI LIỆU THAM KHẢO .................................................................................................... 19
2
MỞ ĐẦU
1. Lý do chọn đề tài
Ngày nay, với sự phát triển nhảy vọt của công nghệ thông tin và Tin học đã
làm thay đổi mọi mặt của đời sống xã hội, thúc đẩy sự phát triển của giáo dục,
kinh tế, chính trị và mọi mặt đời sống xã hội. Chính vì xác định được tầm quan
trọng đó nên môn Tin học được đưa vào giảng dạy ở tất cả các lớp của các cấp
học, đặc biệt việc dạy học lập trình căn bản được chú trọng và áp dụng cho học
sinh khối 8 trở lên. Đây là môn học mới mẻ nhưng rèn luyện cho học sinh tính
tư duy, làm việc logic, có tính sáng tạo, biết phân tích, tổng hợp và giúp giải
quyết được nhiều công việc xuất phát từ thực tiễn cuộc sống.
Mặc dù vậy, qua thực tế chung thì các học sinh khi học môn Tin học 8 nói
chung và BD HSG Tin học 8 và 9 nói riêng đều cảm thấy khó khăn trong nắm
bắt kiến thức hoặc khó khăn trong việc tư duy thuật toán, giải quyết vấn đề, cách
giải một số bài toán cơ bản còn rập khuôn chưa mang tính sáng tạo. Nguyên
nhân những vấn đề trên là do môn học lập trình còn mới mẻ với các em học
sinh; các thuật ngữ, các câu lệnh mang tính kỹ thuật, các từ khóa lập trình, giao
diện phần mềm đều là tiếng Anh nên việc tiếp xúc và làm quen với học sinh còn
khó khăn và bỡ ngỡ. Đa số các em chưa có kinh nghiệm trong việc thể hiện
thuật toán, tìm hiểu chương trình nên việc viết chương trình còn đơn giản hoặc
không hiểu được chương trình người khác viết vì vậy khả năng nâng cao sự hiểu
biết về các cách giải bài toán cũng như sự học hỏi thuật toán còn hạn chế.
Trong chương trình khung bồi dưỡng Tin học 8 của Phòng giáo dục, có bài
tập về số học gắn liền với Toán học phần Đại số lớp 6, 7, 8, một số bài toán
trong đó được định nghĩa lại gắn liền với thực tiễn cuộc sống hơn. Để giải quyết
một bài toán xuất phát từ thực tiễn cuộc sống đòi hỏi học sinh cần có kỹ năng
phân tích bài toán, rút ra cách giải cũng là rèn luyện cách phân tích tổng hợp
trong tư duy để có thể đưa bài toán thực tiễn trở thành bài toán dạng số học đơn
thuần và có thể giải quyết nó. Vậy nên giáo viên cần dạy cho học sinh phát triển
tư duy về quy trình giải một bài toán, phát triển thuật toán và áp dụng kiến thức
tổng hợp về câu lệnh có cấu trúc và kiểu dữ liệu để viết các chương trình giải
các bài toán. Theo kinh nghiệm bản thân, tôi nhận thấy dạng bài ước chung lớn
nhất, bội chung nhỏ nhất phù hợp để hướng dẫn học sinh hiểu cách chuyển từ
kiến thức phần số học sang áp dụng giải các bài toán trong lập trình Pascal từ cơ
bản đến nâng cao, từ bài toán định nghĩa đơn giản đến vận dụng các câu lệnh có
cấu trúc và các kiểu dữ liệu để giải các bài khó nên tôi đã đúc rút lại thành sáng
kiến kinh nghiệm có thể áp dụng giảng dạy ngay tại đơn vị, đó là: “Phương
pháp giải các bài toán về Ước chung lớn nhất và Bội chung nhỏ nhất trong
bồi dưỡng học sinh giỏi Tin học lớp 8, 9”.
3
2. Điểm mới sáng kiến
- Giáo viên có thể chuyển tải kiến thức lý thuyết trong số học dạng bài về
ước chung lớn nhất, bội chung nhỏ nhất thành bài toán lập trình trong Pascal,
phát triển vận dụng bài toán từ định nghĩa kết hợp với câu lệnh có cấu trúc, kiểu
dữ liệu mảng để tạo thành những bài toán nâng cao đòi hỏi học sinh có kĩ năng
vận dụng tổng hợp các kiến thức đã học để giải.
- Hình thành được cho học sinh phương pháp giải quyết các dạng bài toán
ước chung lớn nhất, bội chung nhỏ nhất từ cơ bản đến phức tạp.
- Học sinh hình thành các kĩ năng vận dụng kiến thức để phân tích bài toán,
giải bài toán một cách có hệ thống.
- Giải pháp mới này ngắn gọn và dễ hiểu, phù hợp với học sinh lớp 8 trở
lên, có thể ứng dụng trong dạy học đại trà và bồi dưỡng học sinh giỏi Tin học
của bậc học.
3. Phạm vi nghiên cứu
Giải pháp ““Phương pháp giải các bài toán về Ước chung lớn nhất và
Bội chung nhỏ nhất trong bồi dưỡng học sinh giỏi Tin học lớp 8, 9” được
nghiên cứu tại đơn vị công tác trong năm học 2015 – 2016 và áp dụng trong
giảng dạy với đội tuyển HSG Tin học 8 trong năm học 2016 – 2017. Qua áp
dụng giải pháp này, học sinh hiểu được nhiều cách tiếp cận hơn đối với một bài
toán, hình thành được cách giải đối với dạng bài tập dãy số cho trước nhờ đó
học sinh tự tin tìm hiểu và đam mê khám phá học hỏi hơn, nhờ đó góp phần
nâng cao chất lượng giảng dạy Bồi dưỡng HSG bộ môn Tin học 8 nói riêng và
Tin học nói chung.
NỘI DUNG
1. Thực trạng nội dung cần nghiên cứu
1.1. Cơ sở khoa học về ước chung lớn nhất và bội chung nhỏ nhất:
1.1.1 Tìm ước chung lớn nhất
Trong Toán học, ước chung lớn nhất của hai số nguyên dương được tính
bằng thuật toán Euclid (thuật toán Euclid do nhà Toán học Euclid viết ra trong
cuốn sách toán nổi tiếng Elements từ khoảng năm 300 trước Công Nguyên) bằng
hai phương pháp: phương phương pháp trừ và phương pháp chia lấy số dư
Phương pháp trừ: Nguyên lý chính của thuật toán là ước số chung lớn nhất
của một cặp số không thay đổi với hiệu của hai số đó. Ví dụ như ƯSCLN của
252 và 105 chính bằng ƯSCLN của 147 (= 252 − 105) và 105. Vì số lớn hơn
trong cặp số bị giảm giá trị nên việc lặp đi lặp lại thuật toán này giúp tạo ra
những số ngày càng nhỏ và đến một lúc nào đó quá trình này sẽ kết thúc — khi
