Viết hàm tính f(n) theo công thức: f(1)=1; f(2n)=2f(n); f(2n+1)=2f(n)+ 3f(n+1)

Kỹ thuật lập trình - Đệ quy

Đề bài: Với n>=1; n là số nguyên dương, biết rằng f(n) được tính theo công thức đệ quy sau đây:

• F(1)=1;

• F(2n)=2F(n)

• F(2n+1)=2F(n)+3F(n+1);

Viết hàm tính F(n) bằng 2 cách đệ quy và khử đệ quy.

Các bạn có thể tham khảo đoạn code sau:

#include<iostream> using namespace std; int dequy(int n) { if(n==1)return n; if(n%2==0)return 2*dequy(n/2); else return 2*dequy((n-1)/2)+3*dequy((n+1)/2); } int khudequy(int n) { int a[1000]; a[1]=1; for(int i=1;i<=n/2;i++) { a[i*2]=2*a[i]; a[i*2+1]=2*a[i]+3*a[i+1]; } return a[n]; } int main() { cout<<"de quy: "<<dequy(5)<<endl; cout<<"khu de quy: "<<khudequy(5)<<endl; }

Kết quả khi thực hiện chương trình: bộ test n=5

Được viết bởi Đinh Quang Trưởng

Đệ Quy ky thuat lap trinh 4:15 PM