Gần đây, trong lúc lựa các bài về Mathematics để giải mình tình cờ bắt gặp bài này.
Vấn đề
- Tính tổng các số trong dãy với T(n) = n2 - ( n - 1 )2 = 2n - 1.
- Ta thấy đây là công thức tính ra một số lẽ .
- Nhiệm vụ là tính tổng các số lẽ từ 1 đến n .
Giải quyết
Ta nhận ra đây là một cấp số cộng với công sai bằng 2.
Áp dụng công thức cấp số cộng có thể dễ dàng giải quyết bài toán này với độ phức tạp O(1) như sau:
S = n (1 + 2n - 1)/2 = n2
Ví dụ : n = 3 thì kết quả S = 9.
khó khăn
Với những giá trị n lớn. Ví dụ, với n = 5773408242017850, đáp án mong đợi S(5773408242017850) = 112242846, nhưng phạm vi giá trị lưu trữ dữ liệu lớn nhất của S là 264 - 1 = 18446744073709551615, có độ lớn 64 bit. điều này sẽ làm overflow. Vì vậy ta sẽ dùng modulo để giải quyết vấn đề trên.
để tránh việc tính toán overflow
Như bạn đã biết kiểu dữ liệu int của python có phạm vi lưu trữ lớn nhất là 264 - 1 có độ lớn 64 bit. Và việc làm nhỏ giá trị để phù hợp với kiểu giá trị lưu trữ của chúng ta, hơn là tốn thời gian tìm kiếm và implement các thuật toán xử lý dữ liệu lớn. Vì vậy sử dụng phép tính Modulo sẽ làm đơn giản hoá mọi thứ.
Các phép toán trên modulo với modulo = (109 + 7)
Các phép toán trên modulo với modulo = (109 + 7)
- Phép cộng : (A+B)% modulo = (A% modulo + B% modulo)% modulo
- Phép trừ : (A-B)%mod = (A% modulo + (-B)% modulo)% modulo = (A% modulo - B% modulo + modulo)% modulo
- Phép nhân : (A*B)% modulo = (A% modulo * B% modulo)% modulo
- Phép chia : (A/B)% modulo = (A% modulo * inv(B)% modulo + modulo)% modulo
- với inv(B) = B(modulo-2) % modulo
kết luận
def sum(n):
# kết quả cũng tương tự với
# return (n% 1000000007 * n% 1000000007) % 1000000007
return (n*n)%1000000007 Trong một số bài toán lập trình đôi khi câu trả lời ở dạng n%1000000007, điều này có nghĩa là bạn cần tìm đáp án cho một số quá lớn vượt qua phạm vi số nguyên 64bit mà không thể tính được.
Vì vậy khi gặp những tình huống như thế này chỉ cần làm theo những phép toán trên số modulo ở mỗi bước tính toán của bạn.
Cùng trao đổi
Bình luận bằng tài khoản Google qua Blogger.
Nhận xét
Đăng nhận xét