Không sử dụng đệ quy

mvhix9 · January 22, 2018, 2:51pm

Tính f(n) theo công thức :
f(1)=1
f(2n)=2f(n),
f(2n+1)=2f(n)+3f(n+1)

Mình có đoạn code như sau mà ra kết quả (đối chiếu với sử dụng đệ quy) thì lại khác, không biết có bị sai chỗ nào không

int khongdequy_tinhfn(int n)
{
	int f1=1,f;
	if (n==1) return 1;
	for (int i=2;i<=n;i++)
	{
		if (i%2==0)
		{
			f=2*f1;
			f1=f;
		}
		if (i%2!=0)
		{
			f=2*f1+3*(f1+1);
			f1=f;
		}
	}	
	return f;
}

Xin cảm ơn

mvhix9 · January 22, 2018, 3:12pm

Vậy nên mình nên biến đổi như thế nào ?

noname00 · January 22, 2018, 4:29pm

Cứ thế mà tính thôi.

O(n):

f[1] = 1
for n:
    if (n % 2 == 0) f[n] = 2*f[n/2] else f[n] = 2*f[n/2] + 3*f[n-n/2]

kiencon · January 23, 2018, 2:20am

theo mình nghĩ thì mọi bài toán đệ quy đều khử được bằng stack, trong bài toán này để khử đệ quy mình sẽ dùng 2 vòng lặp, O(2logN), cấp phát 1 mảng n + 1 số mặc định bằng 0, với a[1] = 1; duyệt từ n về 1, để tính các giá trị của f(2n) và f(2n+1) theo f(n) và f(n+1) và lưu công thức theo 1 chuẩn nào đó vào stack. Cho đến khi n = 1, dùng vòng lặp thứ 2 cho đến khi stack rỗng, tính các giá trị theo công thức đã đc lưu trong stack ta sẽ tính đc f(n).