Code C/C++: Thuật toán phân rã ma trận A = LU

Quá trình chuyển hoá ma trận  A ban đầu thành tích hai ma trận tam giác L.U dựa vào phép khử Gauss được thực hiện bằng các phép nhân ma trận. Thuật toán này được gọi là thuật toán Crout. Quá trình Crout bao gồm nhiều bước hồi quy. Nếu ma trận  A có cấp  n x n, ta cần n-1 bước. Thuật toán được thể hiện cụ thể như sau:

Thông qua  n-1 bước hồi quy ta được  A=L.U. Với L là ma trận tam giác dưới và U là ma trận tam giác trên.
Cài đặt chương trình:
#include <conio.h>
#include <iostream>
#define max 100
using namespace std;
void Nhap(float A[max][max],int n) {
for(int i = 0; i<n; i++)
for(int j = 0; j<n; j++) {
cout<<"a["<<i<<"]["<<j<<"] = ";
cin>>A[i][j]; 
}
}
void XuatMaTran(float A[max][max], int n) {
cout<<"\n";
for(int i=0 ; i<n; i++){
cout<<endl;
for(int j=0 ; j<n; j++)
cout<<A[i][j]<<"\t";
}
}
/* Phan ra A = LU */
void PhanRaLU(float A[max][max], float L[max][max], float U[max][max], int n) {
for(int k =0; k<n; k++) {
U[k][k] = A[k][k];
L[k][k] = 1;
for(int i=k+1; i<n; i++) {
L[i][k] = A[i][k]/U[k][k];
U[k][i] = A[k][i];
U[i][k] = 0;
L[k][i] = 0;
}
for(int i = k+1; i<n; i++)
for(int j = k+1; j<n; j++)
A[i][j] = A[i][j]-L[i][k]*U[k][j];
}
}
int main(){
int n;
float A[max][max],L[max][max],U[max][max];
cout<<"Nhap n = ";  cin>>n;
cout<<"Nhap ma tran A\n";
Nhap(A,n);
cout<<"Ma tran A vua nhap";
XuatMaTran(A,n);
PhanRaLU(A,L,U,n);
cout<<"\nMa tran L";
XuatMaTran(L,n);
cout<<"\nMa tran U";
XuatMaTran(U,n);
getch();
return 0;
} 
Kết quả chạy chương trình:

Tag: C, C++, ma trận, A=LU, A=L*U, phân rã ma trận

More about →

Code C/C++: Giải hệ phương trình tuyến tính dạng tam giác dưới

Cho hệ phương trình tuyến tính dạng tam giác dưới:

Nghiệm của hệ trên được xác định như sau:

Cài đặt chương trình:
#include <conio.h>
#include <iostream>
#define max 100
using namespace std;
/* Nhập ma trận tam giác dưới */
void Nhap(float A[max][max],int n) {
for(int i = 0; i<n; i++) 
for(int j = 0; j<=i; j++) {
cout<<"a["<<i<<"]["<<j<<"] = ";
cin>>A[i][j];
}
}
/* Nhập ma trận hệ số tự do */
void Nhap(float B[max],int n) {
for(int i = 0; i<n; i++) {
cout<<"b["<<i<<"] = ";
cin>>B[i];
}
}
/* Xuất ma trận hệ số tự do */
void Xuat(float B[max],int n) {
cout<<"(";
for(int i = 0; i<n-1; i++)
cout<<B[i]<<",";
cout<<B[n-1]<<")";
}
/* Xuất ma trận */
void Xuat(float A[max][max], int n) {
cout<<"\n";
for(int i=0 ; i<n; i++){
cout<<endl;
for(int j=0 ; j<n; j++)
if(i<j)
cout<<"0\t";
else
cout<<A[i][j]<<"\t";
}
}
/* Xuất nghiệm */
void XuatNghiem(float X[], int n, char * s){
cout<<"\nNghiem cua he A.X = B\n";
for(int i=0; i<n; i++)
cout<<s<<i+1<<" = "<<X[i]<<endl;
}
/* Hệ tam giác dưới */
char HeTamGiacDuoi (float A[max][max], float X[max], float B[max], int n ) {
for(int i = 0; i<n; i++) {
if (A[i][i]!=0) {
if (i==0)
X[i] = B[i]/A[i][i]; 
else {
X[i] = B[i];
for(int j=0; j<i; j++)
X[i]=X[i]-A[i][j]*X[j];
X[i] = X[i]/A[i][i];
}
}
else
return 0;
}
return 1;
}
/* Chương trình chính */
int main() {
int n;
float A[max][max],B[max],X[max];
cout<<"So phuong trinh n = "; cin>>n;
cout<<"Nhap vao ma tran tam giac duoi A\n";
Nhap(A,n);
cout<<"\nNhap vao ma tran he so B\n";
Nhap(B,n);
cout<<"Ma tran A";
Xuat(A,n);
cout<<"\nMa tran B\n";
Xuat(B,n);
if(HeTamGiacDuoi(A,X,B,n))
XuatNghiem(X,n,"x");
else
cout<<"\nHe phuong trinh tuyen tinh vo nghiem";
getch();
return 0;

}
Kết quả chạy chương trình:

Tag: C, C++, Hệ phương trình tuyến tính, tam giác trên, tam giác dưới, tam giác trên

More about →

Code C++: Giải hệ phương trình tuyến tính dạng tam giác trên

Cho hệ phương trình tuyến tính dạng tam giác trên:

Nghiệm của hệ trên được xác định như sau:

Cài đặt chương trình:
#include <conio.h>
#include <iostream>
#define max 100
using namespace std;
/* Nhập ma trận tam giác trên */
void Nhap(float A[max][max],int n) {
for(int i = 0; i<n; i++)
for(int j = i; j<n; j++) {
cout<<"a["<<i<<"]["<<j<<"] = ";
cin>>A[i][j];
}
}
/* Nhập ma trận hệ số tự do */
void Nhap(float B[max],int n){
for(int i = 0; i<n; i++) {
cout<<"b["<<i<<"] = ";
cin>>B[i];
}
}
/* Xuất ma trận hệ số tự do */
void Xuat(float B[max],int n) {
cout<<"(";
for(int i = 0; i<n-1; i++)
cout<<B[i]<<",";
cout<<B[n-1]<<")";
}
/*Xuất ma trận */
void Xuat(float A[max][max], int n){
cout<<"\n";
for(int i=0 ; i<n; i++){
cout<<endl;
for(int j=0 ; j<n; j++)
if(i>j)
cout<<"0\t";
else
cout<<A[i][j]<<"\t";
}
}
/* Xuất nghiệm */
void XuatNghiem(float X[], int n, char * s){
cout<<"\nNghiem cuahe A.X = B\n";
for(int i=0; i<n; i++)
cout<<s<<i+1<<" = "<<X[i]<<endl;
}
/* Hệ tam giác trên */
char HeTamGiacTren (float A[max][max], float X[max], float B[max], int n ) {
for(int i = n-1; i>=0; i--) {
if (A[i][i]!=0) {
if (i==n-1)
X[i] = B[i]/A[i][i];
else {
X[i] = B[i];
for(int j=i+1; j<n; j++)
X[i]=X[i]-A[i][j]*X[j];
X[i] = X[i]/A[i][i];
}
}
else
return 0;
}
return 1;
}
/* Chương trình chính */
int main(){
int n;
float A[max][max],B[max],X[max];
cout<<"So phuong trinh n = "; cin>>n;
cout<<"Nhap vao ma tran tam giac tren A\n";
Nhap(A,n);
cout<<"\nNhap vao ma tran he so B\n";
Nhap(B,n);
cout<<"Ma tran A";
Xuat(A,n);
cout<<"\nMa tran B\n";
Xuat(B,n);
if(HeTamGiacTren(A,X,B,n))
XuatNghiem(X,n,"x");
else
cout<<"\nHe phuong trinh tuyen tinh vo nghiem";
getch();
return 0;

}
Kết quả chạy chương trình:

Tag: C, C++, Hệ phương trình tuyến tính, tam giác trên, tam giác dưới

More about →

Code C++: Phép toán cộng, nhân hai ma trận

- Cộng hai ma trận

Cho A=(a_ij) và B=(b_ij) là hai ma trận cùng cấp m x n. Khi đó, C=A ± B cũng là ma trận cấp m x n và được xác định bởi c_ij  =  a_ij  ± b_ij,  1 ≤ i ≤ m, 1 ≤ j ≤ n.

- Nhân hai ma trận

Cho A=(a_ij) là ma trận trận cấp m x n và B=(b_jk) là ma trận cấp n x p. Khi đó, C=A.B = (c_ik) là ma trận cấp m x p.

Cài đặt mã nguồn

#include <conio.h>

#include <iostream>

#define max 100

using namespace std;

/*Hàm nhập ma trận hệ số*/

void NhapMaTran(float A[max][max], int m, int n, char ch)  {

for(int i = 0; i<m; i++)

for(int j = 0; j<n; j++) {

cout<<ch<<"["<<i<<"]["<<j<<"] = ";

cin>>A[i][j];

}

}

/* Hàm xuất ma trận*/

void XuatMaTran(float A[max][max], int m, int n) {

for(int i=0 ; i<m; i++){

cout<<endl;

for(int j=0 ; j<n; j++)

cout<<A[i][j]<<"\t";

}

}

/*C = A+B*/

void CongMaTran(float A[max][max], float B[max][max], float C[max][max], int m, int n) {

for(int i = 0; i<m; i++)

for(int j = 0; j<n; j++)

C[i][j] = A[i][j]+B[i][j];

}

/*A cap mxn * B cap nxp = C cap mxp*/

void NhanMaTran(float A[max][max],float B[max][max], float C[max][max],int m,int n,int p){ 

for(int i = 0; i<m; i++)

for(int k = 0; k<p; k++) {

C[i][k]=0;

for(int j = 0; j<n; j++)

C[i][k] = C[i][k]+A[i][j]*B[j][k];

}

}

/*Chuong trinh chinh*/

int main() {

int m,n,p;

float A[max][max],B[max][max],C[max][max],D[max][max];

cout<<"Nhap m = "; cin>>m;

cout<<"Nhap n = "; cin>>n;

cout<<"Nhap p = "; cin>>p;

cout<<"Nhap ma tran A cap "<<m<<"x"<<n<<endl;

NhapMaTran(A,m,n,'A');

cout<<"Nhap ma tran B cap "<<m<<"x"<<n<<endl;

NhapMaTran(B,m,n,'B');

cout<<"Nhap ma tran C cap "<<n<<"x"<<p<<endl;

NhapMaTran(C,n,p,'C');

cout<<"Ma tran A";

XuatMaTran(A,m,n);

getch();

cout<<"\n\nMa tran B";

XuatMaTran(B,m,n);

getch();

cout<<"\n\nMa tran C";

XuatMaTran(C,n,p);

getch();

cout<<"\n\nMa tran D = A+B";

CongMaTran(A,B,D,m,n);

XuatMaTran(D,m,n);

getch();

cout<<"\n\nMa tran D = A.C";

NhanMaTran(A,C,D,m,n,p);

XuatMaTran(D,n,p);

getch();

return 0;

}

Kết quả khi chạy chương trình

Tag: C, C++, ma trận, matrix, array, cộng hai ma trận, nhân hai ma trận

More about →

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

More about →

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 1: Viế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

More about →

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

More about →