[Algorithm] Thuật toán Đệ quy và một số bài toán Đệ quy cơ bản

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.

[Algorithm] Thuật toán Đệ quy và một số bài toán Đệ quy cơ bản

>> Giáo Trình C++ Và Lập Trình Hướng Đối Tượng

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;
}
}
}

Bài tập 13. Hoán vị mảng số nguyên có n phần tử
Phương pháp: tương tự phương pháp làm bài tập 13 nhưng ở đây ta thay tập hợp {0, 1, … , n-1} là tập hợp giá trị n phần tử của mảng và độ dài của dãy là n.
Ví dụ: n = 3 và A = {-1,0,1} ta sẽ có các dãy con tương ứng là {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1} và {1,0}.

[Cài đặt:]

#include <conio.h>
#include <iostream.h>
#define max 20
char DanhDau[max]; //mang danh dau dinh duoc chon
int Luu[max], A[max], n;
/*Khoi tao cac bien*/
void Init() {
cout<<"Nhap n = ";
cin>>n;
for(int i = 0; i<n; i++) {
/*Danh dau vi tri i chua chon*/
DanhDau[i] = 0;
cout<<"A["<<i<<"] = ";
cin>>A[i];
}
}
/*Xuat ket qua ra man hinh*/
void Out() {
cout<<endl;
for(int i = 0; i<n; i++)
cout<<Luu[i]<<" ";
}
/*Hoan vi mang n phan tu*/
void Try(int i) {
if(i==n)
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] = A[j]; //luu lai gia tri dinh duoc chon
Try(i+1); //tim dinh tiep theo
DanhDau[j] = 0; //phuc hoi dinh j
}
}
}
/*Chuong trinh chinh*/
void main() {
clrscr();
Init();
cout<<"Hoan vi cac phan tu trong mang A";
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] = A[j];
if(i==n-1)
Out();
else {
DanhDau[j] = 1;
Try(i+1);
DanhDau[j] = 0;
}
}
}

Bài tập 14. Đặt n quân hậu trên bàn cờ vua
Mô tả bài toán: liệt kê tất cả phương án đặt n quân hậu trên bàn cờ vua cấp nxn sao cho n quân hậu không được phép ăn nhau.
Ví dụ: cho bàn cờ vua cấp 8x8 . Dưới đây là 1 phương án đặt quân hậu:

[Cài đặt:]

#include <conio.h>
#include <iostream.h>
#define max 20
char a[max]; //danh dau cot
char b[2*max-1]; //danh dau huong Dong-Bac
char c[2*max-1]; //danh dau huong Tay-Bac
int Luu[max]; //luu ket qua tim duoc
int n;
/*Khoi tao cac bien*/
void Init() {
cout<<"Nhap n = ";
cin>>n;
//tat ca cac cot chua duoc chon
for(int i = 0; i<n; i++)
a[i] = 0;
//tat ca cac huong chua duoc chon
for( i = 0; i<2*n-1; i++) {
b[i] = 0;
c[i] = 0;
}
}
/*Xuat ket qua ra man hinh*/
void Out() {
cout<<endl;
for(int i = 0; i<n; i++)
cout<<"("<<i+1<<","<<Luu[i]+1<<") ";
}
/*Chinh hop khong lap chap k*/
void Try(int i) {
if(i==n)
Out();
else {
for(int j = 0; j<n; j++)
if(a[j] == 0 && b[i+j] == 0 && c[i-j+n] == 0) {
a[j] = 1; //danh dau cot j
b[i+j] = 1; //danh dau huong Dong-Bac thu i+j
c[i-j+n] = 1; //danh dau huong tay-Bac thu j-i+n
Luu[i] = j; //luu vi tri dat hau (i,j)
Try(i+1); //tim vi tri dat hau tiep theo
a[j] = 0; //phuc hoi cot j
b[i+j] = 0; //phuc hoi huong Dong-Bac thu i+j
c[i-j+n] = 0; //phuc hoi huong tay-Bac thu j-i+n
}
}
}
/*Chuong trinh chinh*/
void main() {
clrscr();
Init();
cout<<"Dat Hau";
Try(0);
getch();
}

Bài tập 15. Mã đi tuần
Mô tả bài toán: đặt quân mã tại ô có vị trí (x,y) trên bàn cờ vua cấp nx n. Hãy liệt kê tất cả các phương án quân mã xuất phát tại vị trí (x,y) có thể nhảy đến tất cả các ô khác trên bàn cờ với điều kiện mỗi ô quân mã chỉ được phép đi qua đúng 1 lần.
Ví dụ: cho bàn cờ vua cấp 8x8 . Ta có 2 phương án đặt quân mã như sau:

[Cài đặt:]

#include <iostream.h>
#include <conio.h>
#define max 10
int A[max][max]; //Mang danh dau
int B[max][max]; //Mang luu duong di
int X[8]={-1,-2,-2,-1,1,2,2,1};
int Y[8]={-2,-1,1,2,2,1,-1,-2};
int n, x, y, Dem=0;
//Khoi tao
void Init() {
cout<<"Nhap n = ";
cin>>n;
cout<<"Nhap x = ";
cin>>x;
cout<<"Nhap y = ";
cin>>y;
for(int i = 0; i<n; i++)
for(int j = 0; j<n; j++)
A[i][j] = 0; //tat ca cac o chua duoc danh dau
B[x][y] = 1; //duong di dau tien
A[x][y] = 1; //danh dau o duoc chon
}
//Xuat ket qua ra man hinh
void Out() {
Dem++;
for(int i = 0; i<n; i++) {
for(int j = 0; j<n; j++) {
printf("%3d",B[i][j]);
}
cout<<endl;
}
cout<<endl;
}
//Tim duong di
void Try(int i) {
if(i > n*n)
Out();
else {
for(int j = 0; j<8; j++) {
int x1 = x + X[j];
int y1 = y + Y[j];
if(x1>=0 && x1<n && y1>=0 && y1<n && A[x1][y1]==0){
A[x1][y1] = 1; //danh dau o (i,j)
B[x1][y1] = i; //luu lai duong di
x = x1; //lay toa do x moi
y = y1; //lay toa do y moi
Try(i+1); //tim duong di tiep theo
A[x1][y1] = 0; //phuc hoi o (i,j)
B[x1][y1] = 0; //xem nhu o chua di qua
x = x1 - X[j]; //phuc hoi dinh x
y = y1 - Y[j]; //phuc hoi dinh y
}
}
}
}
//chuong trinh chinh
void main() {
clrscr();
Init();
Try(2);
if (Dem==0)
cout<<"Khong co duong di";
else
cout<<"So phuong an tim duoc"<<Dem;
getch();
}