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
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
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ế.
2
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”.
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
cặp số còn lại hai số bằng nhau (nếu quá trình được thực hiện thêm một bước nữa, sẽ có một trong hai số trở thành số 0).
Phương pháp chia lấy số dư: Với hai số nguyên dương ban đầu có thể tạo ra một cặp số nguyên dương mới bao gồm số nhỏ hơn và phần dư của phép chia hai số ban đầu. Quá trình được tiếp tục cho đến khi hai số trong cặp bằng nhau, giá trị lúc đó sẽ trở thành ước số chung lớn nhất của cặp số ban đầu.
Ví dụ: Tính ước số chung lớn nhất của 91 và 287.
Trước hết lấy 287 (số lớn hơn trong 2 số) chia cho 91:
287 = 91*3 + 14 (91 & 14 sẽ được dùng cho vòng lặp kế)
Nhận xét: bất kỳ số nào chia hết bởi 287 và 91 cũng sẽ chia hết bởi 287 - 91*3 = 14. Tương tự, số chia hết bởi 91 và 14 cũng chia hết bởi 91*3 + 14 = 287. Do đó, ƯSCLN(91,287) = ƯSCLN(91,14). Bài toán trở thành tìm ƯSCLN(91,14). Lặp lại quy trình trên cho đến khi phép chia không còn số dư như sau:
91 = 14*6 + 7 (14 & 7 sẽ được dùng cho vòng lặp kế)
14 = 7*2 (không còn số dư, kết thúc, nhận 7 làm kết quả)
Cuối cùng ta có: 7 = ƯSCLN(7,0) = ƯSCLN(14,7) = ƯSCLN(91,14) =
ƯSCLN(287,91).
1.1.2 Tìm bội chung nhỏ nhất (BCNN)
Tìm bội chung nhỏ nhất của hai số nguyên a và b bằng công thức:
BCNN(a,b) = (a * b) div UCLN(a,b)
Ví dụ: BCNN(4,6) = 4*6 div UCLN(4,6) = 24 div 2 = 12.
1.1.3 Tìm UCLN, BCNN của nhiều số.
Để tìm ước chung lớn nhất và bội chung nhỏ nhất của hai hay nhiều số, ta
sử dụng công thức truy hồi:
UCLN(a,b,c) = UCLN(UCLN(a,b),c)
BCNN(a,b,c) = BCNN(BCNN(a,b),c)
Ví dụ: UCLN(4,6,10) = UCLN(UCLN(4,6),10) = UCLN(2,10)=2
BCNN(4,6,10)=BCNN(BCNN(4,6),10)=BCNN(12,10)=60
1.2. Thực trạng dạy học:
Năm học 2015-2016 bản thân tôi được giao phần hành bồi dưỡng học sinh giỏi Tin học 8. Qua trực tiếp giảng dạy và khảo sát phần số học, kết quả cho thấy đa số học sinh còn lúng túng trong phân tích bài toán, tìm thuật toán, cách
4
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 dưới dạng rút gọn phân số tối giản.
b phân số Câu 3: (4 điểm): Em hãy nhập vào N số nguyên dương Ai (0 < N < 200; 0 Giỏi Khá TB Yếu SLHS Đối
tượng SL % SL % SL % SL % HSG 8 6 0 0 2 33.3 2 33.3 2 33.3 Kết quả thống kê như sau: 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. 5 Trong phần Số học lớp 6 có bài về ước và bội, ước chung, ước chung lớn nhất và bội chung nhỏ nhất, theo đó các định nghĩa được nêu ra như sau: - Ước và bội: nếu số nguyên a chia hết cho số nguyên d thì số d được gọi là
ước của số nguyên a, a được gọi là bội của d. Số 0 không có bội số và mọi số
nguyên đều là ước số của số 0. - Ước chung, ước chung lớn nhất: Số nguyên dương d lớn nhất là ước của
cả hai số nguyên a, b được gọi là ước số chung lớn nhất (ƯCLN) của a và b.
Trong trường hợp cả hai số nguyên a và b đều bằng 0 thì chúng không có ƯCLN
vì khi đó mọi số tự nhiên khác không đều là ước chung của a và b. Nếu chỉ một
trong hai số a hoặc b bằng 0, số kia khác 0 thì ƯCLN của chúng bằng giá trị
tuyệt đối của số khác 0. 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 2.2.1. Thuật toán tìm ước chung của hai số: Với a và b là hai số nguyên không âm thì xảy ra ba trường hợp: Trường hợp 1: cả a và b là số 0 thì danh sách các ước chung không liệt kê được hết bởi vì mọi số tự nhiên lớn hơn 0 là ước của số 0. Trường hợp 2: nếu a hoặc b có một số là số 0 thì ước chung của hai số là các ước của số khác 0. Trường hợp 3: cả hai số nguyên dương thì xét tìm các ước nằm trong đoạn
từ số 1 đến một nữa của số nhỏ hơn, cụ thể đoạn lệnh in ra các ước chung của a
và b như sau: If a > b then min :=b else min :=a ; For i:= 1 to min div 2 do if ((a mod i = 0) and (b mod i = 0)) then write(i:3); 6 + 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; 7 Để làm việc trên một dãy số hoặc nhiều số, ta lưu các số đó vào mảng một
chiều sau đó sử dụng công thức truy hồi để tìm ước chung lớn nhất và bội chung
nhỏ nhất theo cách sau: UCLN(a,b,c) = UCLN(UCLN(a,b),c) BCNN(a,b,c) = BCNN(BCNN(a,b),c) Cụ thể, dùng câu lệnh lặp và viết một hàm tìm ước chung lớn nhất của hai
số và hàm tìm bội chung nhỏ nhất của hai số, sau đó dùng công thức truy hồi
như sau: Function ucln(a,b: integer): integer; begin 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} end; function bcnn(a,b : integer):integer; begin Bcnn := a*b div ucln(a,b) ; end; Ucmax := a[1]; bcmax:=a[1]; For i:=2 to N do begin ucmax := ucln(ucmax,a[i]); bcmax:=bcnn(bcmax,a[i]); 8 Var a : array[1..200] of integer;
Tu, mau : array[1..200] of longint ; Var tên mảng : array[ 1 2 ... S For 1
2 3
4 n
2
n 5
6
nhập vào từ bàn phím và 0< n ≤200. Ví dụ bài toán: Cho với n là số nguyên dương được A với A và B là
B Yêu cầu: Tính và rút gọn S thành phân số dạng tối giản 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 9 Chương trình như sau: (Turbo Pascal) số này bằng nhau. Đây rõ ràng là số ước chung lớn nhất của chiều dài và rộng.
Từ đây ta quy về bài toán tìm ước chung lớn nhất của hai số nguyên R và D. Đoạn chương trình sau cho phép tìm ra khoảng cách lớn nhất của hai cây cần tìm: Bài toán 2: Một tấm bìa hình chữ nhật có kích thước X cm và Y cm (0 Yêu cầu: - Tính độ dài lớn nhất (đơn vị cạnh là cm) của cạnh hình vuông mà Long cắt được. - Tính số hình vuông có cạnh lớn nhất mà Long cắt được.
Phân tích bài toán: Tương tự bài toán 1, để cắt tấm bìa thành các hình
vuông nhỏ thì ta cần tìm được một số nguyên A sao cho cả X và Y đều chia hết,
số nguyên A đó chính là độ dài cạnh của hình vuông được cắt ra. Số nguyên A
là ước của X và cũng là ước của Y. Và để có cạnh hình vuông cắt ra lớn nhất thì
số A cần tìm đó phải là lớn nhất trong các ước chung của X và Y. Số hình vuông
thu được được tính bằng tích của (X div A)*(Y div A) Chương trình tham khảo như sau:
Program bia_hinh_vuong ;
Var X, Y, A, tg1, tg2 : integer ;
Begin
Write(‘Nhap vao chieu dai X: ‘); readln(X); tg1 := X;
Write(‘Nhap vao chieu rong Y: ‘); readln(Y); tg2 := Y;
While Y <> 0 do begin A := X mod Y; X := Y; Y := A ; end;
Writeln(‘Do dai lon nhat cua hinh vuong la: ‘ , X, ‘ cm’);
Writeln(‘So hinh vuong thu duoc la: ‘, (tg1 div X)*(tg2 div X));
End. 11 dùng thuật toán Euclid để tìm ước chung lớn nhất dãy số và bội chung nhỏ nhất
dãy số. Ta thấy rằng: ước chung lớn nhất của dãy số là ước của một số tiếp theo
trong dãy với ước chung lớn nhất của hai số đã tìm trước đó; bội chung nhỏ nhất
của dãy là bội chung của số tiếp theo trong dãy với số là bội chung nhỏ nhất của
hai số trước đó. Chương trình tham khảo sau tìm ước chung lớn nhất và bội chung nhỏ nhất dãy số: 12 Yêu cầu: Nhập vào số nam và nữ từ bàn phím, tìm số cách chia số nam và
nữ vào các lớp đều nhau? Với cách chia nào thì mỗi lớp có số học sinh là ít
nhất?
Phân tích bài toán: Việc chia học sinh thành các lớp sao cho số học sinh
các lớp giống nhau, số nam bằng nhau, nữ bằng nhau chính là tìm các ước chung
của nam và nữ, tổng số các ước chung của nam và nữ chính là tổng số cách chia
lớp. Cách chia để số học sinh ít nhất trong mỗi lớp chính là chia số học sinh
thành nhiều lớp nhất có thể. Số học sinh nhiều nhất trong mỗi lớp chính là ước
chung lớn nhất của số học sinh nam và số học sinh nữ. Từ đây ta chỉ việc đếm số
ước chung của số nam, nữ và tìm ước chung lớn nhất của nam và nữ. Chương trình tham khảo:
Program chia_lop_nam_nu ;
Var Xy, XX, dem, min : word ;
Begin
End. 1 x x 3 x 5 x 1 S
...
2
6 2
n
n
2
4
dương và 0 A với A và b là
B 13 + 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. Ta có chương trình tham khảo sau:
Program tong_cac_phan_so ;
Var
function ucln(a,b: integer): integer;
var r : integer;
begin
end;
function bcnn(a,b: integer): longint;
begin
bcnn := a ;
end;
Begin
End. 14 kiến thức lý thuyết vừa vận dụng làm bài tập chuyên đề ước chung lớn nhất và
bội chung nhỏ nhất thành thạo. Không những thế, học sinh hiểu biết cách vận
dụng kiến thức tổng hợp để giải một bài toán từ cơ bản đến nâng cao. Minh chứng cho điều đó, tôi đã kiểm tra đội tuyển HSG lớp 8 sau khi dạy xong chuyên đề trong năm học 2016 – 2017 như sau: Đề bài: Hãy sử dụng ngôn ngữ lập trình Pascal để viết chương trình giải các bài toán sau: Câu 1 (4 điểm): Cho một dãy N số nguyên dương Ai bao gồm các số nguyên chẵn và lẽ Ai (0< N <1000; 0 n Q 2017 ...
Yêu cầu: Hãy nhập vào dãy N số nguyên Ai và cho biết ước chung lớn nhất của các số lẽ và ước chung lớn nhất của các số chẵn trong dãy đó. 1
x 21
2
x
2
2
1 21
..
2
n
x Câu 2 (6 điểm): Cho với 0 10, 0< x ≤10. Đáp án tham khảo 15 Giỏi Khá TB Yếu SLHS Đối
tượng SL % SL % SL % SL % 0 0 0 HSG 8 6 3 50.0 3 50.0 0 16 nhiều số, nhận biết dãy số có quy luật, cách tổng hợp thành công thức chung dãy
số. Đối với học sinh đạt kết quả khá thì kết quả làm được câu 1, câu hai viết
được chương trình nhưng chỉ chạy được với các bộ test nhỏ, thuật toán chưa tối
giản, thời gian giải bài toán lâu, các câu lệnh trình bày rối rắm. Đối với học sinh
đạt kết quả giỏi thể hiện được trọn vẹn bài làm, chương trình trình bày rõ ràng,
ngắn gọn và thời gian thực hiện đáp ứng được yêu cầu của bài toán. Như vậy, từ những kỹ năng thực hành giải bài tập về dạng tìm ước chung
lớn nhất, bội chung nhỏ nhất và các bài toán dãy số có quy luật cho trước ban
đầu còn hạn chế, sau khi được áp dụng những giải pháp trên chất lượng học tập
của học sinh cải thiện vượt bậc. Chứng tỏ những phương pháp trên đã có hiệu
quả và không những thế, minh chứng là sự hứng thú trong học tập và chủ động
tích cực trong các tiết học lập trình Tin học. KẾT LUẬN 1. Ý nghĩa của thuật toán tìm UCLN, BCNN Mặc dù mới được nghiên cứu và áp dụng nhưng từ những kết quả đạt
được cho thấy hướng nghiên cứu là khả dụng. Sử dụng một dạng bài vừa giải
quyết các kiến thức riêng vừa kết nối các kiến thức để cho học sinh có thể giải
các bài toán từ đơn giản đến phức tạp. Đồng thời tăng cường kỹ năng phân tích
bài toán, tổng hợp được mấu chốt bài toán và đưa ra các phương án giải quyết
hợp lý nhờ đó kiến thức và kĩ năng giải lập trình ngày càng tăng lên, tốt hơn
giúp các em có thể học được các kiến thức cao hơn sau này. Để có được phương pháp dạy học phù hợp với kiểu bài, với tư duy của
học sinh, giáo viên phải có một quá trình tìm tòi, suy ngẫm về đổi mới phương
pháp và thử nghiệm trên lớp mới có thể định hình được phương pháp tối ưu cho
đối tượng học sinh mình giảng dạy. Từ một bài học đơn giản đến phức tạp, giáo
viên cần có phương pháp dẫn dắt hữu hiệu, phù hợp với đối tượng thì học sinh
mới tiếp thu và vận dụng. Tránh tình trạng áp đặt suy nghĩ là kiến thức làm cho
học sinh không thấy được sự đa dạng trong cách giải, sự hạn chế của thuật toán
và gây nhàm chán, nặng nề cho học sinh. 17 2. Kiến nghị. 2.1. Giáo viên: Tại đơn vị, đa số học sinh đều có hoàn cảnh kinh tế gia đình khó khăn,
việc tiếp cận với máy tính và học Tin học còn hạn chế, chủ yếu là từ Nhà
trường. Vậy nên giáo viên trực tiếp giảng dạy cần có kế hoạch dạy học sát đối
tượng học sinh và đồng thời áp dụng nhiều phương pháp dạy học sáng tạo đổi
mới để qua đó kích thích tính tự học, tự sáng tạo của học sinh thông qua các bài
giảng có ví dụ thực tiễn, hình ảnh minh họa, tính liên hệ, so sánh, và thực hành
kiểm chứng, … Giáo viên cần tìm tòi hiểu sâu từng nội dung bài học để qua đó
đưa ra được những hướng dẫn mang tính kích thích sự tìm tòi, tiếp cận bài học
của học sinh để phát huy được tính sáng tạo, khám phá của học sinh; đồng thời
cần tăng cường dự giờ trao đổi kinh nghiệm giảng dạy để học hỏi phương pháp
từ đồng nghiệp và nâng cao năng lực tự học, tự nghiên cứu để tích lũy trau dồi
thêm kiến thức chuyên môn của mình. 2.2. Nhà trường: Tổ chuyên môn và Nhà trường tăng cường dự giờ thăm lớp và góp ý, bồi
dưỡng thêm các giáo viên trẻ về kiến thức cũng như phương pháp dạy học để
nâng cao năng lực dạy học cho giáo viên. Bổ sung hằng năm các tài liệu, sách
phục vụ dạy học môn Tin học bởi vì hiện tại các sách và tài liệu liên quan môn
Tin học ở thư viện các trường còn khá hạn chế 2.3. Phòng giáo dục và cấp trên: Hội đồng bộ môn các cấp định kỳ hằng năm tập huấn bồi dưỡng chuyên
môn cho giáo viên nhằm nâng cao kiến thức, kĩ năng, phương pháp dạy học để
áp dụng vào dạy học ở đơn vị, nâng cao chất lượng dạy học môn Tin học nói
riêng và dạy học nói chung.
Trên đây là một vài kinh nghiệm nhỏ của tôi trong việc giảng dạy bộ môn
Tin học lớp 8 và bồi dưỡng học sinh giỏi Tin học 8, 9 mà qua mấy năm giảng
dạy tôi đã tìm tòi, suy nghĩ và viết ra. Chắc chắn rằng vẫn còn nhiêu thiếu sót
trong lập luận, trong phương pháp giảng dạy bộ môn và cách trình bày. Tôi rất
mong được sự góp ý của đồng nghiệp, bạn bè, các thầy, các cô để bản sáng kiến
được hoàn thiện hơn! 18 TÀI LIỆU THAM KHẢO - Cấu trúc dữ liệu và giải thuật – Lê Minh Hoàng - Một số phương pháp giải bài toán trong tin học – Lê Thủy Thạch - Giáo trình ngôn ngữ Pascal – Nhà xuất bản giáo dục - Cấu trúc dữ liệu và giải thuật – Đỗ Xuân Lôi - Ngôn ngữ lập trình Turbo Pascal – Quách Tuấn Ngọc - Tài liệu tập huấn đổi mới phương pháp dạy học Tin học – Phòng GD&ĐT Lệ Thủy 19 - Mạng Internet.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ố
Nhận xét: lấy mốc tìm là một nửa số nhỏ hơn giúp rút ngắn thời gian tìm
ước chung của hai số.
2.2.2. Thuật toán tìm ước chung lớn nhất của hai số
- Thuật toán 1: Phương pháp trừ
Với a và b là hai số nguyên ta có đoạn lệnh chính tìm UCLN là
While a <> b do if a > b then a := a – b else b := b – a ;
Ucln := a ; {Ước chung lớn nhất là a hoặc b}
+ Ưu điểm: Tìm được ước chung của các số nguyên dương
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ố
end;
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
Việc kết hợp câu lệnh có cấu trúc là câu lệnh lặp và kiểu dữ liệu mảng một
chiều xảy ra khi bài toán tìm ước chung lớn nhất và bội chung nhỏ nhất của một
dãy số hoặc dãy phân số, phân thức cho trước. Sử dụng mảng một chiều để lưu
các số vào mảng và dùng câu lệnh lặp để duyệt mảng mới xử lý.
Để sử dụng mảng ta khai báo mảng ở phần khai báo, nếu bài toán là dãy số
thì chỉ cần khai báo một mảng chứa dãy số, nếu bài toán là dãy phân số thì cần
khai báo hai mảng để chứa tử và mẫu của các phân số. Cú pháp khai báo mảng
như sau:
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ử.
Program Rut_gon_day_so ;
Var tu, mau : array[1..200] of integer ;
i, N: byte ;tem, A, B : longint;
function tim_ucln(x, y : integer): integer;
var r : longint ;
begin
while y <>0 do begin r := x mod y ; x := y; y := r; end;
Tim_ucln := x;
end;
function bcnn(a,b: integer): longint;
bcnn:= bcnn*b div ucln(a,b);
begin
bcnn := a ;
end;
For i:= 1 to N do begin tu[i]:= 2*i-1 ; mau[i] := 2*i ; end;
Begin
Write(‘ nhap vao so N: ‘); readln(N);
{ Đưa tất cả các tử và mẫu vào hai mảng Tu và Mau}
{Tìm mẫu chung của các phân số}
tu[i] := (B div mau[i])*tu[i] ;
A := A + tu[i];
end;
B := mau[1] ;
For i:= 2 to N do B := bcnn(B ,mau[i]);
A := 0;
For i:=1 to N do begin
tem:= ucln(A, B);
A := A div tem;
B := B div tem ;
Writeln(‘Tong phan so duoc rut gon toi gian la:: ‘, A,’/’,B);
End.
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
Bài toán 1: Vườn trường hình chữ nhật có chiều dài D mét, rộng R mét (R, D là
các số nguyên dương). Nhà trường định trồng cây xung quanh vườn (mỗi góc có
1 cây) sao cho khoảng cách giữa 2 cây một bằng nhau.
Yêu cầu: Nhập vào D và R là các số nguyên dương từ bàn phím
(0
Phân tích bài toán: Vì chiều dài và rộng sân trường có kích thước khác
nhau nên để chia được khoảng cách lớn nhất giữa hai cây bằng nhau trên đường
viền bao quanh trường ta cần tìm một số lớn nhất mà khi lấy chiều dài chia cho
số đó được một số nguyên, lấy chiều rộng chia số đó cũng là một số nguyên, hai
10
Program Tim_khoang_cach ;
Var R, D, kc : integer ;
Begin
Write(‘Nhap vao chieu dai D: ‘); readln(D);
Write(‘Nhap vao chieu rong R: ‘); readln(R);
While R <> 0 do begin kc := D mod R; D := R; R := kc ; end;
Writeln(‘Khoang cach lon nhat giua hai cay la: ‘ , D, ‘ met’);
End.
Yêu cầu: Nhập vào dãy số Ai. Tìm ước chung lớn nhất và bội chung nhỏ
Bài toán 3: Cho dãy N số nguyên Ai {A1, A2, ... An} với 0 < N < 30, 0 < Ai
<100.
nhất của dãy số đó
Phân tích bài toán: Khi ta nhập vào dãy số Ai thì cần lưu dãy số này lại
nên ta sử dung một mảng một chiều để lưu. Tiếp theo dùng câu lệnh lặp kết hợp
Program UCLN_BCNN_day_so ;
Var a : array[1..30] of integer ;
N, i, Umax, Bmax : integer; bcnn : longint;
begin r:= a mod b; a:=b ; b:= r; end
while b <> 0 do
ucln := a;
bcnn:= bcnn*b div ucln(a,b);
function ucln(a,b: integer): integer;
var r : integer;
begin
end;
function bcnn(a,b: integer): longint;
begin
bcnn := a ;
end;
Begin
Umax := ucln(Umax, a[i]);
Bmax := bcnn(Bmax,a[i]);
Write(‘ Cho biet so N: ‘); readln(N);
For i := 1 to N do begin write(‘a[‘,i,’]=’); readln(a[i]); end;
Umax :=a[1] ; Bmax := a[1] ;
For i:= 2 to n do
Begin
End;
Writeln(‘Uoc chung lon nhat cua day so la: ‘, umax);
Writeln(‘Boi chung nho nhat cua day so la: ‘, bmax);
End.
Bài toán 4: Một trường học có XY nam, XX nữ (XY và XX là các số nguyên
dương, 0< XX, XY < 65000). Người ta muốn chia đều số nam và nữ vào các lớp
học sao cho mỗi lớp đều có ít nhất một nam và một nữ đồng thời số nam và nữ
các lớp bằng nhau, số lớp ít nhất là một.
While b <> 0 do begin r := a mod b ; a := b; b:= r; end;
Ucln := a;
Function ucln (a,b : word): word ;
Var tem : word ;
Begin
End;
If ((XX mod i = 0) and (XY mod i = 0)) then inc(dem);
Write(‘ Nhap so hoc sinh nam va hoc sinh nu: ‘); readln(XY, XX);
If XY > XX then min := XX else min := XY;
Dem := 0;
For i:= 1 to (min div 2) do
Writeln(‘so cach chia lop la: ‘, dem);
Writeln(‘so hoc sinh nu trong lop it nhat co the la: ‘,XX div dem);
Writeln(‘so hoc sinh nam trong lop it nhat co the la: ‘,XY div dem);
Bài toán 5: Cho
với n, x là số nguyên
Yêu cầu: Tính và rút gọn S thành phân số dạng tối giản
hai số nguyên.
Phân tích bài toán: Trước hết là ta phải tính toán lại giá trị của tử và mẫu
thành các số và lưu vào hai mảng riêng, các tử và mẫu từng phân số có chung
chỉ số ở hai mảng. Sau đó ta thực hiện quy trình 5 bước 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ố
tu, mau : array[1..100] of integer ;
i, x, umax, N : integer; Bmax, tong, tem : longint ;
begin r:= a mod b; a:=b ; b:= r; end
while b <> 0 do
ucln := a;
bcnn:= bcnn*b div ucln(a,b);
tu[i] := (Bmax div mau[i])*tu[i] ;
tong := tong + tu[i];
end;
Write(‘ Cho biet so N: ‘); readln(N);
Write(‘ Cho biet so x: ‘); readln(x);
For i := 1 to N do begin tu[i] := x+i ; mau[i] := 2*i ; end;
Bmax := mau[1] ;
For i:= 2 to N do Bmax := bcnn(Bmax,mau[i]);
Tong := 0;
For i:=1 to N do begin
tem:= ucln(tong, Bmax);
tong := tong div tem;
Bmax := Bmax div tem ;
Writeln(‘Phan so rut gon la: ‘, tong,’/’, Bmax);
2.5. Hiệu quả của đề tài:
Sau khi tôi áp dụng sáng kiến trên vào dạy học, chất lượng dạy học bồi
dưỡng học sinh giỏi môn Tin học 8, 9 tăng lên rõ rệt. Giáo viên có thể hoàn
thành chuyên đề dạy học nhanh chóng mà không phải giải thích nhiều lần, dành
nhiều tiết để giải quyết chuyên đề như trước. Đối với học sinh, có thể nắm được
I, N, p, q, Umaxle, Umaxchan : integer;
begin r:= a mod b; a:=b ; b:= r; end
while b <> 0 do
ucln := a;
If so mod 2 = 0 then begin inc(p); chan[p] := so end
else begin inc(q) ; le[q] := so; end;
begin write(‘ nhap vao so: ‘); readln(so);
end;
Write(‘ Cho biet so N: ‘); readln(N);
p:=0; q:=0;
For i:=1 to N do
Umaxchan :=chan[1] ; Umaxle := le[1] ;
For i:= 2 to p do Umaxchan := ucln(Umaxchan, chan[i]);
For i:= 2 to q do Umaxle := ucln(Umaxle,le[i]);
Writeln(‘Uoc chung lon nhat cua cac so le la: ‘, Umaxle);
Writeln(‘Boi chung nho nhat cua cac so chan la: ‘, Umaxchan);
Câu 1:
Program cau1 ;
Var chan, le : array[1..1000] of integer ;
function ucln(a,b: integer): integer;
var r : integer;
begin
end;
BEGIN
END.
tu, mau : array[1..100] of integer ;
i, x, umax, N : integer; Bmax, tong, tem : longint ;
begin r:= a mod b; a:=b ; b:= r; end
while b <> 0 do
ucln := a;
bcnn:= bcnn*b div ucln(a,b);
tu[i] := (Bmax div mau[i])*tu[i] ;
tong := tong + tu[i];
end;
Write(‘ Cho biet so N: ‘); readln(N);
Write(‘ Cho biet so x: ‘); readln(x);
Tu[1]:=1;
For i := 2 to N do begin tu[i] := tu[i-1]+i ; mau[i] := i*i + x ; end;
Bmax := mau[1] ;
For i:= 2 to N do Bmax := bcnn(Bmax,mau[i]);
Tong := 0;
For i:=1 to N do begin
tong := tong+2017*Bmax
tem:= ucln(tong, Bmax);
tong := tong div tem;
Bmax := Bmax div tem ;
Writeln(‘Phan so rut gon la, Q=: ‘, tong,’/’, Bmax);
Câu 2:
Program tong_cac_phan_so ;
Var
function ucln(a,b: integer): integer;
var r : integer;
begin
end;
function bcnn(a,b: integer): longint;
begin
bcnn := a ;
end;
Begin
End.
Kết quả các bài kiểm tra như sau:
Qua kết quả kiểm tra cho thấy, tất cả học sinh đã nhận biết được dạng bài,
viết được chương trình tìm ước chung lớn nhất, bội chung nhỏ nhất của hai hay
Trong quá trình dạy học, việc hình thành ý tưởng và tìm hiểu cách giải bài
toán là vô cùng quan trọng. Vì thế, khi củng cố bài học giáo viên cần phải khắc
sâu kiến thức đã học cũng như hướng dẫn các em chuẩn bị bài học ở nhà thật
chu đáo. Đồng thời trong quá trình học, giáo viên khuyến khích các em tự tìm
tòi sáng tạo các cách giải khác nhau cũng như việc tham khảo cách giải của
người khác để qua đó tích lũy được kinh nghiệm viết chương trình và có được
kết quả cao trong học tập.
Tôi xin chân thành cảm ơn!
