Tính Y(n) theo công thức: y(1)=1;y(2)=2; y(3)=3; y(n)=y(n-1)+2y(n-2)+3y(n-3)

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

Đề bài: Với mỗi n>=1, số Y(n) được tính như sau:
y(1)=1; y(2)=2; y(3)=3;
y(n)=y(n-1)+2y(n-2)+3y(n-3) nếu n>=4;
Viết hàm tính Y(n) bằng 2 cách khử đệ quy và đệ quy

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

#include<iostream> using namespace std; int dequyb(int n) { if(n<4)return n; return dequyb(n-1)+dequyb(n-2)*2+dequyb(n-3)*3; } int khudequyb(int n) { int a[100000]; a[1]=1;a[2]=2;a[3]=3; for(int i=4;i<=n;i++) { a[i]=a[i-1]+a[i-2]*2+a[i-3]*3; } return a[n]; } int khudequyb1(int n) { int x=n,x1=1,x2=2,x3=3; for(int i=4;i<=n;i++) { x=x3+2*x2+3*x1; x1=x2; x2=x3; x3=x; }return x; } int main() { cout<<"de quy: "<<dequyb(12)<<endl; cout<<"khu de quy 1: "<<khudequyb(12)<<endl; cout<<"khu de quy 2: "<<khudequyb1(12)<<endl; }

*Mình có đưa ra 2 cách khử đệ quy cho bài toán:

• Gọi hàm chính nó
• Dùng mảng 1 chiều

Kết  quả của chương trình khi bộ test n=5

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

Đệ Quy ky thuat lap trinh 4:31 PM