Mathematics for Topcoders Phần 2

Như ở bài trước tối giới thiệu về các thuật toán và cách tối ưu sao cho có hiệu suất tốt nhất có thể như tìm số nguyên tố, tìm ước chung lớn nhất của hai số ... Thuật toán tiếp theo tôi sẽ giới thiệu là Geometry Chúng ta cũng thường có bài toán là tìm giao của hình chữ nhật. Có nhiều cách để thể hiện một hình chữ nhật. Đối với mặt phẳng Đề cát chuẩn thì phương pháp phổ biến nhất là lưu tọa độ các điểm góc dưới bên trái và gọc trên bên phải.

Giả sử có hai hình chữ nhật R1 và R2. Gọi (X1, Y1) là tọa độ của đỉnh góc dưới bên trái của hình chữ nhật R1, (X2, Y2) là tọa độ của đỉnh góc trên bên phải của hình chữ nhật R1. Tương tự gọi (X3, Y3) và (X4, Y4) lần lượt là tọa độ của các đỉnh góc dưới bên trái và góc trên bên phải của hình chữ nhật R2. Giao của hai hình chữ nhật R1 và R2 là hình chữ nhật R3 với tọa độ của đỉnh góc dưới bên trái là tạo max của (X1, Y1) và (X3, Y3) và tọa độ của đỉnh góc trên bên phải là min (X2, Y2) và (X4, Y4). Trong trường hợp max(X1, X3) > min(X2, X4) hoặc max(Y1, Y3) > min(y2, y4) thì hai hình chữ nhật R1 và R2 không giao nhau. Phương pháp này còn được mở rộng để tìm kiếm giao của nhiều hơn 2 kích thước như được trình bày trong CuboidJoin (SRM 191, Div 2 Hard)

Thường thì chúng ta phải làm việc với các đa giác mà chứa trong nó là các tọa độ nguyên. Những đa giác như vậy gọi là đa giác lưới. Trong hướng dẫn của Ông về khái niệm hình học, lbackstrom đưa ra cách gọn gàng để tìm ra diện tích của một đa giác lưới. Bây giờ, giả sử chúng ta không biết chính xác vị trí của các đình và thay vào đó chúng ta đứa ra hai giá trị

B = Tổng số các cạnh trong đa giác lưới
I = Tổng số các điểm các đỉnh lưới ở bên trong đa giác lưới.

Area = B/2 + I -1

Công thức trên được gọi là định lý của Pích được đưa ra bởi Géc-giơ A-léc-xan-đơ-Pích (1859-1943).

Bases Còn một vấn đề chung của các Topecoder đó là việc chuyển đổi qua lại giữa số nhị phân và số thập phân.

Vì vậy cơ số chuẩn ở đây là số nào. Chúng ta bắt đầu làm việc với cơ số chuẩn (hệ thập phân). Giả sử số thập phân 4325. Số 4325 được biểu diễn bằng 5 + 2 x 10 + 3 x 10 x 10 + 4 x 10 x 10 x 10. Chú ý rằng giá trị của mỗi số tăng theo hệ số 10 từ phải qua trái. Số nhị phân cũng được biểu diễn tương tự nhưng cơ số ở đây là cơ số 2. Giả sử 1011 trong hệ cơ số thập phân được biểu diễn cho 1 + 1 x 2 + 0 x 2 x 2 + 1 x 2 x 2 x 2 = 1 + 2 + 8 = 11 trong hệ cơ số 10. Chúng ta vừa chuyển từ số nhị phân sang số thập phân. Đây là đoạn code chuyển từ số hệ b sang số hệ 10 ( 2<=b<=10) .

public int toDecimal(int n, int b)
{
   int result=0;
   int multiplier=1;
      
   while(n>0)
   {
      result+=n%10*multiplier;
      multiplier*=b;
      n/=10;
   }
      
   return result;
}

Đối với những người dùng java thật là may mắn vì hàm trên đã được có sẵn.

return Integer.parseInt(""+n,b);

Để chuyển từ số thập phần sang số nhị phân thật là dễ dàng. Giả sử chúng ta muốn chuyển số 43 sang số nhị phân. Mỗi bước của phương pháp, chúng ta chia 43 cho 2 và lưu lại số dư. Một danh sách các số dư cuối cùng sẽ là số nhị phân cần tìm.

43/2 = 21 + remainder 1
21/2 = 10 + remainder 1
10/2 = 5  + remainder 0
5/2  = 2  + remainder 1
2/2  = 1  + remainder 0
1/2  = 0  + remainder 1

Nếu cơ số b là lớn hơn 10 thì chúng ta phải sử dụng các chữ cái để biểu diễn chữ số đó. Những số đó có gía trị lớn hơn 10. Chúng ta đặt 'A' = 10, 'B' = 11 ... .Đoạn code sau để chuyển từ cơ số 10 sang bất kỳ cơ số nào ( đến cơ số 20).

public String fromDecimal2(int n, int b)
{
   String chars="0123456789ABCDEFGHIJ";
   String result="";
      
   while(n>0)
   {
      result=chars.charAt(n%b) + result;
      n/=b;
   }
      
   return result;
}

Trong java có các hàm rất hữu ích đểu chuyển từ hệ cố số 10 sang các cơ số khác như 2, 8, 16.

Integer.toBinaryString(n);
Integer.toOctalString(n);
Integer.toHexString(n);

Fractions and Complex Numbers

Phân số cũng có nhiều vấn đề được quan tâm. Có lẽ khía cạnh khó khăn nhân cần phải giải quyết về phần phân số là tìm ra cách tốt nhất để thể hiện phân số. Mặc dù có thể tạo một lớp phân số chứa các hàm và thuộc tính cần thiết. Hầu hết thì phân số được biểu diễn như hai mảng các phần tử. Trong cách này thì tử số được biểu diễn bởi phần tư thứ nhất, mẫu số được biểu diễn bởi phẩn tử thứ 2.

Chúng ta sẽ bắt đầu với phép nhân 2 phân số.

public int[] multiplyFractions(int[] a, int[] b)
{
   int[] c={a[0]*b[0], a[1]*b[1]};
   return c;
}

Phép cộng 2 phần số thì phức tạp hơn phép nhân một chút, vì chỉ những phân số có cùng mẫu số mới có thể thực hiện phép cộng với nhau. Trước tiên chúng ta phải tìm mẫu chung của hai phân số. Và sau đó sử dụng phép nhân để biến đổi các phân số về cùng chung có mẫu số. Mẫu số chung là một số có thể chia hết cho cả hai mẫu số và đơn giản nhất là bội số chung nhỏ nhất của ai mẫu số. Ví dụ thực hiện phép cộng 2 phân số 4/9 và 1/6. Mẫu chung nhỏ nhất của 9 và 6 là 18. Vì vậy cần biến đổi phân số thứ nhất chúng ta cần phải nhấn nó với 2/2 và nhân phân số thứ hai với 3/3.

4/9 + 1/6 = (4*2)/(9 * 2) + (1 * 3)/(6 * 3) =  8/18 +  3/18

Khi cả hai phân số có cùng mẫu số. Việc đơn giản của chúng ta là cộng hai tử số với nhau. Đối với phép trừ hai phân số cũng vậy.

4/9 - 1/6 =  8/18 -  3/18 =  5/18

dưới đây là đoạn code cộng hai phân số với nhau.

public int[] addFractions(int[] a, int[] b)
{
   int denom=LCM(a[1],b[1]);
   int[] c={denom/a[1]*a[0] + denom/b[1]*b[0], denom};
   return c;
}

Cuối cùng chúng ta phải tối giản phân số. Phân số tối giản nhất khi ước chung lớn nhất của tử số và mẫu số là 1.

public void reduceFraction(int[] a)
{
   int b=GCD(a[0],a[1]);
   a[0]/=b;
   a[1]/=b;
}

Với cách tiếp cận tương tự, chúng ta có thể biểu diễn các số đặc biệt khác như số phức tạp. Nhìn chung, số phức tạp là số có dạng a + bi trong đó a, b là các số thực còn i là căn bậc 2 của -1. Ví dụ để cộng hai số phức m = a + ib, n = c + id. Chúng ta làm theo cách sau.

m + n
= (a + ib) + (c + id)
= (a + c) + i(b + d)

Nhân hai số phức cũng như nhân hai số thực. Ngoại trừ trường hợp. i^2 = -1.

m * n
= (a + ib) * (c + id)
= ac + iad + ibc + (i^2)bd
= (ac - bd) + i(ad + bc)

đây là đoạn code nhân hai số thực

public int[] multiplyComplex(int[] m, int[] n)
{
   int[] prod = {m[0]*n[0] - m[1]*n[1], m[0]*n[1] + m[1]*n[0]};
   return prod;
}

Bài viết tham khảo ở https://www.topcoder.com/community/data-science/data-science-tutorials/mathematics-for-topcoders/