Sáng kiến kinh nghiệm THCS: 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

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

Thêm vào BST

Báo xấu

64
lượt xem 6
download

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

Mục tiêu nghiên cứu của sáng kiến kinh nghiệm là 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.

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ươ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
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ế. 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
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
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); 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 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; 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
Để 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]); 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: 8
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. A Yêu cầu: Tính và rút gọn S thành phân số dạng tối giản 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
Chương trình như sau: (Turbo Pascal) 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; begin bcnn := a ; bcnn:= bcnn*b div ucln(a,b); 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} For i:= 1 to N do begin tu[i]:= 2*i-1 ; mau[i] := 2*i ; end; {Tìm mẫu chung của các phân số} B := mau[1] ; For i:= 2 to N do B := bcnn(B ,mau[i]); A := 0; For i:=1 to N do begin tu[i] := (B div mau[i])*tu[i] ; A := A + tu[i]; end; 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
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: 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. 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
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ố: Program UCLN_BCNN_day_so ; Var a : array[1..30] of integer ; N, i, Umax, Bmax : integer; bcnn : longint; function ucln(a,b: integer): integer; var r : integer; begin while b 0 do begin r:= a mod b; a:=b ; b:= r; end ucln := a; end; function bcnn(a,b: integer): longint; begin bcnn := a ; bcnn:= bcnn*b div ucln(a,b); end; Begin 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 Umax := ucln(Umax, a[i]); Bmax := bcnn(Bmax,a[i]); 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. 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 ; Function ucln (a,b : word): word ; Var tem : word ; Begin While b 0 do begin r := a mod b ; a := b; b:= r; end; Ucln := a; End; Begin 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 If ((XX mod i = 0) and (XY mod i = 0)) then inc(dem); 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); End. x 1 x  3 x  5 x  2n  1 Bài toán 5: Cho S     ...  với n, x là số nguyên 2 4 6 2n dương và 0
+ 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 tu, mau : array[1..100] of integer ; i, x, umax, N : integer; Bmax, tong, tem : longint ; function ucln(a,b: integer): integer; var r : integer; begin while b 0 do begin r:= a mod b; a:=b ; b:= r; end ucln := a; end; function bcnn(a,b: integer): longint; begin bcnn := a ; bcnn:= bcnn*b div ucln(a,b); end; Begin 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 tu[i] := (Bmax div mau[i])*tu[i] ; tong := tong + tu[i]; end; tem:= ucln(tong, Bmax); tong := tong div tem; Bmax := Bmax div tem ; Writeln(‘Phan so rut gon la: ‘, tong,’/’, Bmax); End. 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 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
Câu 2: Program tong_cac_phan_so ; Var tu, mau : array[1..100] of integer ; i, x, umax, N : integer; Bmax, tong, tem : longint ; function ucln(a,b: integer): integer; var r : integer; begin while b 0 do begin r:= a mod b; a:=b ; b:= r; end ucln := a; end; function bcnn(a,b: integer): longint; begin bcnn := a ; bcnn:= bcnn*b div ucln(a,b); end; Begin 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 tu[i] := (Bmax div mau[i])*tu[i] ; tong := tong + tu[i]; end; 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); End. Kết quả các bài kiểm tra như sau: Giỏi Khá TB Yếu Đối SLHS tượng SL % SL % SL % SL % HSG 8 6 3 50.0 3 50.0 0 0 0 0 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 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. 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. 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! Tôi xin chân thành cảm ơn! 18