Code C++: Đệ quy phi tuyến

Đệ quy phi tuyến: Thân hàm đệ quy lặp gọi 1 số lần chính nó.

long U (int n){ 
    if (n<6) return n;
    long S= 0;
    for (int i = 5; i>0; i--) 
          S+= U(n-i);
    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

Related Posts
Previous
« Prev Post