SKKN 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Ộ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 
 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 
 1 
 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 
 3 
 rút ra công thức và viết chương trình chạy, một số em viết được chương trình 
giải nhưng chỉ tìm được ước chung lớn nhất của hai số. Đề khảo sát học sinh 
giỏi lớp 8 sau khi dạy xong các chuyên đề lý thuyết và bài tập số học như sau: 
 Đề ra: Dùng ngôn ngữ lập trình Free Pascal hoặc Turbo Pascal để giải các 
bài toán sau, thời gian làm bài 120 phút. 
 Câu 1 (3 điểm): Nhập vào hai số nguyên dương a và b (0 < a,b < 32000). 
Tính tổng các ước chung của hai số đó và in ra màn hình tổng đó. 
 Câu 2 (3 điểm): Nhập vào hai số nguyên a và b (b≠ 0, 0<a,b<32000). In ra 
phân số a dưới dạng rút gọn phân số tối giản. 
 b
 Câu 3: (4 điểm): Em hãy nhập vào N số nguyên dương Ai (0 < N < 200; 0 
<Ai < 32000), in ra màn hình ước chung lớn nhất của các số nguyên đó. 
 Kết quả thống kê như sau: 
 Giỏi Khá TB Yếu 
 Đối 
 SLHS 
 tượng 
 SL % SL % SL % SL % 
 HSG 8 6 0 0 2 33.3 2 33.3 2 33.3 
 Kết quả kiểm tra cho thấy số học sinh yếu làm được câu 1 nhưng chưa nắm 
được cách giải câu 2 và câu 3, chỉ mới viết được các câu lệnh khai báo biến 
nhập vào dữ liệu, các câu lệnh xử lý chính chưa đúng và chưa hoàn chỉnh, chưa 
hoàn thành được yêu cầu bài. Những học sinh đạt trung bình thì hoàn thành câu 
1 và ở câu 2 đã khai báo, nhập được dữ liệu vào, viết được các lệnh để tìm ước 
chung lớn nhất của hai số nhưng do không gán giá trị trung gian của a và b trong 
quá trình tìm ước nên sau khi tìm ước xong thì giá trị a và b đã bị thay dổidẫn 
đến kết quả bị sai, còn câu 3 chưa tìm được cách để tìm được ước chung lớn 
nhất của dãy số và chương trình chưa chạy được. Đối với học sinh đạt kết quả 
khá thì viết được chương trình câu 1 và 2 hoàn chỉnh, chạy được và cho kết quả 
là ước chung lớn nhất của hai số, chưa vận dụng được kiến thức câu lệnh lặp và 
mảng để giải quyết bài toán câu 3. Vì vậy, cần phải hướng dẫn cho học sinh nắm 
được cách giải quyết bài toán theo hướng đơn giản hơn, hiệu quả hơn, từ cơ bản 
đến nâng cao. 
2. Các giải pháp thực hiện 
 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 
 + Nhược điểm: Nếu a hoặc b là số 0 thì đoạn lệnh trên sẽ gây lặp vô hạn 
lần, đồng nghĩa là không tìm được ước chung lớn nhất; ngoài ra thuật toán này 
thực hiện còn khá nhiều lần (lâu) nếu a và b chênh lệch giá trị lớn. 
 + Phương án khắc phục: Kiểm tra các số a và b phải lớn hơn 0 trước khi 
tìm ước chung lớn nhất. 
 - Thuật toán 2: Phương pháp chia lấy số dư 
 While b 0 do begin r := a mod b ; a := b; b := r ; end; 
 Ucln := a ; {Ước chung lớn nhất là a} 
 + Ưu điểm: Tìm được ước chung lớn nhất của hai số nguyên bao gồm một 
trong hai số là số 0. Tốc độ tìm nhanh hơn thuật toán 1 nêu trên vì vậy thuật toán 
này thường được sử dụng để tìm ước chung lớn nhất của hai số nguyên. 
 + Nhược điểm: Nếu cả hai số a và b đều là số 0 thì kết quả tìm ước chung 
lớn nhất cho giá trị là số 0. Nhưng theo định nghĩa về ước thì số 0 không có ước 
lớn nhất nên sẽ không tìm được ước chung lớn nhất của hai số 0. 
 + Phương án khắc phục: Kiểm tra đầu vào các số a và b phải có ít nhất 
một số khác số 0 rồi mới tìm ước chung lớn nhất. 
2.2.3. Thuật toán tìm bội chung nhỏ nhất của hai số 
 Để tìm bội chung nhỏ nhất của hai số nguyên dương ta tìm ước chung lớn 
nhất của hai số đó, sau đó lấy tích của hai số đó rồi chia lấy phần nguyên cho 
ước chung lớn nhất tìm được. Gọi BCNN(a,b) và UCLN(a,b) là bội chung nhỏ 
nhất của a và b và ước chung lớn nhất của a và b thì ta có: BCNN(a,b) = a*b div 
UCLN(a,b). Đoạn lệnh chính tìm bội chung nhỏ nhất của hai số nguyên dương a 
và b là: 
 x := a; y := b ; 
 While y 0 do begin r := x mod y ; x := y; y := r ; end; 
 Ucln := x; {Ước chung lớn nhất là x} 
 Bcnn := a*b div ucln ; 
 Lưu ý rằng cần kiểm tra các số a và b phải nguyên dương trước bởi vì nếu a 
hoặc b là số 0 thì không tìm được bội chung nhỏ nhất bởi theo định nghĩa số 0 
không có bội. 
2.2.4. Thuật toán tìm ước chung lớn nhất và bội chung nhỏ nhất của nhiều 
số 
 7 
 Var tên mảng : array[..] of ; 
 Ví dụ: Var a : array[1..200] of integer; 
 Tu, mau : array[1..200] of longint ; 
 Đối với câu lệnh lặp, thông thường sử dụng câu lệnh lặp với số lần biết 
trước bởi vì các bài toán thường cho biết trước số phần tử của dãy số, dãy phân 
số. Có hai dạng câu lệnh lặp với số lần biết trước, đó là: 
 For := to do ; 
 For := downto do ; 
 Việc sử dụng câu lệnh lặp dùng để nhập số lượng phần tử hoặc dựa vào quy 
luật của dãy số mà đưa các số, tử hoặc mẫu của các phân số lưu vào mảng sau 
đó tìm ước chung lớn nhất và bội chung nhỏ nhất theo yêu cầu của bài. 
 1 3 5 2n 1
 Ví dụ bài toán: Cho S ... với n là số nguyên dương được 
 2 4 6 2n
nhập vào từ bàn phím và 0< n ≤200. 
 Yêu cầu: Tính và rút gọn S thành phân số dạng tối giản A với A và B là 
 B
hai số nguyên. 
 Phân tích bài toán: Các phân số trong phép toán trên có quy luật chung, tử 
số luôn là các số lẻ đại diện bằng công thức 2n-1 và mẫu luôn là các số chẵn, đại 
diện bằng công thức là 2n. Dãy số có n phân số nên ta sẽ lặp lại n phép cộng các 
phân số với nhau nên trong chương trình sẽ dùng câu lệnh lặp với số lần biết 
trước để viết đoạn lệnh tính toán. Trong toán học, các bước để tính toán và rút 
gọn tổng các phân số được thực hiện như sau: 
 + Bước 1: Tìm mẫu chung của các mẫu số. 
 + Bước 2: Lấy mẫu chung chia cho các tử riêng để lấy nhân tử phụ, sau đó 
lấy nhân tử phụ nhân với tử riêng tạo thành tử mới của mỗi phân số 
 + Bước 3: Tính tổng các tử và giữ nguyên mẫu 
 + Bước 4: Tìm ước chung lớn nhất của tử và mẫu 
 + Bước 5: Rút gọn cả tử và mẫu bằng cách cùng chia cho ước chung lớn 
nhất ta có phân số tối giản cần tìm. 
 Áp dụng phương pháp đó để giải bài toán này trong lập trình, trình tự các 
bước vẫn giữ nguyên. Việc tìm mẫu chung chính là tìm bội chung nhỏ nhất của 
các mẫu, để tìm bội chung nhỏ nhấ ta phải tìm ước chung lớn nhất các mẫu, 
trong trường hợp này để tránh viết nhiều đoạn lệnh tìm ước chung lớn nhất và 
bội chung nhỏ nhất ta nên viết chương trình con tìm ước chung lớn nhất để sử 
dụng cho gọn trong chương trình. Hơn nữa, ta cần lưu các tử và mẫu phân số lại 
để tính toán thực hiện ở các bước 1 đến bước 3 nên ta dùng mảng để lưu các tử 
và mẫu theo từng cặp chỉ số thứ tự ở hai mảng khác nhau có cùng số lượng phần 
tử. 
 9