Đề tài Ứng dụng công nghệ thông tin vào giải một số bài toán số học

Cấu trúc đề tài
trang
A. mở đầu. 
 i. lý do chọn đề tài.
 II. mục đích nghiên cứu.
 III. phương pháp nghiên cứu.
b. nội dung.
 I. một số định nghĩa và kháI niệm liên quan.
 II. chương trình giảI các bài toán.
 1.Biểu biễn số tự nhiên trong hệ g phân.
 2. Cộng các số trong hệ nhị phân.
 3. Biểu diễn số hữu tỷ dưới dạng thập phân.
 4. Biểu diễn liên phân số.
 5. Tính giản phân.
 6. Kiểm tra số nguyên tố.
 7. Phân tích một số ra thừa số nguyên tố.
 8. Số hoàn chỉnh.
 9. Tìm ước chung lớn nhất.
 10. Tìm bội chung nhỏ nhất.
 11. Nhân hai số trong hệ nhị phân. 
C. Kết luận.
D. tài liệu tham khảo.
A. mở đầu.
I. lý do chọn đề tài.
 Khoa học kỹ thuật phát triển như vũ bão, công nghệ thông tin bùng nổ trên toàn cầu, nhân loại đang dần tiến tới nền kinh tế tri thức. Công nhệ thông tin có mặt ở khắp mọi nơi trong tất cả các lĩnh vực để phục vụ và nâng cao đời sống cho con người. Hoà cùng xu thế đó tin học đang dần phổ biến trong hệ thống giáo dục của Việt Nam, giúp người học làm quen với công nhệ thông tin và sử dụng nó để phục vụ cho việc học tập, tự tìm tòi, khám phá.
 Tin học là công cụ hỗ trợ học tập sinh động và tiện ích nhất hiện nay phục vụ cho tất cả các ngành học như: toán, lý, hoá, văn, sử ,địa Đặc biệt đối với môn toán, có những bài toán yêu cầu phải tính toán rất phức tạp như: tính các liên phân số, giản phân, đổi cơ sốđiều này gây khố khăn không nhỏ cho cả người dạy và người học. Nhưng những bất tiện này sẽ được giải quyết nhanh chóng nếu ta sử dụng phần mềm tin học để viết các bài toán thành chương trình tổng quát chạy trên máy tính.Khi đã nghiên cứu thuật toán và viết thành công các chương trình thì lúc đó người học chỉ cần nhập yêu cầu và mọi tính toán đều do máy thực hiện. Từ đó giúp người học có thể tính toán nhanh chóng, chính xác, giúp tiết kiệm được thời gian và công sức.
 Tuy nhiên giải toán trên máy tính là vấn đề tương đối lạ với nhiều người và việc viết thành công chương trình là điều rất phức tạp, nhưng nếu thành công thì phục vụ rất nhiều trong việc học tập. Đồng thời rèn luỵên rất nhiều khả năng tư duy thật toán logic, viết thành thạo các chương trình trên máy tính góp phần phát triển trí tuệ. Là sinh viên đang đi sâu nghiên cứu môn: cơ sở số học nhận thấy tác dụng to lớn của việc sử dụng tin học để giải quyết các bài toán số học có tính toán phức tạp. Nên Tôi quyết định chọn nghiên cứu đề tài: ứng dụng công nghệ thông tin để giảI một số bài toán số học. 
II. mục đích nghiên cứu.
- Có các nhìn tổng quát hơn về thuật toán và chương trình, vừa nắm vững môn cơ sở số học vừa biết cách viết chương trình cho một bài toán. 
- là tài liệu bổ ích phục vụ cho việc học tập của bản thân.
- Bổ sung vào nguồn tài liệu để mọi người cùng tham khảo, sử sụng.
- Rèn luyện, phát triển tư duy toán học và tin học. 
III. phương pháp nghiên cứu.
Nghiên cứu từ góc độ môn cơ sở số học:
 + Nghiên cứu, nắm vững các thuật toán.
 + Tính toán các khả năng xảy ra.
 + Xây dựng thuật toán tổng quát cho bài toán.
nhiên cứu từ góc độ tin học:
 + Từ các thuật toán tổng quát tìm cách xây dựng các giải thuật hợp lí.
 + Viết chương trình.
 + Kiểm định kết quả.
B. nội dung.
Một số định nghĩa và khái niệm
Định nghĩa tính chia hết.
 Cho hai số nguyên a và b , với b # 0. Nếu có một số nguyên q sao cho a=bq thì ta nói rằng b chia hết a hay b là ước của a, và ký hiệu là: b\ a.
Ta cũng nói a chia hết cho b hay b là bội của a và ký hiệu là: a:b
Định nghĩa về phép chia có dư.
 Cho hai số nguyên a và b , với b # 0. Khi đó có các số nguyên q và r sao cho: a = bq+r, 0 r < 
 3 - Định nghĩa số nguyên tố - hợp số – số hoàn chỉnh.
 a) Số tự nhiên lớn hơn 1 không có ước nào khác ngoài 1 và chính nó được gọi là số nguyên tố.
 b) Số tự nhiên lớn hơn 1 và không phải là số nguyên tố được gọi là hợp số.
 c) Một số tự nhiên khác 0 được gọi là số hoàn chỉnh nếu tổng các ước của nó gấp hai lần số đó.
Nếu gọi d là tổng các ước của n thì d(n) = 2n.
4 - Định nghĩa ước chung lớn nhất.
Một số nguyên được gọi là ước chung của nhiều số a1, a2,,an. Khi nó là ước của mỗi số đó.
Một ước chung d của các số a1, a2,,an sao cho mọi ước chung của a1, a2,,an đều là ước của d, thì d được gọi là ước chung lớn nhất của a1, a2,,an. 
Nếu 1 là ước chung lớn nhất của a1, a2,,an thì các số a1, a2,,an gọi là nguyên tố cùng nhau.
Nếu ta còn có 1 là ước chung lớn nhất của mọi cặp số ai, aj ( với i #j; i,j=1,2,3,) thì các số a1, a2,,an gọi là nguyên tố cùng nhau từng đôi một. Hay là nguyên tố sánh đôi.
5 - Định nghĩa bội chung nhỏ nhất.
a) Một số nguyên được gọi là bội chung của nhiều số a1, a2,,an. Khi nó là bội của mỗi số đó.
b) Một bội chung m của các số a1, a2,,an sao cho mọi bội chung của a1, a2,,an đều là bội của m, thì m được gọi là bội chung nhỏ nhất của a1, a2,,an. 
6 - Định nghĩa hệ ghi số g- phân.
Giả sử g là một số tự nhiên lớn hơn 1. Khi đó mỗi số tự nhiên a>0 đều biểu diễn dược một cách duy nhất dưới dạng a= Cngn + Cn-1gn-1 + Cn-2gn-2 +  + C1g1 + C0g0.
ở đây 0 Cig-1, i=0,1,2,,n và Cn # 0.
Thì ta viết a=Cn Cn-1 Cn-2 C1 C0g và ta nói đó là sự biểu diễn a trong hệ g- phân.
7- Định nghĩa số thập phân hữu hạn.
Giả sử là một phân số thập phân, a là một số tự nhiên có (m+1) chữ số: a=am10n + am-110m-1 +  + a110 + a0.
8 - Định nghĩa số thập phân vô hạn tuần hoàn
 - Nếu (N,a1a2a3) là dãy số tương ứng với dãy số hữu tỉ không âm, thì ta viết x=N,a1a2a3 và nói: đó là sự biểu diễn số hữu tỉ x dưới dạng thập phân
 - Nếu x là số hữu tỉ âm thì ta viết x=- N, a1a2a3.Trong đó (N, a1a2a3) là sự biểu diễn của 
9 - Khái niệm của liên phân số hữu hạn
 Biểu thức có dạng 
Trong đó q0 Z; q1,q2,N*; qn>1 được gọi là một liên phân số hữu hạn cấp n. q1,q2,,qn gọi là các số hạng của liên phân số.
10. Khái niệm giản phân hữu hạn.
Giả sử đã cho liên phân số hữu hạn cấp n. Đặt
 t0 = q0 , t1 = q0 + 1/q1 ,
Tổng quát: tk = 
 Thực hiện phép tính chỉ ra trong biểu thức tk ta được một phân số, chẳng hạn tk = Pk/Qk.
Phân số Pk/Qk được gọi là giản phân cấp k của liên phân số cấp n.
 Như vậy, giá trị của liên phân số hữu hạn cấp n bằng giản phân cấp n của nó.
 Công thức tính giản phân
 P0 = q0 ;
 Q0 = 1;
 P1 =q1q0 + 1; 
 Q1=q1;
 Pk = qkPk-1 + Pk-2;
 Qk = qkQk-1 + Qk-2;
 2 Ê k Ê n.
II. chương trình giảI các bài toán 
 1. Biểu diễn số tự nhiên trong hệ g phân.
program doiso;
uses crt;
type psd=^node;
 node=record
 sodu:psd;
 sd:byte;
 next:psd;
 end;
 mangkt=array[1..100] of char;
var last,p:psd;
 i,n,so,r,luuso,g:integer;a:mangkt;
Begin
 clrscr;
 write('nhap so can doi = ');readln(so);
 luuso:=so;
 write('nhap co so = ');readln(g);
 while so 0 do
 begin
 r:=so mod g;
 n:=n+1;
 new(p);
 p^.sd:=r;
 if (r>=0) and (r<=9) then a[n]:=chr(r+48);
 if r=10 then a[n]:= 'A';
 if r=11 then a[n]:= 'B';
 if r=12 then a[n]:= 'C';
 if r=13 then a[n]:= 'D';
 if r=14 then a[n]:= 'E';
 if r=15 then a[n]:= 'F';
 so:=so div g;
 p^.next:=last;
 last:=p;
 end;
 write(luuso,' viet trong co so ',g,' la = ');
 p:=last;
 while p nil do
 begin
 write(p^.sd);
 p:=p^.next;
 end;
 writeln;
 for i:= n downto 1 do
 write(a[i]);
 readln;
 End.
2. Cộng các số nguyên trong hệ nhị phân.
Program cong_nhi_phan;
type mang=array[0..100] of integer;
var a,b,c,d,i,j,m,n,k:integer;
 x,y,s,tg:mang;
Begin
 i:=0;
 Write('Nhap a= ');read(lnxa; 
 while (a0) do
 begin
 i:=i+1;
 x[i]:=a mod 2;
 a:=a div 2;
 end;
 n:=i;
 for i:=1 to n do
 write(x[i]);
 i:=0;
 Write('Nhap b= '); readln(b);
 while (b0) do
 begin
 i:=i+1;
 y[i]:=b mod 2;
 b:=b div 2;
 end;
 m:=i;
 for i:=1 to n do
 write(x[i]);
 k:=n;
 if m>n then
 begin
 k:=m;
 for j:=1 to m do
 tg[i]:=0;
 i:=m;
 j:=n;
 while (i>(m-n)) do
 begin
 tg[i]:=x[j];
 dec(i);
 dec(j);
 end;
 for j:=1 to m do x[j]:=tg[j];
 end
 else if m<n then
 begin
 k:=n;
 for j:=1 to n do
 tg[i]:=0;
 i:=n;
 j:=m;
 while (i>(n-m)) do
 begin
 tg[i]:=y[j];
 dec(i);
 dec(j);
 end;
 for j:=1 to n do y[j]:=tg[j];
 end;
 writeln('ket qua');
 for i:=1 to k do
 write(x[i]);
 writeln;
 for i:=1 to k do
 write(y[i]);
 writeln;
 c:=0;
 for j:=1 to k do
 begin
 d:=(x[j]+y[j]+c) div 2;
 s[j]:=x[j]+y[j]+c-2*d;
 c:=d;
 end;
 s[k+1]:=c;
 writeln('Tong la s= ');
 for i:=k+1 downto 1 do
 write(s[i]);
readln;
end.
3. Biểu diễn số hữu tỷ dưới dạng thập phân. 
program so_huu_ti;
uses crt;
var i,k,a,b,q:integer;
 x:array [0..100] of integer;
Begin
clrscr;
 write('nhap a= ');readln(a);
 write('nhap b= ');readln(b);
 q:=a;
 k:=0;
 x[k]:=q div b;
 while (q mod b 0) do
 begin
 k:=k+1;
 q:=(q mod b)*10;
 x[k]:=q div b;
 write(q:4);
 end;
 writeln;
 write('Bieu dien huu ti cua ',a,'/',b,' la: ',x[0],',');
 for i:=1 to k do
 write(x[i]);
 readln;
end.
4. Liên phân số.
 Program lien_phan_so;
var i,a,b,x,y,k,du:integer;
 q:array [0..100] of integer;
Begin
 write('Nhap a= '); readln(a);
 write('Nhap b= '); readln(b);
 x:=a;
 y:=b;
 k:=0;
 while (y0) do
 begin
 q[k]:=x div y;
 du:=x mod y;
 x:=y;
 y:=du;
 inc(k);
 end;
 writeln;
 write('Bieu dien lien phan so cua ',a,'/',b,' la: [',q[0],';');
 for i:=1 to k-2 do
 write(q[i],',');
 write(q[k-1],']');
 readln;
End.
5. Tính giản phân.
 Program gianphan;
uses crt;
var a,p,q:array [0..100] of integer;
 i,n:integer;
Begin
clrscr;
write('lien phan so cap n= ');readln(n);
for i:=0 to n do
 begin
 write('nhap a',i,'= ');
 readln(a[i]);
 end;
 p[0]:=a[0];
 q[0]:=1;
 p[1]:=(a[1]*a[0])+1;
 q[1]:=a[1];
 for i:=2 to n do
 begin
 p[i]:=(a[i]*p[i-1])+p[i-2];
 q[i]:=(a[i]*q[i-1])+q[i-2];
 end;
 writeln('cac gian phan la: ');
 for i:=0 to n do
 write(p[i],'/',q[i],'; ');
 writeln;
 writeln('Gia tri cua lien phan so nay la: ',p[n],'/',q[n]);
 readln;
end.
6. Kiểm tra số nguyên tố.
 program so_nguyen_to;
uses crt;
var j,k,n:word;
 tiep:char;
Begin
clrscr;
 write('SO N CO PHAI LA SO NGUYEN TO HAY KHONG ');
 repeat
 write('nhap so n = '); readln(n);
 k:=trunc(sqrt(n));
 j:=1;
 repeat
 j:=j+1;
 until (j>k) or (n mod j=0);
 if j>k then
 writeln('so ',n,' la so nguyen to ')
 else
 writeln('so ',n,' khong phai la so nguyen to ');
 writeln;
 write('*thuc hien nua khong(c/k) ');
 readln(tiep);
 until ( upcase(tiep)='K');
end.
7. Phân tích một số ra thừa số nguyên tố.
Program phan_tich_ra_thua_so_nguyen_to;
var n,m,i,j:integer;
 a:array [1..100] of integer;
Function ktnt(c:integer):Boolean;
 var i:integer;
 Begin
 if c>=2 then ktnt:=true else ktnt:=false;
 for i:=2 to c-1 do
 if c mod i=0 then
 begin
 ktnt:=false;
 break;
 end;
 end;
BEGIN
 write('Nhap n= '); readln(n);
 m:=n;
 j:=0;
 i:=2;
 while ((i1)) do
 begin
 if (ktnt(i) and (n mod i=0)) then
 begin
 inc(j);
 a[j]:=i;
 n:=n div i;
 end
 else
 inc(i);
 end;
 write(m,' = ');
 for i:=1 to j-1 do
 write(a[i],'*');
 write(a[j]);
readln;
end.
8. Số hoàn chỉnh.
program so_hoan_chinh;
uses crt;
var n,i,s:integer;
begin
 clrscr;
 write('nhap n= ');readln(n);
 s:=1;
 for i:=2 to n div 2 do
 if n mod i = 0 then
 s:=s+i;
 i:=i+1;
 if s=n then
 writeln(n,' la so hoan chinh ');
 if sn then
 writeln(n,' khong la so nguyen to ');
 readln;
 End.
9. Tìm ước chung lớn nhất .
program Tim_uoc_chung_lon_nhat;
uses crt;
var a,b:integer;
function UCLN(a,b:integer):integer;
 var r:integer;
 begin
 if a<b then
 begin
 r:=a;
 a:=b;
 b:=r;
 end;
 while b0 do
 begin
 r:=a mod b;
 a:=b;
 b:=r;
 end;
 UCLN:=a;{gia tri duoc gan cho ten ham}
 end;
BEGIN
 clrscr;
 write('moi nhap gia tri cua a=');readln(a);
 write('moi nhap gia tri cua b=');readln(b);
 writeln('UOC CHUNG LON NHAT CUA HAI SO DA CHO LA:',UCLN(A,B));
 READLN;
END.
10 – Tìm bội chung nhỏ nhất của hai số.
program Tim_boi_chung_nho_nhat;
uses crt;
var a,b:longint;
function UCLN(a,b:longint):longint;
 var r:longint;
 begin
 if ab then
 begin
 r:=a;
 a:=b;
 b:=r;
 end;
 while b0 do
 begin
 r:=a mod b;
 a:=b;
 b:=r;
 end;
 UCLN:=a;
 end;
function BCNN(a,b:longint):longint;
 begin
 BCNN:=(a div UCLN(a,b))*b;
 end;
BEGIN
 clrscr;
 write('moi nhap so nguyen duong a=');readln(a);
 write('moi nhap so nguyen duong b=');readln(b);
 writeln('BOI CHUNG NHO NHAT CUA HAI SO DA CHO LA :',BCNN(a,b));
 readln;
END.
Chú ý:
 có thể nhóm hai chương trình 9, 10 thành chương trình sau nếu cần: 
 Program tim_ucln_va_bcnn;
Var i,r,a,b,d,q,p:integer;
Begin
 write('Nhap a= '); readln(a);
 write('Nhap b= '); readln(b);
 r:=a mod b;
 q:=a*b;
 while r0 do
 begin
 a:=b;
 b:=r;
 r:=a mod b;
 end;
 d:=b;
 writeln('uoc chung lon nhat cua a va b la d = ',d);
 p:= q div d;
 writeln('boi chung nho nhat cua hai so la p = ',p);
readln;
end.
11- Nhân hai số trong hệ nhi phân.
program nhan_he_nhi_phan;
uses crt;
var n,p,a,b:integer;
procedure nhan(var a,b:integer);
 var i,n,bi,ci,p:integer;
 begin
 for i:=1 to n-1 do
 if bi=1 then
 ci:=a
 else
 p:=0;
 for i:=0 to n-1 do
 p:=p+ci;
 end;
procedure nhap(var p,n:integer);
 var i:integer;
 begin
 for i:=1 to n do
 readln(p);
 end;
procedure inketqua(var p,n:integer);
 var i:integer;
 begin
 for i:=1 to n do
 write(p:8);
 writeln;
 end;
BEGIN
 clrscr;
 writeln('GIAI THUAT NHAN CAC SO NGUYEN TRONG HE NHI PHAN');
 WRITELN;
 write('moi nhap gia tri cua n=');readln(n);
 write('nhap gia tri bieu dien nhi ohan cua a=');readln(a);
 write('nhap gia tri bieu dien nhi phan cua b=');readln(b);
 writeln('tich cua a va b la p:8');readln(p);
 nhap(p,n);
 inketqua(p,n);readln;
END.
C. kết luận.
 Đề tài ứng dụng công nghệ thông tin vào giảI một số bài toán số học là sự kết hợp chặt chẽ giữa toán học và tin học. Có ý nghĩa quan trọng trong việc củng cố, mở rộng, đào sâu kiến thức cả hai lĩnh vực toán và tin, đồng thời giúp người học rèn luyện kỹ năng giải toán bằng máy tính.
 Giải toán bằng chương trình là công việc rất khó bởi vì có thể thành thạo thuật toán nhưng lựa chọn và sử dụng giải thuật phù hợp để viết thành chương trình thành công tối ưu nhất là rất khó khăn.Do đó qua quá trình này đòi hỏi chúng ta phải hoạt động trí tuệ tích cực, sáng tạo, nhuần nhuyễn giữa toán và tin, từ đó tư duy người học cũng được rèn luyện và phát triển lên nhiều. Làm cho tư duy trở nên mềm dẻo và sáng tạo qua từng bài toá được lập trình.
 Đề tài đã giải thành công được một số bài toán điển hình cơ bản trong chương trình toán học trung học cơ sở, trở thành công cụ hữu ích cho người học trong việc giải các bài toán cần sử dụng kết quả tính toán từ những bài toán cơ bản này. Đã góp phần giải quyết một phần rắc rối trong việc tính các bài toán số học phức tạp ở Trung học cơ sở.
 Mặc dù được sự giúp đỡ nhiệt tình của các thầy cô và các bạn sinh viên và sự nỗ lực của bản thân, nhưng do thời gian có hạn và kiến thức tin học còn nhiều hạn chế nên còn rất nhiều thiếu sót. Do vậy rất mong được sự đóng góp ý kiến của các thầy cô và các bạn cho các đề tài sau được hoàn thiện hơn. Để ngày càng có nhiều công cụ phục vụ đắc lực hơn trong việc giải các bài toán số học.
 Cuối cùng em xin chân thành cảm ơn sự góp ý của các thầy cô khoa Tự Nhiên, khoa Công Nghệ Thông Tin và các bạn sinh viên. Đặc biệt là sự hướng dẫn nhiệt tình của cô giáo thạc sỹ Đặng Thị Hiền để em có thể hoàn thành đề tài này. 
D. tài liệu tham khảo.
 1. Giáo trình cơ sở số học – Nguyễn Tiến Tài – nxb đhsp
 2. Giáo trình lập trình – Nguyễn Xuân My – nxb đhsp
 3. Ngôn ngữ lập trình pascal – Quách Tuấn Ngọc – nxb thống kê
 4. Giáo trình lý thuyết số – Nguyễn hữu Hoan – nxb đhsp.
 5. Giáo trình lý thuyết và bài tập pascal – nxb thống kê.