Thuật toán tối ưu trong một bài toán đơn giản

#1

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\n", 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\n", 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!

1 Like
#2

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 : ))

1 Like
#3

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ới đoạn code của bạn máy tính sẽ phải thực hiện 1000 vòng lặp và hàng trăm phép tính (tương ứng với mỗi vòng lặp đúng điều kiện)
  • Đoạn code của tác giả thì máy chỉ cần tính vài biểu thức đơn giản.
    Vậy ta biết cái nào tối ưu hơn rồi !!! :joy:
#4

thuật toán 2 hay vậy.

#5

Toán đấy :smiley: đầ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.

2 Likes
#6

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

#7

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.

long long sum = 0;
for(int i = 3, j =5;i < 1000 || j < 1000; i += 3, j += 5){
   if(i < 1000) sum += i;
   if(j < 1000) sum += j;
}

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 s

#8

Bài này xét về kiến thức toán thì THCS (lớp 7) cũng suy ra được :smiley: 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.

1 Like
#9

Đâ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)/2
Số 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

int sum(int divisibleNumber){
	int target = 999;
	int n = target/divisibleNumber;
	return divisibleNumber*(n*(n+1))/2;
}
3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?