Thuật Toán Đệ Quy Và Một Số Bài Toán Đệ Quy Cơ Bản - VN SEEDER

VN SEEDER

Chắc chắn là có đủ....

Menu

• Tin học - Lập trình
  • Lập trình căn bản
  • Lập trình đồ họa
  • Cấu trúc dữ liệu & giải thuật
  • C# và SQL Server
  • Thủ thuật máy tính
• Kiến thức
  • Có thể bạn chưa biết
  • Làm thế nào
  • Nuôi dạy con
  • Sức khỏe
• Đọc
  • Hạt giống tâm hồn
  • Truyện cổ tích
  • Truyện cười
  • Truyện ngụ ngôn
  • Tony buổi sáng
  • Phật học
• Ebook
  • English Ebook
  • Vietnamese Ebook

Trang chủ >> Cấu trúc dữ liệu và giải thuật >> Thuật toán >> Thuật toán Đệ quy và một số bài toán Đệ quy cơ bản Thuật toán Đệ quy và một số bài toán Đệ quy cơ bản Từ khóa Cấu trúc dữ liệu và giải thuật Thuật toán

Hàm đệ quyHà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:

#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; elsereturn 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 nViế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;elsereturn 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ấtViế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);elsereturn 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ênViế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);elsereturn 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];elsereturn 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ừaViế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;elsereturn 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;elsereturn 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áchViế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];elsereturn 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ươngViế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;elsereturn X(n-1) + Y(n-1);}long int Y(int n) {if(n==0)return 1;elsereturn 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áchViế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];elsereturn 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;elseif(a[n-1]==x)return 1+Find(a,n-1,x);elsereturn 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 kChỉ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 20int 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();elseTry(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 20char 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 chonfor(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 chonDanhDau[j] = 1; //chon dinh jLuu[i] = j; //luu lai gia tri jTry(i+1); //tim phan tu tiep theoDanhDau[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 20char DanhDau[max]; //mang danh dau dinh duoc chonint 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 chonDanhDau[j] = 1; //chon dinh jLuu[i] = A[j]; //luu lai gia tri dinh duoc chonTry(i+1); //tim dinh tiep theoDanhDau[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ờ vuaMô 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 20char a[max]; //danh dau cotchar b[2*max-1]; //danh dau huong Dong-Bacchar c[2*max-1]; //danh dau huong Tay-Bacint Luu[max]; //luu ket qua tim duocint n;/*Khoi tao cac bien*/void Init() {cout<<"Nhap n = ";cin>>n;//tat ca cac cot chua duoc chonfor(int i = 0; i<n; i++)a[i] = 0;//tat ca cac huong chua duoc chonfor( 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 jb[i+j] = 1; //danh dau huong Dong-Bac thu i+jc[i-j+n] = 1; //danh dau huong tay-Bac thu j-i+nLuu[i] = j; //luu vi tri dat hau (i,j)Try(i+1); //tim vi tri dat hau tiep theoa[j] = 0; //phuc hoi cot jb[i+j] = 0; //phuc hoi huong Dong-Bac thu i+jc[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ầnMô 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 10int A[max][max]; //Mang danh dauint B[max][max]; //Mang luu duong diint 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 taovoid 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 dauB[x][y] = 1; //duong di dau tienA[x][y] = 1; //danh dau o duoc chon}//Xuat ket qua ra man hinhvoid 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 divoid 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 dix = x1; //lay toa do x moiy = y1; //lay toa do y moiTry(i+1); //tim duong di tiep theoA[x1][y1] = 0; //phuc hoi o (i,j)B[x1][y1] = 0; //xem nhu o chua di quax = x1 - X[j]; //phuc hoi dinh xy = y1 - Y[j]; //phuc hoi dinh y}}}}//chuong trinh chinhvoid main() {clrscr();Init();Try(2);if (Dem==0)cout<<"Khong co duong di";elsecout<<"So phuong an tim duoc"<<Dem;getch();}

Bài liên quan

Bài liên quan

>

Thể loại

Cổ tích Có thể bạn chưa biết Nuôi - Dạy con TonyBuổi Sáng-TnBS Sức khỏe Máy tính Lập trình căn bản Làm thế nào Ngẫm Cấu trúc dữ liệu và giải thuật Hạt giống tâm hồn C# và SQL Server Phật học Truyện ngụ ngôn Giáo dục

Ebook Tiếng Anh

CSharp Facebook SEO Windows

Bài xem nhiều

• Lập trình căn bản C: Tìm ước chung lớn nhất, bội chung nhỏ nhất của 2 số a, b
• Lập trình căn bản C: Rút gọn phân số
• Lập trình căn bản C: Xét trúng tuyển thi đại học
• Những lần xê dịch
• Lập trình căn bản C: In ra n số nguyên tố đầu tiên
• Chuyện tiền chuyện bạc (phần 2)
• Lập trình căn bản C: in tam giác số đối đỉnh
• Lập trình căn bản C: tìm số m lớn nhất sao cho tổng từ một đến m nhỏ hơn bằng n
• Làm Menu lựa chọn bằng mũi tên di chuyển lên xuống C/C++
• Đảo ngược số nguyên dương bằng cách sử dụng đệ quy (có trả về kết quả)

top