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

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
Xem chi tiết

Code C++: Đệ quy Hỗ tương

Code C++: Đệ quy Hỗ tương
Đệ quy hỗ tương: Với dạng đệ quy hỗ tương, việc gọi hàm không đơn thuần là tự gọi nó mà còn có gọi đến hàm khác, và hàm kia có khả năng gọi lại hàm ban đầu. Cứ như vậy tạo vòng lặp xen kẽ nhau, và tất nhiên dù là lặp dạng nào thì cũng cần có điểm dừng. Ở đây cần tạo điểm dừng trên cả 2 hàm, nếu 1 trong 2 hàm không có điểm dừng thì đệ quy sẽ vô tận.


Bài toán 1Viết chương trình tính Un và Gn được xác định như sau:

Mã nguồn:
long G(int n); 


long U ( int n){ 
      if (n<5) return n;
      return U(n-1) + G(n-2);
}

long G(int n){ 
      if (n<8) return n-3;
      return U(n-1) + G(n-2);
}
Bài toán 2: Viết chương trình tính Xn và Yn được xác định như sau:

Mã nguồn:

#include<conio.h>
#include<iostream>
using namespace std;
long int X(int n);
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);
}
int main(){
int n;
cout<<"n = ";
cin>>n;
cout<<"X("<<n<<") = "<<X(n);
cout<<"\nY("<<n<<") = "<<Y(n);
getch();
}
Tag: C, C++, Đệ quy tuyến tính, Đệ quy, Khử đệ quy, recursive, đệ quy nhị phân, đệ quy hỗ tương
Xem chi tiết

Code C++: Đệ quy Nhị phân

Code C++: Đệ quy Nhị phân

Đệ quy nhị phân: Thân hàm gọi 2 lần chính nó.
Ví dụ: Chuỗi số Fibonacci: 1 1 2 3 5 8 13 ... 

long Fibonacci(int n){
      if (n<=2) return 1;
      return Fibonacci(n-2) + Fibonacci(n-1);
}

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

Mã nguồn:


#include<math.h>

#include<iostream>
#include<conio.h>
using namespace std;
int Fibonacci(int N){
if(N==0 || N==1)
return 1;
else
return Fibonacci(N-2) + Fibonacci(N-1);
}

int main(){
int n;
cout<<"Nhap vao gia tri cua n = ";
cin>>n;
cout<<"Fibonacci("<<n<<") = "<<Fibonacci(n);
getch();
return 0;
}
Tag: C, C++, Đệ quy tuyến tính, Đệ quy, Khử đệ quy, recursive, đệ quy nhị phân
Xem chi tiết

Code C++: Đệ quy Tuyến tính

Code C++: Đệ quy Tuyến tính
Đệ quy tuyến tính: Thân hàm gọi 1 lần chính nó


Ví dụ:

double U(int n, double a, double r){
      if (n==1) return a;
      return r + U(n-1,a,r);    //Gọi 1 lần chính tên hàm đang định nghĩa
}

Bài toán 1: Tính X lũy thừa n

Viết chương trình tính X^n với X là số thực được xác định như sau:


Mã nguồn:

#include<conio.h>
#include<iostream>
using namespace std;
/* Hàm đệ quy trả về số thực tính giá trị X^n*/
float Mu(float X, int n){
if(n==0)
return 1;
else
return X*Mu(X,n-1);  // Gọi đệ quy hàm Mu
}
/* Chương trình chính */
int main(){
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<<" = "<<Mu(X,n);
getch();
return 0;
}

Bài toán 2: 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:


Mã nguồn:

#include<conio.h>
#include<iostream>
using namespace std;
/* Hàm đệ quy trả về ước chung lớn nhất của 2 số a,b */
int UCLN(int a, int b) {
if(a==b)
return a;
else if(a>b)
return UCLN(a-b,b);  //Gọi hàm đệ quy UCLN
else
return UCLN(a,b-a);  //Gọi hàm đệ quy UCLN
}
/* Chương trình chính */
int main(){
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();
return 0;
}

Bài toán 3: Tính n giai thừa
Viết chương trình tính n! được định nghĩa đệ quy như sau:
Mã nguồn:
#include<conio.h>
#include<iostream>
using namespace std;
/* Hàm đệ quy trả về giai thừa của n */
int GiaiThua(int n){
if(n==0)
return 1;
else
return n*GiaiThua(n-1);
}
/* Chương trình chính */
int main(){
int n;
cout<<"Nhap n = "; cin>>n;
cout<<n<<"!= "<<GiaiThua(n);
getch();
return 0;
}
Tag: C, C++, Đệ quy tuyến tính, Đệ quy, Khử đệ quy, recursive
Xem chi tiết

Code C++: Chương trình Đệ quy tìm phần tử Fibonacci thứ N

Code C++: Chương trình Đệ quy tìm phần tử Fibonacci thứ N
Chương trình tìm phần tử Fibonacci thứ n được định nghĩa đệ quy như sau:
#include<math.h>
#include<iostream>
#include<conio.h>
using namespace std;
/* 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 */
int main(){
int n;
cout<<"Nhap vao gia tri cua n = ";
cin>>n;
cout<<"F("<<n<<") = "<<F(n);
getch();
return 0;
}
Tag: Fibonacci, fibonaxi, Đệ quy, C, C++
Xem chi tiết

Code C++: Hàm tính tổng các phần tử trên cùng 1 dòng, 1 cột của Ma trận

Code C++: Hàm tính tổng các phần tử trên cùng 1 dòng, 1 cột của Ma trận
1. Hàm tính tổng các phần tử trên cùng một dòng của ma trận.
void tongdong(int a[][100],int n,int m){
          for(int i=0;i<n;++i){
                   int S=0;
                   for(int j=0;j<m;++j)
                             S+=a[i][j];
                   cout<<"dong "<<i<<" la: "<<S<<endl;
          }
}

2. Hàm tính tổng các phần tử trên cùng một cột của ma trận
void tongcot(int a[][100],int n,int m){
  for(int i=0;i<m;i++){
                    int s=0;
                   for(int j=0;j<n;j++)
                              s=s+a[j][i];
                   cout<<"cot "<<i<<" la: "<<s<<endl;
           }

}
Tag: C, C++, ma trận, mảng 2 chiều, mảng hai chiều, tổng ma trận
Xem chi tiết

Code C++: Các câu lệnh duyệt mảng 2 chiều thường gặp

Code C++: Các câu lệnh duyệt mảng 2 chiều thường gặp

Các câu lệnh duyệt mảng 2 chiều thường gặp:
*Ghi chú: n là số dòng, m là số cột
-Nhập mảng
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
                   cout<<"nhap vao phan tu thu "<<i<<j<<": ";
cin>>a[i][j];
                   }
-Xuất mảng
for(int i=0;i<n;i++)
{       
for(int j=0;j<m;j++)
cout<<a[i][j]<<" ";
                   cout<<endl;
          }
*Một số câu lệnh chỉ có trong ma trận vuông: (số dòng bằng số cột n=m):
-Xuất các phần tử nằm trên đường chéo chính
          for(int i=0;i<n;i++)
cout<<a[i][i];

-Xuất các phần tử nằm phía trên đường chéo chính(còn gọi là tam giác trên)
for(int i=0;i<n;i++)                                    for(int i=0;i<n;i++)
     for(int j=0;j<i;j++)            OR                       for(int j=i+1;j<n;j++)
cout<<a[j][i]<<" ";                                    cout<<a[i][j]<<" ";                         
  
-Xuất các phần tử nằm phía dưới đường chéo chính (còn gọi là tam giác dưới)
for(int i=0;i<n;i++)
      for(int j=0;j<i;j++)
          cout<<a[i][j]<<" ";

-Xuất các phần tử nằm trên đường chéo phụ
for(int i=0;i<n;i++)
cout<<a[i][n-1-i)<<” “;

-Xuất các phần tử nằm phía trên đường chéo phụ
for(int i=0;i<n;i++)                                    for(int i=0;i<n;i++)
    for(int j=0;j<n-1-i;j++)                OR          for(int j=n-i;j<n;j++)       
        cout<<a[i][j]<<" ";                                         cout<<a[n-1-j][n-1-i]<<" ";      
                                     
-Xuất các phần tử nằm phía dưới đường chéo phụ
for(int i=0;i<n;i++)
              for(int j=n-i;j<n;j++)
                    cout<<a[i][j]<<" ";

Tag: Mảng 2 chiều, mảng hai chiều, mã nguồn, C, C++

Xem chi tiết