Các công thức toán học trong lập trình

Các bạn thân mền

Trong lập trình thi đấu, kỹ năng tư duy và cài đặt rất quan trọng trong lập trình thi đấu. Ngoài ra khả năng vận dụng các công thức toán học một cách linh hoạt và chính xác cũng là một trong những kĩ năng mà mỗi người cần phải thành thạo. Các công thức về số học, tổ hợp, đại số, hình học hay xác suất không chỉ giúp giải quyết bài toán hiệu quả hơn mà còn mở ra những hướng đi tối ưu khi thời gian và tài nguyên bị giới hạn. Bài viết này sẽ cùng tìm hiểu các công thức toán học trong lập trình thi đấu mà ai cũng nên nắm vững.

Oke (●’◡’●) , chúng ta bắt đầu thôi

Mục lục

1) Các công thức tính tổng các dãy số:

a)Tổng

$$ 1 + 2 + … + n = frac{n(n+1)}{2}$$

b)Tổng bình phương:

$$1^2 + 2^2 + ldots + n^2 = frac{n(n+1)(2n+1)}{6}$$

c)Tổng lập phương:

$$1^2 + 2^2 + ldots + n^2 = frac{n(n+1)(2n+1)}{6}$$

2) Các phép thay thế cho phép chia dư

Một cách tổng thể, thì phép chia dư làm cho thời gian chạy của chương trình bị giảm đi tương đối, nên một công thức thay thế nó thật sự cần thiết:

Nếu a và b là số nguyên:

$${a} – left(frac{a}{b}right) * {b}$$

Nếu như a âm :

$$ (a % b + b) % b $$

(cách này sẽ đưa số dư về số dương)

3) Phép đồng dư

* Đây là phép không xuất hiện trong chương trình phổ thông, nhưng những ai đã học và ôn thi chương trình chuyên Toán sẽ không xa lạ nữa, nhưng đây lại là phép tính thật sự quan trọng khi các bạn học lập trình thi đấu, nên mình sẽ tổng hợp lại về phép đồng dư

a)Cho 3 số nguyên a, b, và m > 0. Nếu:

$$a equiv b (text{mod} m)$$

Ta nói: a đồng dư với b mod m, nếu:

$${a} – {b}$$

chia hết cho m
Hay :

$$a % m = b % m$$

( a chia cho m có số dư bằng b chia cho m)

b)Tính chất phép đồng dư:

Nếu :

$$a equiv b (text{mod} m)$$

và

$$c equiv d (text{mod} m)$$

Thì:

$$a+c equiv b+d (text{mod} m)$$
$$a-c equiv b-d (text{mod} m)$$
$$a*c equiv b*d (text{mod} m)$$

Nếu

$$ c neq 0 $$

và c có nghịch đạo modulo thì:

$$ frac{a}{c} equiv frac{b}{d} pmod{m} $$

*Nghịch đảo modulo:

Cho 2 số nguyên a và m, với m > 1.

Nghịch đảo modulo của a theo modulo m là một số nguyên x sao cho:

$$a*x equiv 1 (text{mod} m)$$

Khi đó, ta gọi x là nghịch đảo modulo của a theo mod m, và viết là:

$$x equiv a^{-1} (text{mod} m)$$

Đồng dư là một công cụ toán học cực kỳ quan trọng trong lập trình thi đấu, đặc biệt khi làm việc với những bài toán liên quan đến chia hết, số dư, hoặc xử lý các số rất lớn. Kỹ thuật này giúp đơn giản hóa các phép toán bằng cách làm việc với phần dư theo một mô-đun cho trước, từ đó tránh được hiện tượng tràn số và tăng tốc độ tính toán. Ngoài ra, đồng dư còn đóng vai trò nền tảng trong nhiều thuật toán phổ biến như tính lũy thừa nhanh, nghịch đảo modulo, hệ phương trình đồng dư (áp dụng trong Định lý phần dư Trung Hoa) và thuật toán Euclid mở rộng.

4) Tổ hợp, chỉnh hợp

4.1) Công thức tổ hợp cơ bản

Số cách chọn ( k ) phần tử từ ( n ) phần tử (không phân biệt thứ tự) được tính bằng:

[
C(n, k) = binom{n}{k} = frac{n!}{k!(n-k)!}
]

4.2) Công thức chỉnh hợp

Số cách chọn và sắp xếp ( k ) phần tử từ ( n ) phần tử (có phân biệt thứ tự) là:

[
A(n, k) = frac{n!}{(n-k)!}
]

4.3) Công thức tổ hợp lặp

Khi cho phép chọn lặp lại các phần tử, số cách chọn ( k ) phần tử từ ( n ) phần tử là:

[
H(n, k) = binom{n+k-1}{k}
]

4.4) Một số tính chất quan trọng

Định lý Pascal:
[
binom{n}{k} = binom{n-1}{k} + binom{n-1}{k-1}
]
Công thức đối xứng:
[
binom{n}{k} = binom{n}{n-k}
]
Giá trị biên:
[
binom{n}{0} = binom{n}{n} = 1
]

5. Ứng dụng trong lập trình thi đấu

Các công thức tổ hợp thường được dùng trong:

Tính số cách sắp xếp hoặc chọn đội hình.
Bài toán phân chia nhóm, chia quà, hoặc chia bài.

Việc tối ưu hóa tính toán các giá trị tổ hợp thường đòi hỏi tiền xử lý giai thừa và nghịch đảo giai thừa modulo một số nguyên lớn, đặc biệt trong các bài toán có ràng buộc lớn như ( n leq 10^5 ) hoặc ( n leq 10^6 ).

5) Logarit

Cho hai số thực dương ( a ) và ( b ) với ( a neq 1 ), logarit cơ số ( a ) của ( b ) là số ( x ) sao cho:

[
a^x = b
]

Ký hiệu:

[
x = log_a b
]

a. Các công thức cơ bản

Logarit của một tích:
[
log_a (bc) = log_a b + log_a c
]
Logarit của một thương:
[
log_a left( frac{b}{c} right) = log_a b – log_a c
]
Logarit của một lũy thừa:
[
log_a (b^n) = n log_a b
]
Đổi cơ số:
[
log_a b = frac{log_c b}{log_c a}
] (thường đổi về cơ số 10 hoặc cơ số ( e ) cho dễ tính toán)

b. Vai trò của Logarit trong Lập trình Thi đấu

Logarit thường hay dùng để Phân tích độ phức tạp thuật toán, đặc biệt trong các thuật toán nhị phân, chia để trị (ví dụ: tìm kiếm nhị phân có độ phức tạp ( O(log n) ).

6) Các công thức liên quan tới hệ trục toạ độ

Các biểu diễn đồ thị hàm số:

1)Đồ thị bậc nhất

$$y=a*x+b$$

Đồ thị là một đường thẳng:

Cho một điểm A(m,n)

Nếu $$ n = am + b $$ Điểm A thuộc đường thẳng
Nếu

$$ n > am + b $$

Điểm A nằm bên trên đường thẳng

Nếu

$$ n < am + b $$

Điểm A nằm bên dưới đường thẳng

2)Đồ thị bậc 2

$$y=ax^{2}+bx+c$$

Đồ thị là một parabol

Cho một điểm A(m,n)

Nếu
$$y=ax^{2}+bx+c$$ Điểm A thuộc parabol
Nếu $$y>ax^{2}+bx+c$$ Điểm A nằm bên trên/ trong parabol

Nếu :$$y<ax^{2}+bx+c$$Điểm A nằm bên dưới parabol

3) Phương trình đường tròn

$$ left(x-aright)^2+left(y-bright)^2=R^2 $$

Đồ thì là một đường tròn có tâm là (a,b)

Xét điểm A(m,n):

Nếu

$$ left(x-aright)^2+left(y-bright)^2=R^2 $$

Thì A thuốc đường tròn

Nếu

$$ left(x-aright)^2+left(y-bright)^2>R^2 $$

Thì điểm A nằm ngoài đường tròn

Nếu:

$$ left(x-aright)^2+left(y-bright)^2<R^2 $$

Thì điểm A nằm trong đường tròn

Mỗi công thức không chỉ là một công cụ giải bài, mà còn là chiếc chìa khóa mở ra những cánh cửa tư duy sâu sắc và đột phá. Khi nắm chắc trong tay những định lý, những phép biến đổi tinh tế, bạn không chỉ nhanh hơn, chính xác hơn mà còn mạnh mẽ hơn trên hành trình chinh phục lập trình thi đấu. Hi vọng với những công thức trên, việc học lập trình thi đấu của các bạn sẽ dễ dàng hơn.
Chúc các bạn thành công.
Và đừng quên hãy tham khảo thêm các thuật toán tại đây nhé