Thuật toán đệ quy trong PHP

Hàm đệ quy

Hàm đệ quy là những hàm gọi lại chính nó. Nó hữu dụng  trong các tác vụ như sắp xếp hoặc tính toán các số giai thừa… Hàm đệ quy tương ứng với khái niệm quy nạp trong toán học. 

Bài tập 1. Tìm phần tử Fibonacci thứ n (bài toán Fibonacci)
Viết chương trình tìm phần tử Fibonacci thứ n được định nghĩa đệ quy như sau:

[Cài đặt:]

#include <conio.h>
#include <iostream.h>
/*Ham tra ve so nguyen tinh gia tri Fibonacci thu n*/
int F(int n) {
   if(n==0 || n==1)
   return 1;
  else
return F(n-1) + F(n-2);
} 

/*Chuong trinh chinh*/
void main() {
 clrscr();
 int n;
 cout<<"Nhap vao gia tri cua n = ";
 cin>>n;
 cout<<"F("<<n<<") = "<<F(n);
 getch();
}
Bài tập 2. Tính X lũy thừa n
Viết chương trình tính X mũ n với X là số thực, n là số nguyên:
Cài đặt:
#include <conio.h>
#include <iostream.h>
/*Ham tra ve so thuc tinh gia tri X^n*/
float Power(float X, int n) {
if(n==0)
return 1;
else
return X*Power(X,n-1);
}
/*Chuong trinh chinh*/
void main() {
clrscr();
int n;
float X;
cout<<"Nhap vao gia tri cua n = ";
cin>>n;
cout<<"Nhap vao gia tri cua X = ";
cin>>X;
cout<<X<<"^"<<n<<" = "<<Power(X,n);
getch();
}

Bài tập 3. Thuật toán Euclide tìm ước chung lớn nhất
Viết chương trình tìm ước chung lớn nhất của 2 số nguyên dương a, b bằng thuật toán. Euclide được định nghĩa đệ quy như sau:

[Cài đặt:]

#include <conio.h>
#include <iostream.h>
int UCLN(int a, int b) {
if(a==b)
return a;
else if(a>b)
return UCLN(a-b,b);
else
return UCLN(a,b-a);
}
void main() {
clrscr();
int a,b;
cout<<"Nhap a = ";
cin>>a;
cout<<"Nhap b = ";
cin>>b;
cout<<"Uoc chung lon nhat cua "<<a<<" va "<<b<<" la "<<UCLN(a,b);
getch();
}

Bài tập 4. Tìm ước chung lớn nhất của n số nguyên
Viết chương trình tìm ước chung lớn nhất của n số nguyên dương 0 1 ,..., n a a được định nghĩa đệ quy như sau:

[Cài đặt:]

#include <conio.h>
#include <iostream.h>
/*Ham tra ve uoc chung lon nhat cua a va b*/
int UCLN(int a, int b) {
if(a==b)
return a;
else if(a>b)
return UCLN(a-b,b);
else
return UCLN(a,b-a);
}
/*Ham tra ve uoc chung lon nhat cua n phan tu duoc luu tru trong mang 1 chieu a*/
int UC(int a[], int n) {
if(n==1)
return a[0];
else
return UCLN(a[n-1],UC(a,n-1));
}
void main() {
clrscr();
int *a,n;
cout<<"Nhap n = ";
cin>>n;
a = new int[n];
cout<<"Nhap vao "<<n<<" phan tu\n";
for(int i=0; i<n ; i++){
cout<<"a["<<i<<"] = ";
cin>>a[i];
}
cout<<"UCLN cua "<<n<<" phan tu vua nhap la "<<UC(a,n);
getch();
}

Bài tập 5. Tính n giai thừa
Viết chương trình tính n! được định nghĩa đệ quy như sau:

[Cài đặt:]

#include <conio.h>
#include <iostream.h>
/*Ham tra ve so nguyen tinh n! (Factorial)*/
long int Fac(int n) {
if(n==0)
return 1;
else
return n*Fac(n-1);
}
/*Chuong trinh chinh*/
void main() {
clrscr();
int n;
cout<<"Nhap vao gia tri cua n = ";
cin>>n;
cout<<n<<"! = "<<Fac(n);
getch();
}

Bài tập 6. Tổ hợp chập k của n phần tử
Viết chương trình tính tổ hợp chập k của n  được xác định như sau:

[Cài đặt:]

#include <conio.h>
#include <iostream.h>
/*C(n,k)=C(n-1,k-1)+c(n-1,k) dk: 0<k<n; c(n,0)=c(n,n)=1*/
long int C(int n, int k) {
if (n==k||k==0)
return 1;
else
return C(n-1,k-1)+C(n-1,k);
}
/*Chuong trinh chinh*/
void main() {
clrscr();
int n,k;
cout<<"n = ";
cin>>n;
cout<<"k = ";
cin>>k;
cout<<"C("<<n<<","<<k<<") = "<<C(n,k);
getch();
}

Bài tập 7. Tính tổng n phần tử trong danh sách
Viết chương trình tính tổng n phần tử a0, a1 ,..., an.   được định nghĩa đệ quy như sau:

[Cài đặt:]

#include <conio.h>
#include <iostream.h>
/*Ham tra ve so nguyen tinh tong n phan tu trong mang a*/
long int S(int a[], int n) {
if(n==1)
return a[0];
else
return a[n-1]+S(a,n-1);
}
/*Chuong trinh chinh*/
void main() {
clrscr();
int *a,n;
cout<<"n = ";
cin>>n;
a = new int[n];
cout<<"Nhap vao "<<n<<" phan tu\n";
for(int i=0; i<n ; i++){
cout<<"a["<<i<<"] = ";
cin>>a[i];
}
cout<<"Tong "<<n<<" phan tu trong mang a la "<<S(a,n);
getch();
}

Bài tập 8. Đệ quy hỗ tương
Viết chương trình tính n X và n Y được xác định như sau:

[ Cài đặt:]

#include <conio.h>
#include <iostream.h>
long int Y(int n);
long int X(int n) {
if(n==0)
return 1;
else
return X(n-1) + Y(n-1);
}
long int Y(int n) {
if(n==0)
return 1;
else
return 2*X(n-1)*Y(n-1);
}
/*Chuong trinh chinh*/
void main() {
clrscr();
int n;
cout<<"n = ";
cin>>n;
cout<<"X("<<n<<") = "<<X(n);
cout<<"Y("<<n<<") = "<<Y(n);
getch();
}

Bài tập 9. Tích n phần tử trong danh sách
Viết chương trình tính tích n phần tử 0 1 ,..., n a a được định nghĩa đệ quy như sau:

[Cài đặt:]

#include <conio.h>
#include <iostream.h>
/*Ham tra ve so nguyen tinh tich n phan tu trong mang a*/
long int S(int a[], int n) {
if(n==1)
return a[0];
else
return a[n-1]*S(a,n-1);
}
/*Chuong trinh chinh*/
void main() {
clrscr();
int *a,n;
cout<<"n = ";
cin>>n;
a = new int[n];
cout<<"Nhap vao "<<n<<" phan tu\n";
for(int i=0; i<n ; i++){
cout<<"a["<<i<<"] = ";
cin>>a[i];
}
cout<<"Tong "<<n<<" phan tu trong mang A la "<<S(a,n);
getch();
}

Bài tập 10. Đếm số lần xuất hiện của phần tử x trong danh sách

[Cài đặt:]

#include <conio.h>
#include <iostream.h>
/*Ham tra ve so lan xuat hien cua x trong danh sach A*/
int Find(int a[], int n, int x) {
if(n==0)
return 0;
else
if(a[n-1]==x)
return 1+Find(a,n-1,x);
else
return Find(a,n-1,x);
}
/*Chuong trinh chinh*/
void main() {
clrscr();
int *a,n,x;
cout<<"n = ";
cin>>n;
a = new int[n];
cout<<"Nhap vao danh sach "<<n<<" phan tu\n";
for(int i=0; i<n ; i++){
cout<<"a["<<i<<"] = ";
cin>>a[i];
}
cout<<"x = ";
cin>>x;
cout<<"So lan xuat hien cua "<<x<<"trong danh sach la "<<Find(a,n,x);
getch();
}

Bài tập 11. Liệt kê tất cả dãy nhị phân độ dài k
Chỉnh hợp lặp chập k của n phần tử là một nhóm có thứ tự gồm k phần tử lấy từ n phần tử đã cho, trong đó mỗi phần tử có thể có mặt 1, 2, …, k lần trong nhóm tạo thành.
Phương pháp: ta liệt kê tất cả chỉnh hợp có lặp chập k của hai phần tử 0 và 1. Khi đó ta sẽ có tất cả dãy nhị phân có độ dài k.
Ví dụ: minh họa dạng cây với k = 3.

[Cài đặt:]

#include <conio.h>
#include <iostream.h>
#define max 20
int Luu[max];
int k;
/*Xuat ket qua ra man hinh*/
void Out() {
cout<<endl;
for(int i = 0; i<k; i++)
cout<<Luu[i];
}
/*Day nhi phan do dai n*/
void Try(int i) {
if(i==k)
Out();
else {
for(int j = 0; j<=1; j++) {
Luu[i] = j;
Try(i+1);
Luu[i]=0;
}
}
}
/*Chuong trinh chinh*/
void main() {
clrscr();
cout<<"Nhap n = ";
cin>>k;
cout<<"Day nhi phan do dai k.\n";
Try(0);
getch();
}
//Hàm Try(int i) có thể viết lại theo cách như sau:
void Try(int i) {
for(int j = 0; j<=1; j++) {
Luu[i] = j;
if(i==k-1)
Out();
else
Try(i+1);
}
}

Bài tập 12. Chỉnh hợp không lặp chập k của n phần tử
Chỉnh hợp chập k của n phần tử  là một nhóm có thứ tự gồm k phần tử khác nhau được chọn từ n phần tử đã cho.
Phương pháp: liệt kê dãy có độ dài k và các phần tử trong dãy được lấy từ tập hợp {0,1, … , n-1} các phần tử được đưa vào dãy không được phép trùng nhau.
Ví dụ: n = 3 và k = 2 ta sẽ có các dãy con {0,1}, {0,2}, {1,0}, {1,2}, {2,0} và {2,1}.

[Cài đặt:]

#include <conio.h>
#include <iostream.h>
#define max 20
char DanhDau[max];
int Luu[max];
int n,k;
/*Khoi tao cac bien*/
void Init() {
cout<<"Nhap n = ";
cin>>n;
cout<<"Nhap k = ";
cin>>k;
//khoi tao tat ca cac dinh chua duoc chon
for(int i = 0; i<k; i++)
DanhDau[i] = 0;
}
/*Xuat ket qua ra man hinh*/
void Out() {
cout<<endl;
for(int i = 0; i<k; i++)
cout<<Luu[i]<<" ";
}
/*Chinh hop khong lap chap k*/
void Try(int i) {
if(i==k)
Out();
else {
for(int j = 0; j<n; j++)
if(DanhDau[j] == 0) { //neu dinh j chua duoc chon
DanhDau[j] = 1; //chon dinh j
Luu[i] = j; //luu lai gia tri j
Try(i+1); //tim phan tu tiep theo
DanhDau[j] = 0; //phuc hoi dinh j
}
}
}
/*Chuong trinh chinh*/
void main() {
clrscr();
cout<<"Chinh hop khong lap n chap k";
Init();
Try(0);
getch();
}
//Hàm Try(int i) có thể viết lại theo cách như sau:
void Try(int i) {
for(int j = 0; j<n; j++)
if(DanhDau[j]==0) {
Luu[i] = j;
if(i==n-1)
Out();
else {
DanhDau[j] = 1;
Try(i+1);
DanhDau[j] = 0;
}
}
}