Mathematics for Topcoders [Phần 1]

Giới thiệu

Toán học trong lập trình là một vấn đề mà rất nhiều người tham gia các cuộc thi của topcoder.co thường phàn nàn rằng thật là không công bằng vì họ thường gặp vấn đề về toán học. Nhưng theo tôi toán học và khoa học máy tính là luôn đi với nhau. Thật là khó mà tưởng tượng được rằng một thế giới mà ờ đó 2 lĩnh vực toán học và khoa học máy tính có thể tồn tại mà không có sự tương tác lẫn nhau. Ngày nay, có rất nhiều các ứng dụng toán học được thực hiện trên máy tính để giải quyết các vấn đề của hệ thống lớn như giải phương trình và phương trình vi phân mà không có một công thức nào có thể giải quyết nổi. Toán học được sử dụng rộng rãi trong nghiên cứu khoa học máy tính cũng như được đâu tư áp dụng cho các thuật toán đồ thị và các vùng thị giác máy tính.

Số nguyên tố

Một số nguyên tố là số chỉ chia hết cho một và chính nó. Ví dụ như 2, 3, 5, 79, 311 và 1931 là các số nguyên tố. Trong khi đó 21 không phải là số nguyên tố bởi vì nó chia hết cho 3 và 7. Để tìm xem một số có phải là số nguyên tố hay không chúng ta phải kiểm tra xem nó có chia hết cho bất kỳ số nào nhỏ hơn nó không. Chúng ta có thể sử dụng phép toán % để kiểm tra khả năng chia hết của nó.

for (int i=2; i<n; i++)
   if (n%i==0) return false;

return true;

Chúng ta có thể cải thiện thuật toán tốt hơn bằng cách chỉ kiểm tra khả năng chia hết của số cần kiểm tra với các số nhở hơn căn bậc 2 của chính nó. Vì nếu số ta cần kiểm tra chia hết cho một số lớn hơn căn bậc 2 của nó thì kết quả trả về sẽ là một số nhỏ hơn căn bậc 2 của chính nó vì vậy ta chỉ cần kiểm tra xem nó có chia hết cho bất kỳ số nào nhỏ hơn căn bậc 2 của nó không thôi. Còn một cách khác để tối ưu hóa thuật toán đó là không có số chẵn nguyên tố nào lớn hơn 2. Vậy đầu tiên chúng ta kiểm tra xem nó có phải là số chẵn không và có lớn hơn 2 hay không. Và đây là hàm đã tối ưu để kiểm tra số nguyên tố.

public boolean isPrime (int n)
{
   if (n<=1) return false;
   if (n==2) return true;
   if (n%2==0) return false;
   int m=Math.sqrt(n);

   for (int i=3; i<=m; i+=2)
      if (n%i==0)
         return false;

   return true;
}

Và bây giờ chúng ta có một vấn đề hay được nói đến ở phần số nguyên tố đó là tìm các số nguyên tố trong khoảng từ 1 đến 1 số bất kỳ. và số bất kì ở đây có thể là 100000 hay thậm trí là 10000000. Vấn đề xảy ra là khi số bất kỳ quá lớn ví dụ là 100000, thi chúng ta sẽ phải gọi lại hàm kia lập đi lặp lại 100000 lần và đó là hoàn toàn không hiệu quả cho dù hàm trên có hiệu quả đi chăng nữa. Nhưng trong tình huống này có một cách giải quyết rất hiệu quả đó là The Sieve of Eratosthenes(Sáng Ơ-ra-tô-xten). The Sieve of Eratosthense(Sáng Ơ-ra-tô-xten) sẽ coi tất cả các số từ 2 đến n là các số nguyên tố. Nó kiểm tra số đầu tiên là số nguyên tố và xóa tất cả các số là bội số của nó đi. Và tiếp tục áp dụng phương pháp vừa rồi với số tiếp theo trong dãy các số cần kiểm tra từ 2 -> n. Và cứ tiếp tục cho đến tất cả các số trong dãy đều được thực hiện phương pháp trên. Ví dụ, giả sử rằng tìm các số nguyên tố từ 2 đến 20. Chúng ta bắt đầu viết tất cả các số đó xuống.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

2 là số nguyên tố đầu tiên. Và bây giờ chúng ta kiểm tra tất cả các số là bội của nó trong dãy trên nếu số nào là bội của nó thì ta đánh dấu không phải là số nguyên tố.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Số nguyên tố tiếp theo được thực hiện kiểm tra là 3 vì 3 không phải là bội của 2. và thực hiện cùng phương pháp trên với 3.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Tất cả các số được đánh dấu là số nguyên tố còn lại sau khi thực hiện phương pháp trên là số nguyên tố và chúng ta có thể kết thúc thuật toán ở đây. Dưới đây là đoạn code cho phương pháp trên.

public boolean[] sieve(int n)
{
   boolean[] prime=new boolean[n+1];
   Arrays.fill(prime,true);
   prime[0]=false;
   prime[1]=false;
   int m=Math.sqrt(n);

   for (int i=2; i<=m; i++)
      if (prime[i])
         for (int k=i*i; k<=n; k+=i)
            prime[k]=false;

   return prime;
} 

Trong hàm trên. Chúng ta tạo ra một mảng boolean có kích thước nhỏ hơn n. Nếu prime[i] là true thì i là số nguyên tố. Các vòng lặp ngoài tìm ra các số nguyên tố tiếp theo trong khi đó vòng lặp trong sẽ loại bỏ hết các số không phải là số nguyên tố.

GCD

Ước chung lớn nhất của hai số là số lớn nhất mà hai số a và b đều chia hết. Có một cách khá đơn giản để tìm bội chung nhỏ nhất của hai số đó là từ số nhỏ hơn trong hai số và giảm dần xuống đến khi tìm được số nào mà cả hai số đều chia hiết thì số đó là ước chung lớn nhất của hai số.

for (int i=Math.min(a,b); i>=1; i--)
   if (a%i==0 && b%i==0)
      return i;

Mặc dù rất nhiều ứng dụng đã sử dụng cách trên để tìm ước chung lớn nhất của hai số. Nhưng chúng ta vẫn còn một phương pháp nhanh hơn gọi là thuật toán Euclid. Thuật toán Euclid đó là lặp trên hai số cho đến khi số dư còn lại bằng 0. Ví dụ, giả sử chúng ta tìm ước chung lớn nhất của hai số 2336 và 1314. Chúng ta bắt đầu bằng việc biểu diễn số lớn hơn 2336 bằng số bé hơn 1314 nhân với một số nào đó và cộng với phần dư.

2336 = 1314 x 1 + 1022

Ta tiếp tục làm lại với 1314 và 1022

1314 = 1022 x 1 + 292

Ta tiếp tục quá trình cho đến khi số dư còn lại là 0

1022 = 292 x 3 + 146
292 = 146 x 2 + 0

Số cuối cùng với số dư là 0 chính là ước chung lớn nhất. Vậy ước chung lớn nhất của 2 số 2336 và 1314 là 146. Thuật toán trên có thể dễ dàng triển khai bằng phương pháp đệ quy.

//assume that a and b cannot both be 0
public int GCD(int a, int b)
{
   if (b==0) return a;
   return GCD(b,a%b);
}

Thuật toán trên còn được sử dụng để tìm bội chung lớn nhất của hai số. Ví dụ bội chung lớn nhất của hai số 6 và 9 là 18. vì 18 là số nhỏ nhất có thể chia hết cho 6 và 9. Và đây là đoạn code để tìm bội chung lớn nhất của hai số.

public int LCM(int a, int b)
{
   return b*a/GCD(a,b);
}

Có một chú ý cuối cùng đó là thuật toán Euclid còn được sử dụng để giải phương trình tuần tự Diophantine. Các phương trình đó là các phường trình có dạng.

ax + by = c

Còn một số bài toán về toán học nữa tôi xin phép trình bày ở phần tiếp theo.

Nguồn

https://www.topcoder.com/community/data-science/data-science-tutorials/mathematics-for-topcoders/