Sáng kiến kinh nghiệm Thuật toán tối ưu tìm ước chung lớn nhất của hai số nguyên

SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HOÁ
TRƯỜNG THPT HÀ TRUNG
*********************
SÁNG KIẾN KINH NGHIỆM
THUẬT TOÁN TỐI ƯU
 TÌM ƯỚC CHUNG LỚN NHẤT CỦA HAI SỐ NGUYÊN 
Người thực hiện: Lê Thị Hạnh
Chức vụ: Giáo viên
Đơn vị công tác: Trường THPT Hà Trung
SKKN thuộc môn: Tin học
THANH HOÁ NĂM 2016
MỤC LỤC
MỤC
NỘI DUNG
TRANG
PHẦN I
MỞ ĐẦU
1
Lý do chọn đề tài
01
2
Mục đích
01
3
Đối tượng
02
4
Phương pháp
02
PHẦN II
NỘI DUNG SÁNG KIẾN KINH NGHIỆM
I
Cơ sở lý luận và cơ sở thực tiễn của vấn đề
02
1
Cơ sở lý luận
02
2
Cơ sở thực tiễn
02
II. 
Nội dung đề tài
03
III
Thực trạng trước và sau khi áp dụng đề tài
12
PHẦN III
KẾT LUẬN VÀ ĐỀ XUẤT
13
PHẦN I. MỞ ĐẦU
Lý do chọn đề tài 
	Môn Tin học cũng như các môn học khác trong trường, việc dạy Tin học cần được thực hiện trong hoạt động và bằng hoạt động tự giác, tích cực, chủ động và sáng tạo của người học. Khi cần dạy một nội dung cho học sinh giáo viên cần cần hướng cho học sinh nội dung đó liên quan đến những hoạt động nào, dạng bài toán nào. Căn cứ trình độ học sinh, trang bị hiện có của nhà trường để lựa chọn cho học sinh luyện tập. Để học sinh có ý thức về ý nghĩa của những hoạt động. Cần đặt học sinh vào tình huống có vấn đề để hướng đích cho học sinh. Tập luyện cho học sinh tư duy thuật toán, chỉnh sửa thuật toán, khắc phục thuật toán và tìm ra thuật toán tối ưu.
	Đối với chương trình lớp 11, lập trình để giải các bài toán trên máy tính được hiểu theo nghĩa chuyển đổi thuật toán đã có sang chương trình viết trên ngôn ngữ lập trình bậc cao. Từ việc cài đặt chương trình học sinh hiểu hơn về thuật toán. Kết quả có được của bài toán từ thuật toán đã có. Từ đó học sinh biết cách điều chỉnh, tìm tòi, chỉnh sửa, lựa chọn thuật toán cho bài toán.
 Bài toán vận dụng tìm ƯCLN là một dạng bài toán cơ bản trong chương trình toán học từ THCS đến THPT. Các bài toán loại này rất phong phú, đa dạng, nếu nắm vững kiến thức, dạng bài toán cơ bản học sinh có điều kiện để giải rất nhiều bài tập liên quan tới kiến thức này.
Việc giải tốt loại bài toán này giúp cho học sinh hình thành thói quen làm việc một cách khoa học, hình thành thói quen tìm ra các quy luật trong toán học nói riêng, trong Tin học và trong đời sống nói chung . Với học sinh đại trà yêu cầu của dạng bài tập này không quá phức tạp, có lẽ vì vậy mà thời gian dành cho học bài toán loại này không nhiều. Tuy nhiên trong thực tế giảng dạy tôi nhận thấy học sinh rất hay nhầm lẫn trong việc tìm ƯCLN có rất nhiều thuật toán từ đơn giản nhất. Học sinh dễ nhớ nhất. Nhưng đôi khi học sinh chưa tìm ra được cách giải quyết để khắc phục thuật toán. Hoặc chưa tìm ra được thuật toán tối ưu cho bài toán cần giải quyết vấn đề.
 Chính vì vậy tôi muốn tìm ra cho mình một cách dạy, một quy trình truyền đạt kiến thức cho học sinh để học sinh không mất nhiều thời gian mà vẫn nắm bắt chắc chắn và giải thành thạo loại bài toán này. Đề tài “Thuật toán tối ưu tìm ước chung lớn nhất của hai số nguyên” chỉ là một ví dụ minh họa cho việc hình thành tri thức cho học sinh trong việc học lập trình cơ bản.
2. Mục đích
Đây là đề tài sáng kiến kinh nghiệm đã được tôi thực hịên từ năm hoc trước, khi ấy tôi trực tiếp giảng dạy môn Tin học lớp 11. Tiếp tục khẳng định giá trị thực tế của đề tài, trong năm học này mặc dù chỉ dạy môn Tin học lớp 12 song tôi vẫn kết hợp với đồng nghiệp áp dụng đề tài. Với mục đích :
- Giáo viên gây được hứng thú cho học sinh khi gặp hai loại bài toán này .
- Có kỹ năng nhận diện , phân biệt chính xác hai loại bài toán này.
- Có cách giải và cách trình bày chính xác khoa học, có kỹ năng thành thạo khi giải toán .
- Giải được một số dạng bài toán mà cách giải vận dụng dạng toán cơ bản trên .
3. Đối tượng
 	 Để thực hiện đề tài này tôi chọn đối tượng là học sinh đại trà lớp 11D trường THPT Hà Trung , thực hiện trong học kì I năm học 2014 – 2015 . lớp 11C năm học 2015 – 2016
4. Phương pháp:
Để học sinh hình thành kỹ năng làm dạng bài tập liên quan đến các thuật toán. Cũng như cách khắc phục những ưu khuyết điểm của thuật toán áp dụng. Cần cho học sinh thử chạy chương trình với các bộ test theo từng tiêu chí khác nhau. Để từ đó học sinh biết cách khắc phục và hoàn thiện chương trình. Tìm ra đc thuật toán tối ưu nhất
PHẦN II. NỘI DUNG SÁNG KIẾN KINH NGHIỆM
Cơ sở lý luận và thực tiễn của vấn đề
1.Cơ sở lí luận 
Quan điểm hoạt động trong phương pháp dạy học sinh thể hiện ở các tư tưởng chủ đạo sau:
Cho học sinh thực hiện và luyện tập những hoạt động 
Gợi động cơ cho các hoạt động
Dẫn dắt học sinh kiến tạo tri thức, đặc biệt là tri thức phương pháp phương tiện và kết quả học tập
Phân bậc hoạt động làm phương pháp căn cứ
2.Cơ sở thực tiễn
a. Đối với học sinh
Trong quan niệm và cách nghĩ của nhiều học sinh, môn Tin học là môn học sử dụng máy tính, gõ văn bản, làm theo thói quen, không cần có sự tư duy; là môn học phụ nên học sinh có tâm lý xem nhẹ môn học, chỉ học và làm theo lối mòn, học để đối phó. Hơn nữa đây lại là môn học cần được thực hành mà điều kiện kinh tế địa phương còn nhiều hạn chế. Thời gian thực hành ít, cơ sở vật chất thiếu thốn. Học lập trình lại khó, học sinh dễ nản lòng
	Còn một bộ phận không nhỏ học sinh lười đọc tài liệu, không chịu khó, chưa có sự tìm tòi, khám phá dẫn đến thiếu hiểu biết về kiến thức bộ môn.
b.Đối với phụ huynh:
	Phần lớn phụ huynh chưa có nhận thức đúng đắn về tầm quan trọng của môn học; có tư tưởng xem nhẹ, không khuyến khích con em có những định hướng đúng đắn phù hợp trong quá trình học tập bộ môn.
	Một bộ phận phụ huynh ít quan tâm đến việc học của học sinh, làm cho các em không có được sự tập trung, thiếu định hướng từ phía gia đình dẫn đến các em lơ là việc học, kiến thức lỏng lẻo.
c. Đối với bộ môn, giáo viên và nhà trường:
	Phương tiện dạy học còn thiếu thốn, việc dạy Tin học trong nhà trường hiện nay chỉ coi trọng dạy kiến thức, mà chưa coi trọng dạy các kỹ năng Tin học; chưa thực sự phát huy được năng lực của học sinh nên khi học xong các em quên khá nhiều kiến thức. Trong khi đó, các kỹ năng đơn giản như vận dụng kiến thức đã học để lý giải một bài toán cũng không thực hiện được
 Nội dung đề tài:
Đầu tiên chúng ta cần tìm hiểu vấn đề sau:
- Ước chung lớn nhất là gì? Nếu một số nguyên a bất kỳ chia hết cho số nguyên c được gọi là ước của số nguyên a và a được gọi là bội của c. Nếu 2 số dương a và b bất kỳ cùng chia hết cho một số nguyên c lớn nhất thì c được gọi là ước chung lớn nhất của a và b. Nếu a và b đều = 0 thì chúng không có ước chung.
- Bội chung nhỏ nhất là gì? c được gọi là bội chung nhỏ nhất của a và b khi c là số nguyên nhỏ nhất chia hết cho a và b.
Công thức: UCLN(a,b) = (a*b)/BCNN(a,b)
-Phân số tối giản là gì? phân số mà có tử số và mẫu số không thể cùng chia hết cho số nào ngoại trừ số 1 (hoặc -1 nếu lấy các số âm). Nói cách khác phân số a/b là tối giản nếu a và b là nguyên tố cùng nhau, nghĩa là a và b có ước số chung lớn nhất là 1.
Để giải quyết được các bài toán trên điều đầu tiên chúng ta cần giải quyết được bài toán tìm UCLN của hai số nguyên A và B. Chúng ta sẽ tìm hiểu các thuật toán tìm UCLN của 2 số nguyên. Ưu điểm, nhược điểm và cách khắc phục của thuật toán đó.
Cách 1: Dưới đây là thuật toán tìm UCLN bằng cách trừ đi nhau, được trình bày trong SGK tin học 10. 
Trước tiên học sinh sẽ nhắc lại thuật toán đã học lớp 10
B1   Nhập 2 số nguyên A và B
B2 Nếu A=B thì UCLN=A và dừng
B3 Nếu A>B thì Aß A-B ngược lại BßB-A
B4 Quay lại B2
Thuật toán trên có thể minh họa bằng chương trình:
Function UCLN(a,b:Integer):Integer;
Begin
While a b do
If a>b then a:=a-b else b:=b-a;
UCLN:=a;
End; 
Với thuật toán này ta có thể áp dụng tìm BCNN của 2 số nguyên
var x,y,UCLN,BCNN:integer;
begin
readln(x,y);
BCNN:=x*y;
While xy do If x>y then x:=x-y else y:=y-x;
UCLN:=x;
BCNN:=BCNN div UCLN;
write(UCLN,' ',BCNN);
end.
Chương trình con trên chỉ chạy đúng khi 2 số nguyên dương, ngoài ra chương trình sẽ gặp vòng lặp vô hạn.
Cụ thể, lệnh c:=UCLN(4,0) hoặc c=(4,-3); đều gặp vòng lặp vô hạn. Do đó ta cần cải tiến chương trình như sau:
Function UCLN(a,b:Integer):Integer;
Begin
While (a>0) And (b>0) do
If a>=b then a:=a-b else b:=b-a;
UCLN:=a+b;
End; 
Với chương trình cải tiến trên, vòng lặp chỉ thực hiện khi 2 tham trị truyền vào lớn hơn 0 cho đến khi một trong hai số bằng 0, vì vậy kết quả UCLN:=a+b(một trong 2 số đó bằng 0). Dễ thấy chương trình trên vẫn còn sai khi 2 số nhập vào có 1 số âm
Thật vậy lệnh c:=UCLN(6,-2) cho kết quả là UCLN=4 nhưng thực ra phải là 2 vì 6⋮2 và-2⋮2
Để khắc phục được lỗi trên ta cần lấy trị tuyệt đối của hai số nhập vào bằng hàm ABS. Chẳng hạn gán: a:=ABS(a); b:=ABS(b); trong chương trình chính hoặc trong chương trình con tìm UCLN:
Function UCLN(a,b:Integer):Integer;
Begin
	A:=Abs(a); b:=Abs(b)
While (a>0) And (b>0) do
If a>=b then a:=a-b else b:=b-a;
UCLN:=a+b;
End; 
Cách 2: Thuật toán Euclide: Ngoài cách tìm UCLN như trên. Các bạn có thể sử dụng cách chia lấy dư (mod), chương trình sẽ tối ưu do phải thực hiện ít phép tính hơn.
Ý tưởng: UCLN của 2 số A, B cũng là UCLN của 2 số B và A mod B, vậy ta sẽ đổi A là B, B là A mod B cho đến khi B bằng 0. Khi đó UCLN là A. 
Hay nói cách khác UCLN(a,b)=UCLN(a mod b. b);
 Ta nhận thấy rằng 0≤ (a mod b)<b, do đó sau mỗi lần lấy dư ta cần đổi chỗ 2 tham trị nói trên trong Function để có thể tiếp tục xử lí cho đến khi gặp số dư bằng 0. Chương trình như sau:
Function UCLN(a,b:integer):Integer;
Var c:Integer;
Begin
A:=Abs(a); b:=Abs(b);
While (b0) do
Begin
C:= a mod b;
A:=b;
B:=c;
End;
UCLN:=a;
End;
Ta có thể áp dụng tìm BCNN của 2 số nguyên
var a,b,UCLN,BCNN,t:integer;
begin
readln(x,b); 
BCNN:=a*b;
t:= b mod a;
While t 0 do
      Begin
        t:= a MOD b;
        a:= b;
        b:= t;
      End;
ucln:=a;
BCNN:=BCNN div UCLN;
write(UCLN,' ',BCNN);
End.
Cách 3: Tìm UCLN bằng cách dùng đệ quy: 
Đệ quy được hiểu đơn giản là sự gọi nhiều lần chương trình con trong chương trình. Thực sự, đối với bài toán đơn giản, không ai sử dụng đệ quy vì sẽ làm phức tạp vấn đề và làm chương trình trở nên rắc rối, phải thực hiện nhiều phép tính hơn. Tuy nhiên, nếu bắt buộc phải dùng đệ quy, các bạn có thể tham khảo cách làm dưới đây:
Function Ucln(a,b:integer):integer;
begin
if a = b then
ucln:=a
else if a > b then 
ucln:=ucln(a mod b,b)
else 
ucln:=ucln(a, b mod a); 
end;
var a,b:integer;
begin
readln(a,b);
write('Ước chung lớn nhất là: ', UCLN(a,b), ' Bội chung nhỏ nhất là: ', (a*b) div UCLN(a,b));
end.
Ngoài ra học sinh có thể tách theo từng trường hợp để làm như sau:
B1   Nhập 2 số nguyên A và B
B2   Gán A = giá trị tuyệt đối của A, B =  giá trị tuyệt đối của B
B3   Nếu A =0 và B=0 thì B9
B4   Nếu A=0 và B 0 thì B10
B5   Nếu B=0 và A 0 thì B11
B6   Gán dư của phép chia A cho B vào biến D ( D = A mod B )
B7   Nếu D = 0 thì chuyển sang B10
B8   Gán A = B ; B = D ; D = A mod B chuyển về B7
B9   Thông báo UCLN không tồn tại , chuyển về Bkt
B10 Thông báo kết quả : Ước số chung lớn nhất là số B , chuyển về Bkt
B11 Thông báo kết quả : Ước số chung lớn nhất là số A
Bkt   Kết thúc
Chương trình cụ thể:
Uses   Crt;
Var   A,B,La,Lb : Integer;
Procedure Nhap(i : Char;Var x : Integer);
Var Ok : Boolean;
Begin
Write(‘Nhap so nguyen ‘,i,’ = ‘);
Repeat
{$I-} Readln(x); {$I+}
Ok := (IoResult=0);
Until Ok;
End;
Procedure Hien(x : Integer);
Begin
Write(‘UCLN(‘,LA:5,’,’,LB:5,’) = ‘,x);
Readln;
Halt;
End;
Procedure Hien2;
Begin
Writeln(‘ Moi so nguyen deu = UCLN(0, 0) ‘);
Readln;
Halt;
End;
Procedure Tim;
Var D : Integer;
Begin
A := Abs(A);
B := Abs(B);
If (A=0) and (B0) then Hien(B);
If (B=0) and (A0) then Hien(A);
If (A=0) and (B=0) then Hien2;
D := A mod B;
While D0 do { Chu y neu dung Repeat can tranh chia cho 0 }
Begin
A := B;
B := D;
D := A mod B;
End;
Hien(B);
End;
BEGIN
Clrscr;
Nhap(‘A’,A);
Nhap(‘B’,B);
La := A;
Lb := B;
Tim;
Readln;
END.
Tuy nhiên làm theo cách này rất dài dòng. Không cần thiết vì mất nhiều thời gian cho việc viết chương trình
Chúng ta có thể tham khảo một vài cách xử lí khác nữa. Cùng với ưu và nhược điểm của nó để so sánh:
used crt;
var
m, n, u, i:longint;
begin
clrscr;
write('nhap n,m:');read(n, m);
for i:= m downto 1 do
if(m mod i=0)and(n mod i=0) then
begin
u:=i;{u nhận giá trị ước chung lớn nhất đó}
i:=1;{để nhảy ra khỏi vòng lặp}
end;
write('UCLN(,'m',n,')',u);
readln;
end.
Thuật tóan này đơn giản, hiệu quả nhưng không nhanh. Thuật tóan khác với các thuật tóan phổ thông khác, dùng phương pháp thử để tìm. Với các số trong phạm vi (-1000,1000) thì chạy nhanh hơn phổ thông. Còn trên 1000 thì chạy châm hơn, càng lớn chạy càng châm.
Đề xuất thuật toán nhanh hơn như sau: 
Function UCLN(m,n:word):word
begin
while(m0 and n0) do
begin
if(m>n) then m:=m mod n;
else n:=n mod m;
end;
UCLN:=m+n;
end;
 Cách này giống như là cách tìm UCLN trong máy casio học sinh hay làm trong toán học để tìm nhanh bằng máy tính cầm tay.
 Cách này có trong nhiều tài liệu tham khảo. Không thể coi là một cách mới.
nói về tốc độ thuật toán có thể chạy nhanh hơn. Nếu số quá lớn có thể sửa lại vòng lặp cho nhỏ lại.
Vd: thay n trong 
for i:= n downto.....
bằng n div 2 .v.v. tốc độ có thể theo đó tăng lên.
cái khó là giới hạn vòng lặp sao cho nhỏ nhất có thể.
Từ việc có thuật toán UCLN ta có thể áp dụng cho một số bài toán thường gặp như sau:
1. Nhập một số nguyên dương n >=2 , nhập n số nguyên dương , và tìm ước chung lớn nhất của n số đó .
Ý tưởng:
 Tìm ước chung lần lượt của 2 số rồi lấy ước chung đó dùng làm tham số cho hàm UCLN ở trên rồi tìm với số tiếp theo.
Đưa tất cả các số đã nhập vào 1 mảng, rồi sau đó lần lượt dùng giải thuật nhị phân chia cặp ra các số rồi tìm ƯCLN. Các ƯCLN này lại được chặt tiếp cho đến khi nào chỉ còn 1 thì thoát vòng lặp. Hơi giống thuật toán sắp xếp nhị phân 
Gọi U là UCLN của dãy
U:=a[1];
For i:=2 to n do u:=UCLN(u,abs(a[i]));
2. Tìm BCNN của một dãy số
Ý tưởng:
Gọi P là BCNN của dãy
P:=a[1];
For i:=2 to n do
P:=p*a[i]; 
khi đưa ra
BCNN là p:=p div u;
3. Phân số tối giản( rút gọn phân số):
Ý tưởng:
 Sau khi có thuật toán UCLN của hai số nguyên. Chúng ta có thể áp dụng với rút gọn phân số
Một phân số chưa tối giản có thể chuyển về dạng tối giản bằng cách chia tử số và mẫu số của phân số cho ước số chung lớn nhất của chúng. 
4. Số nguyên tố cùng nhau:
Ý tưởng:
Dựa trên thuật toán tính UCLN ta có thể kiểm tra được 2 số nguyên tố cùng nhau là hai số có UCLN =1
5. Số Tam Tam: Tât cả các số tự nhiên có 3 chữ số sao cho khi đảo trật tự các số ta thu được một số nguyên tố cùng nhau với số đã cho.
Ý tưởng:
Với bài toán này chúng ta qui về bài kiểm tra số có 3 chữ số abc thỏa mãn UCLN(100*a+10*b+c,100*c+10*b+a)=1
Thực trạng trước và sau khi áp dụng sáng kiến kinh nghiệm
Thường học sinh có thói quen khi áp dụng thuật toán để viết chương trình đều không quan tâm thuật toán đã đúng đắn, chính xác hay chưa. Sau khi áp dụng ở các lớp tôi dạy năm trước. Và các lớp do các đồng nghiệp tiến hành ở năm học này. Phần lớn học sinh đã hình thành thói quen, tư duy sáng tạo.
PHẦN III: KẾT LUẬN VÀ ĐỀ XUẤT.
1. Kết luận:
	Qua trao đổi với các giáo viên, học sinh tham gia lớp dạy khuyến khích học sinh tích cực, chủ động tham gia học tập một cách độc lập. Vì thế mà những kiến thức các em thu lượm được qua các giờ học sẽ được các em nhận thức một cách đầy đủ hơn, sâu sắc và toàn diện hơn.
Ở các lớp đối chứng, do vẫn giảng dạy theo phương pháp truyền thống, việc tổ chức các hoạt động cho học sinh thường không linh hoạt vì thế đã làm hạn chế sự tích cực, khả năng sáng tạo của các em trong việc phát hiện, lĩnh hội và chủ kiến thức.
Tuy nhiên cũng cần phải nói rằng, dạy học là cả một quá trình lao động sáng tạo mà trong đó giáo viên luôn tự đổi mới để làm mới quá trình lao động của mình. Để giờ dạy đạt hiệu quả cao đòi hỏi người giáo viên phải luôn tâm huyết với nghề, luôn đề cao quá trình tự học, tự bồi dưỡng để nâng cao trình độ chuyên môn nghiệp vụ.
2. Một số đề xuất, kiến nghị:
- Trước hết, nhà trường đầu tư phòng máy đầy đủ để đảm bảo mỗi học sinh được thực hành trong các tiết học bộ môn Tin học. Để tổ chức cho học sinh các hoạt động nhận thức phù hợp với trình độ học tập của các em. 
- Thứ hai là, cấp trên đầu tư máy tính định kỳ 5 năm 1 lần. tránh trường hợp các máy tính dùng quá lâu. Thiết bị thay thế khan hiếm. Không đảm bảo việc thực hành cho học sinh.
- Thứ ba là, việc sử dụng và vận dụng các kỹ thuật dạy học tích cực trong giảng dạy nhất thiết cần có sự hỗ trợ không thể thiếu của các phương tiện dạy học hiện đại (máy chiếu đa năng, máy chiếu projector ). Vì vậy, nhà trường cần trang bị đầy đủ các phương tiện, thiết bị, đồ dùng để tạo điều kiện tốt hơn nữa cho giáo viên trong việc nghiên cứu xây dựng và sử dụng phương pháp sơ đồ trong giảng dạy bộ môn Tin học
Trên đây là một kinh nghiệm nhỏ trong áp dụng trong quá trình dạy học với đặc thù bộ môn Tin học trong chương trình lớp 11. Mong rằng sẽ ngày càng phát triển hơn và hoàn thiện hơn nữa 
 Tôi xin chân thành cảm ơn.
XÁC NHẬN CỦA THỦ TRƯỞNG ĐƠN VỊ
Thanh Hóa, ngày 19 tháng 5 năm 2016
CAM KẾT KHÔNG SAO CHÉP.
Người viết sáng kiến
Lê Thị Hạnh