Tiếp tục thư giãn đầu óc với những bài toán lập trình nhỏ mà mình lấy từ Code Fights. Bài toán hôm nay của chúng ta có nội dung như sau:
Tạm dịch: Cho một số nguyên n. Tính hiệu của bình phương tổng từ 1 đến n và tổng các bình phương từ 1 đến n.
Ví dụ: Cho n = 4
Bình phương tổng từ 1 đến 4: (1 + 2 + 3 + 4)² = 10² = 100
Tổng các bình phương từ 1 đến 4: 1² + 2² + 3² + 4² = 31
Kết quả: 100 – 31 = 69
Bài giải hôm nay mình code bằng C++. Các bạn có thể xem:
1 2 3 4 5 6 7 8 9 10 11 12 | int SumSquareDiff(int n) { int sum_square = 0; int square_sum = 0; int result = 0; for(int i=1; i<=n; i++){ sum_square = sum_square + i * i; square_sum = square_sum + i; } square_sum = square_sum * square_sum; result = square_sum - sum_square; return result; } |
Sau khi post lời giải lên thì mình nhận được một phản hồi của một anh đang là giảng viên bộ môn toán của một trường Cao đẳng đại ý như sau:
Bình phương của tổng từ 1 đến n: n*(n+1)*(2*n+1)/6
Tổng của các bình phương từ 1 đến n: n*(n+1)/2 * [n*(n+1)/2 – (2*n+1)/3]
Sau khi thực hiện phép trừ rồi rút gọn lại công thức ta có biểu thức: n*(n+1)*(3n²-n-2)/12
Rõ ràng đây thật sự là một thuật toán rất tối ưu. Mình xin nhường để các bạn tự code.
Chúc các bạn thành công.
Huỳnh Mai Anh Kiệt
