Bài 1: Series luyện giải thuật theo từng bài tập


Giới thiệu về series một chút. Trong series này, chúng ta sẽ hoàn thành từng bài tập một theo cách của mình, sau đó chúng tôi sẽ đưa ra những giải pháp tốt hơn để giải quyết vấn đề. Hay nói cách khác, với một cách thông thường mà chúng ta giải quyết bài toán mà trình biên dịch sẽ chạy với thời gian t, nhưng sau khi hiểu và áp dụng các giải thuật thì bài toán thực hiện với thời gian t’ với t’ << t. Trong series này chúng tôi sẽ sử dụng ngôn ngữ C. Các bạn có thể sử dụng một ngôn ngữ khác mà các bạn thành thục nhất! Và trong series này, chúng ta cũng sẽ được học thêm về ngôn ngữ c.
Nguồn cung cấp: projecteuler.net

Đề bài: Nếu liệt kê tất cả các số tự nhiên nhỏ hơn 10 mà là bội của 3 hoặc 5, chúng ta sẽ có: 3, 5, 6, 9. Tính tổng các số lại thì bằng 23. Tìm tổng của tất cả các bội số của 3 hoặc 5 nhỏ hơn 1000.
Đáp số: 233168

Giải thuật thông thường

target=999 
sum=0 
for  i=1 to target do 
    if (i mod 3=0) or (i mod 5)=0 then 
        sum:=sum+i 
output sum

Code như sau:

#include <stdio.h>
// Khai báo hàm
int sumOfMultiples(int);

// Hàm main
int main(int argc, char *argv[])
{
	printf("%d", sumOfMultiples(999));
	return 0;
}

// Hàm tính tổng các bội số của 3 hoặc 5
int sumOfMultiples(int n)
{
	int i = 1;
	int result = 0;
	for(i; i <= n; i++)
	{
		if((i % 3 == 0) || (i % 5 == 0))
		{
			result += i;
		}
	}
	return result;
}

Các bạn có thể thực hiện chương trình trên CodeBlock hay bất kì IDE nào để xem thời gian mà compiler biên dịch.

Và bây giờ, chúng ta sẽ tìm kiếm giải thuật tối ưu nhất cho bài toán này. Bởi vì bài toán chỉ yêu cầu các số nhỏ hơn 1000, vậy khi các số nhỏ hơn 1 tỷ thì sao. Không biết sẽ mất bao nhiêu thời gian nữa.

Phân tích
Để tính tổng như vậy, chúng ta chỉ cần tính tổng các số nhỏ hơn 1000 và chia hết cho 3 (gọi là SumDivisibleBy(3)), sau đó cộng với tổng các số nhỏ hơn 1000 mà chia hết cho 5 (gọi là SumDivisibleBy(5)).
Nhưng những số nhỏ hơn 1000 mà chia hết cho 15 (gọi là SumDivisibleBy(15)) thì đều chia hết cho 3 và 5 nên sẽ xuất hiện ở SumDivisibleBy(3) và SumDivisibleBy(5).
Nên kết quả cuối cùng: SumDivisibleBy(3)+ SumDivisibleBy(5) – SumDivisibleBy(5).

Chúng ta lại có:
3+6+9+12+……+999=3*(1+2+3+4+…+333)

5+10+15+…+995=5*(1+2+….+199)
Chú ý rằng 199=995/5 hay 199=999div5

Công thức cấp số cộng thì như sau: 1+2+3+…+p=½*p*(p+1)

Giải thuật cuối cùng

target=999
Function SumDivisibleBy(n)  
    p=target div n  
    return n*(p*(p+1)) div 2 
EndFunction
Output SumDivisibleBy(3)+SumDivisibleBy(5)-SumDivisibleBy(15)

Chương trình C sẽ như sau:

#include <stdio.h>
int sumOfMultiples(int);
int target = 999;
int main(int argc, char *argv[])
{
	printf("%d", 
		sumOfMultiples(3) + sumOfMultiples(5) - sumOfMultiples(15));
	return 0;
}

int sumOfMultiples(int n)
{
	int p = target / n;
	return (n * p * (p + 1) / 2);
}

Các bạn hãy kiểm tra tốc độ biên dịch chương trình nhé, thử và cảm nhận!

END

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s