Thuật toán toán học ứng dụng

ứng dụng lý thuyết Toán để giải các bài toán tin

Lê Nguyễn Tuấn Thành

Như các bạn đã biết, toán học có ảnh hưởng rất lớn đến mọi lĩnh vực của cuộc sống. Các

bài tin nếu có được thuật toán dựa trên cơ sở lí thuyết toán học vững chắc sẽ đem lại kết

quả tốt hơn rất nhiều so với các thuật toán khác. Các bạn có thể tìm thấy nhiều bài tin hay

ứng dụng toán học để giải trên các số báo trước. Trong bài viết này tôi sẽ trao đổi thêm

với các bạn một vài bài tin với các thuật toán dựa trên cơ sở toán học. Các thuật toán tôi

đưa ra có thể chưa tối ưu vì vậy rất mong nhận được sự góp ý của các bạn.

Chúng ta hãy bắt đầu bằng bài toán đơn giản sau:

Bài 1: Tìm tất cả các cặp số nguyên dương x,y,z sao cho x2

+ y2

= z2

. 0< x,y,z ≤10000.

Giải:

Đặt Max là giới hạn trên của x,y,z.

Với bài toán này, chúng ta có thể dùng hai vòng lặp x,y lồng nhau rồi kiểm tra nếu x2

+ y2

là số chính phương thì ghi nhận kết quả. Để giảm bớt số lần lặp ta sẽ cho y>x, mỗi lần ghi

nhận kết quả ta sẽ phải viết ra hai cặp nghiệm. Ta dùng một biến dem để ghi nhận số cặp

x,y,z thoả mãn. Chương trình chính có thể viết như sau:

for x:=1 to Max-2 do

for y:=x+1 to Max-1 do

if trunc(sqrt(sqr(x)+sqr(y)))=sqrt(sqr(x)+sqr(y)) then

if trunc(sqrt(sqr(x)+sqr(y)))<=Max then

begin

z:=trunc(sqrt(sqr(x)+sqr(y)));

inc(dem);

writeln(’Cach thu’,dem);

write(’ x=’,x,’ y=’,y,’ z=’,z);

writeln;

inc(dem);

writeln(’Cach thu ’,dem);

write(’ x=’,y,’ y=’,x,’ z=’,z);

writeln;

end;

writeln(’Co tat cac’,dem,’ cach’);

Song ta có thể dùng cách khác để giải bài toán này. Các bạn hãy để ý điều kiện thoả mãn

của x,y,z: x2+y2

= z2

. Đó chính là phương trình Pitago. Nghiệm của phương trình này có

dạng:

x=t*2*m*n

y=t*(m2

-n2

)

z=t*(m2+n2

)

Với m,n,t là các số nguyên dương; m,n nguyên tố cùng nhau 1 chẵn,1 lẻ. Các bạn có thể

tìm thấy chứng minh trên trong các tài liệu về số học, ở đây tôi không chứng minh lại. Từ

công thức trên ta có một cách làm khác như sau: Ta đi tìm các giá trị có thể có của m,n,t.

Với mỗi bộ ba số m,n,t ta sẽ được hai cặp nghiệm x,y,z. Giả sử n<m.