01/10/2018, 14:15
Không sử dụng đệ quy
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
Bài liên quan
Vậy nên mình nên biến đổi như thế nào ?
Cứ thế mà tính thôi.
O(n):
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).