Đệ quy phi tuyến: Thân hàm đệ quy lặp gọi 1 số lần chính nó.
long U (int n){
More about →
long U (int n){
if (n<6) return n;
long S= 0;
for (int i = 5; i>0; i--)
long S= 0;
for (int i = 5; i>0; i--)
S+= U(n-i);
return S;
}
return S;
}
Bài toán 1: 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,...,an-1 được định nghĩa đệ quy như sau:
Mã nguồn:
#include<conio.h>
#include<iostream>
using namespace std;
long int S(int a[], int n) {
if(n==1)
return a[0];
else
return a[n-1]+S(a,n-1);
}
int main(){
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();
return 0;
}
Bài toán 2: Tính tích n phần tử trong danh sách
Viết chương trình tính tổng n phần tử a0,...,an-1 được định nghĩa đệ quy như sau:
Mã nguồn:
#include<conio.h>
#include<iostream>
using namespace std;
long int S(int a[], int n) {
if(n==1)
return a[0];
else
return a[n-1]*S(a,n-1);
}
int main(){
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<<"Tich "<<n<<" phan tu trong mang A la "<<S(a,n);
getch();
return 0;
}
Bài toán 3: Đếm số lần xuất hiện của phần tử x trong danh sách
Viết chương trình đếm số lần xuất hiện của số nguyên x trong danh sách A={a0,...,an-1} với n phần tử. Thuật toán đệ quy được thể hiện như sau:
Mã nguồn:
#include<conio.h>
#include<iostream>
using namespace std;
/*Ham tra ve so lan xuat hien cua x trong danh sachA*/
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);
}
int main(){
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();
return 0;
}
Tag: C, C++, Đệ quy tuyến tính, Đệ quy, Khử đệ quy, recursive, đệ quy nhị phân, đệ quy hỗ tương, Đệ quy phi tuyến
Tag: C, C++, Đệ quy tuyến tính, Đệ quy, Khử đệ quy, recursive, đệ quy nhị phân, đệ quy hỗ tương, Đệ quy phi tuyến
