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


Bài hôm nay là một bài khá kinh điển: dãy số Fibonacci. Trong bài này chúng tôi đưa ra một kiến thức mới cũng khá khó đó là đệ quy (recursion). Các bạn nên tìm hiểu về kiến thức này trước, vì nó cũng là một trong những phần quan trọng trong lập trình và giải thuật.
Chúng tôi sẽ không hướng dẫn về đệ quy trong bài viết này, các bạn có thể đợi ở một bài viết khác hoặc tìm kiếm trên internet.
Chúng ta bắt đầu với bài tập hôm nay!

Đề bài: MỖI SỐ TRONG DÃY FIBONACCI ĐƯỢC TẠO BỞI VIỆC CỘNG 2 SỐ TRƯỚC VỚI NHAU.
HAI SỐ ĐẦU TRONG DÃY LÀ 1 VÀ 2. DÃY FIBONACCI NHƯ SAU:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
HÃY TỔNG CÁC SỐ CHẴN TRONG DÃY FIBONACCI MÀ SỐ CUỐI CÙNG TRONG DÃY KHÔNG ĐƯỢC
VƯỢT QUÁ 4 TRIỆU.

Đáp số: 4613732

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

limit = 4000000 
sum = 0 
a = 1 
b = 1 
while b < limit   
    if b mod 2 = 0 then 
        sum = sum + b   
    h = a + b   
    a = b   
    b = h 
output sum

Các bạn cứ theo giải thuật này viết. Code C sẽ như sau:

#include <stdio.h>

unsigned int target = 4000000;

int main(int argc, char *argv[])
{
	unsigned int limit = 4000000;
	unsigned int sum = 0;
	unsigned int a = 1;
	unsigned int b = 1;
	unsigned int h = 0;
	while(b < limit)
	{
		if(b % 2 == 0)
			sum += b;
		h = a + b;
		a = b;
		b = h;
	}
	printf("%d\n", sum);
	return 0;
}

Phân tích
Dãy fibonacci chúng ta sẽ viết lại như sau:
1    1    2    3    5    8   13   21   34   55   89   144
a    b    c    a    b    c    a    b    c     a     b     c

Những số chẵn trong dãy Fibonacci được tô màu đỏ. Giải thuật tốt hơn như sau (bởi vì vòng lặp while chạy nhanh hơn nhiều so với while cũ trên kia):

limit = 4000000 
sum = 0 
a = 1 
b = 1 
c = a + b 
while c < limit
   sum = sum + c
   a = b + c
   b = c + a
   c = a + b 
output sum

Chúng tôi sẽ dùng C để viết và dùng đệ quy và đoạn code sẽ chạy chậm hơn nhiều so với giải thuật trên!

/*
BÀI TẬP: MỖI SỐ TRONG DÃY FIBONACCI ĐƯỢC TẠO BỞI VIỆC CỘNG 2 SỐ TRƯỚC VỚI NHAU.
HAI SỐ ĐẦU TRONG DÃY LÀ 1 VÀ 2. DÃY FIBONACCI NHƯ SAU:
						1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
HÃY TỔNG CÁC SỐ CHẴN TRONG DÃY FIBONACCI MÀ SỐ CUỐI CÙNG TRONG DÃY KHÔNG ĐƯỢC
VƯỢT QUÁ 4 TRIỆU.
*/

/* Mục đích của đoạn code này là dùng đệ quy cho nên tốc độ sẽ chậm hơn */
#include <stdio.h>

unsigned int sumOfEven(int);
unsigned int target = 4000000;

int main(int argc, char *argv[])
{
	int i = 0;
	int result = 0;
	int temp = 0;

	for(i = 1;; i++)
	{
		temp = sumOfEven(i);
		if(temp > target) // điều kiện kết thúc vòng for
			break;
		if(temp % 2 == 0) // nếu số đó chia hết 2 thì cộng dồn kết quả!
			result += temp;
	}
	printf("%d\n", result);
	return 0;
}

// dùng đệ quy để tính số thứ n trong dãy fibonacci
unsigned int sumOfEven(int n) 
{
	if(n == 1)
		return 1;
	else if(n == 2)
		return 2;
	else
		return sumOfEven(n - 1) + sumOfEven(n - 2);
}

Bây giờ chúng ta sẽ cải thiện thuật toán nhưng vẫn dùng đệ quy!
Chúng ta sẽ tách những số chẵn ra khỏi dãy Fibonacci như sau:
2    8    34   144 …
Chúng ta dễ dàng tìm được công thức đệ quy:
E(n)=4*E(n-1)+E(n-2)
Đoạn code dùng đệ quy tốt hơn như sau:

#include <stdio.h>

unsigned int sumOfEven(int);
unsigned int target = 4000000;

int main(int argc, char *argv[])
{
	int i = 0;
	int result = 0;
	int temp = 0;

	for(i = 1;; i++)
	{
		temp = sumOfEven(i);
		if(temp > target) // điều kiện kết thúc vòng for
			break;
		result += temp;
	}
	printf("%d\n", result);
	return 0;
}

// dùng đệ quy để tính số thứ n trong dãy fibonacci
unsigned int sumOfEven(int n) 
{
	if(n == 1)
		return 2;
	else if(n == 2)
		return 8;
	else
		return 4*sumOfEven(n - 1) + sumOfEven(n - 2);
}

Nếu các bạn có giải thuật tốt hơn nữa thì hãy chia sẽ cho chúng tôi để cùng nhau bàn luận! 🙂

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