Tính X(n) theo công thức: x(1)=1; x(2)=1; x(n)=x(n-1)+(n-1)x(n-2)

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

Đề bài: Với mỗi số nguyên n>=1, số X(n) được tính như sau:

• X(1)=1

• X(2)=2

• X(n)=X(n-1)+(n-1)X(n-2) với x>=3

Viết hàm tính X(n) bằng hai cách đệ quy và không đệ quy.

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

#include<iostream> using namespace std; int dequyc(int n) { if(n==1||n==2)return 1; return dequyc(n-1)+dequyc(n-2)*(n-1); } int khudequyc(int n) { int a[1000]; a[1]=1;a[2]=1; for(int i=3;i<=n;i++) { a[i]=a[i-1]+(i-1)*a[i-2]; } return a[n]; } int khudequyc1(int n) { int x=n,x1=1,x2=1; for(int i=3;i<=n;i++) { x=x2+(i-1)*x1; x1=x2;x2=x; } return x; } int main() { cout<<"de quy: "<<dequyc(11)<<endl; cout<<"khu de quy 1: "<<khudequyc(11)<<endl; cout<<"khu de quy 2: "<<khudequyc1(11)<<endl; }

* Phần khử đệ quy mình đã viết 2 cách:

• Gọi lại hàm
• Dùng mảng 1 chiều

Kết quả khi chạy chương trình với bộ test n=11

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

Đệ Quy ky thuat lap trinh 4:42 PM