30/09/2018, 18:26
Thuật toán tối ưu trong một bài toán đơn giản
Mình vừa đọc qua một bài toán trên mạng có nội dung như sau:
- Tính tổng tất cả các số 0->999 chia hết cho 3 hoặc 5
Mình nghĩ ngay tới đoạn code:
#include "stdio.h"
int main(int argc, char const *argv[])
{
int s, i = 0;
while (i<1000){
if (i % 3 == 0 || i % 5 == 0){
s += i;
}
i++;
}
printf("%d
", s);
return 0;
}
Nhưng tác giả nói rằng cách này không tối ưu và đoạn code của a ta là:
#include "stdio.h"
int sum(int n){
int target = 999;
int p = target/n;
return n*(p*(p+1))/2;
}
int main(int argc, char const *argv[])
{
printf("%d
", sum(3) + sum(5) - sum(15));
return 0;
}
Vậy liệu nó có thực sự tối ưu hơn đoạn code của tôi? Và phải chăng còn có đoạn mã tối ưu hơn nữa cho bài toán đơn giản này? Mong các bạn giải đáp thắc mắc dùm mình. Cảm ơn rất nhiều!
Bài liên quan
Tối ưu hơn là chắc rồi: của bạn độ phức tạp là O(n). còn người ta là O(1). mà người ta làm hay thật : ))
Tối ưu ở đây có nghĩa là tốc độ thực hiện bài toán của máy tính.
Vậy ta biết cái nào tối ưu hơn rồi !!!
thuật toán 2 hay vậy.
Toán đấy đầu tiên từ 3 tới 3n là n số, hay số số là n*(3n+3) / 2.
Sau đó dùng quy tắc thêm bớt (1, 3, 5,… phép giao là dấu trừ) để tính kết quả cuối cùng.
như vậy là giỏi toán mới có thể nghĩ ra đc cách 2 phải ko ạ, chứ em chịu cách 2 lun ik
Phải nói là ông kia nghĩ ra công thức hay thật đấy. Nhưng nếu làm trâu bạn vẫn có thể tối ưu hơn.
p/s: Cách này số lần loop sẽ giảm đi 3 lần.
Lưu ý: Mình có lôi code bạn về để kiểm tra kết quả thì bạn code bạn sai vì chưa khởi tạo giá trị ban đầu cho biến
sBài này xét về kiến thức toán thì THCS (lớp 7) cũng suy ra được có vững căn bản không mà thôi.
Phần tập hợp thì có thể vẽ giản đồ, nhưng phát biểu tổng quát sẽ hay hơn.
Đây là bài toán cơ bản trong arithmetic progression. Mình viết lại cách suy nghĩ cho các bạn nào chưa hiểu nha.
Tổng số từ 1 -> 999 chia hết cho 3 và 5 có thể tách ra 3 vế:
sum(3) + sum(5) - sum(15) => tổng các số chia hết cho 3 + tổng các số chia hết cho 5 và trừ đi tổng các số chia hết cho 15 ( vì chia hết cho 15 chắc chắn sẽ chia hết cho 3 hoặc 5)
Để tính sum(3) chúng ta thấy các số như sau:
s = { 3 , 6, 9, 12, … , 996, 999} các số trong chuỗi này đều chia hết cho 3
Đặt 3 ra khỏi chuỗi số chúng ta sẽ có
s = 3 {1, 2, 3,…, 333}
Tương tự với chuỗi chia hết cho 5 và 15
5{1, 2, 3,…,199)
15{1, 2, 3, …, 66}
Như vậy chúng ta phải tính tổng của 1 + 2 + 3 +…+ n
Công thức để tính là : n*(n+1)/2Số cuối cùng của mỗi chuỗi là n = 999/ 3 với chuỗi số chia hết cho 3; n= 999/5 với chuỗi 5; n = 999/15 với chuỗi 15.
Như vậy công thức sẽ gom thành thuật toán