Mở đầu
-
Toán học + Tin học + Animation = Nghệ thuật 🤩
-
Các bạn còn nhớ CÔNG THỨC TÍNH TỔNG TẤT CẢ CÁC SỐ HẠNG CỦA MỘT CẤP SỐ CỘNG không? 🫣 (Hãy thành thật trước khi xem đáp án)
-
Nếu bạn quên rồi, thì mình tin là bài viết/video này xứng đáng để bạn xem đấy 💯
-
Vì vấn đề ở đây thực ra không phải do trí nhớ của bạn kém. Mà có thể là do bạn chưa hiểu bản chất, hoặc đơn giản là chưa từng tìm cách chứng minh tại sao công thức đó đúng mà thôi.
-
Cùng xem bài viết/video này để không còn phải học gạo, học thuộc công thức toán học đơn giản này nữa nhé!
-
Các bạn có thể xem phiên bản video của bài viết này tại đây:
Toán học trong Lập trình thi đấu
-
Nếu các bạn đã từng tham gia các cuộc thi lập trình thi đấu, thì chắc các bạn cũng biết rằng: Toán học đóng vai trò quan trọng trong các cuộc thi này.
-
Ở Việt Nam cũng có rất nhiều anh tài chuyển từ chuyên Toán sang chuyên Tin như:
-
Lăng Trung Hiếu (Codeforces:
ngfam_kongu
- Max rating Codeforces:2518
) -
Phạm Đức Thắng (Codeforces:
AomeII
- Max rating Codeforces:2372
), -
Nguyễn Đinh Quang Minh (Codeforces:
MofK
- Max rating Codeforces:2726
), -
Vương Hoàng Long (Codeforces:
Lomk
- Max rating Codeforces:2436
) -
...
-
-
Do đó, trong bài viết này và một vài bài viết sắp tới của series "Lên trình Thuật toán - Lập trình thi đấu 🏆", chúng ta sẽ cùng nhau thảo luận về một số khái niệm, công thức toán học quan trọng, và là nền tảng cần thiết cho những kiến thức nâng cao ở phía sau.
Định nghĩa Cấp số cộng (Arithmetic Progression)
-
Cấp số cộng là dãy số thỏa mãn điều kiện: kể từ số thứ 2, mỗi số sẽ đều là tổng của số đứng ngay trước nó với một số không đổi.
-
Trong Toán học, hằng số này thường được viết tắt là
d
(viết tắt của từ common difference - tức là một hiệu số chung), hay tiếng Việt còn gọi là công sai của cấp số cộng. -
Ví dụ ta có dãy số:
1, 3, 5, 7, 9
là một cấp số cộng với hằng số difference
d = 2
-
Để tính tổng tất cả các phần tử của một cấp số cộng, chúng ta có thể sử dụng công thức:
-
Ví dụ với dãy số
1, 3, 5, 7, 9
. Ta sẽ tính được tổng của dãy số này là:1 + 3 + 5 + 7 + 9 = (1 + 9) * 5 / 2 = 25
-
Nếu mình nhớ không nhầm thì công thức này chúng ta đã được học từ hồi học cấp 1.
-
Nhưng đây là trong trường hợp mình còn nhớ công thức này, nhưng giả sử một vài năm nữa mình lớn tuổi hơn, trí nhớ kém hơn, thì sao nhỉ?
-
Mình sẽ chỉ cho các bạn 1 cách suy luận logic để suy ra được công thức này mà không cần phải học gạo, học thuộc nữa.
Suy luận logic để suy ra công thức
-
Quay lại với dãy số lúc nãy, mình muốn tính tổng:
1 + 3 + 5 + 7 + 9
-
Mình sẽ biểu diễn chúng dưới dạng các hình vuông xếp chồng lên nhau 🟥:
-
Số 1 tương ứng với 1 hình vuông
-
Số 3 tương ứng với 3 hình vuông
-
Số 5 tương ứng với 5 hình vuông
-
Số 7 tương ứng với 7 hình vuông
-
Số 9 tương ứng với 9 hình vuông
-
-
Tiếp đến, mình sẽ nhân đôi dãy các hình vuông này lên:
-
Lúc này, nó cũng giống như việc mình lấy 2 nhân với (tổng các số ban đầu), tức là:
2 x (1 + 3 + 5 + 7 + 9)
-
Và khi mình lật ngược lại dãy các hình vuông bên dưới thành như thế này. Các bạn đã nhìn ra điều đặc biệt ở đây chưa nào?
-
Tổng của các cặp số này đều bằng nhau.
-
Ví dụ:
-
Cặp đầu tiên là
1 + 9 = 10
-
Cặp thứ hai là
3 + 7 = 10
-
Cặp thứ ba, cặp thứ tư, cặp thứ 5 cũng như vậy.
-
-
Nên về bản chất, nó cũng giống như mình đang tính 5 lần tổng của cặp đầu tiên, tức là:
5 x (1 + 9)
-
Giờ thì chắc hẳn các bạn đã hiểu rồi đúng không nào?
-
Chúng ta có:
2 x (1 + 3 + 5 + 7 + 9) = 5 x (1 + 9)
-
Chuyển vế số
2
sang bên phải, ta sẽ được là1 + 3 + 5 + 7 + 9 = 5 x (1 + 9) / 2
-
Và đây cũng chính là lý do chúng ta có công thức tính tổng các số hạng của cấp số cộng là:
- Với số đầu ở đây là
1
- Số cuối là
9
- Số số hạng là
5
(vì dãy nãy gồm 5 số hạng là1, 3, 5, 7, 9
)
- Với số đầu ở đây là