[C\C++] Ví dụ sử dụng cấu trúc trong lập trình C\C++ [struct SV]

Ví dụ: Viết các hàm thực hiện
 - Nhập thông tin SV gồm: họ tên, địa chỉ, tuổi, điểm toán, lý, hóa
 - Tính điểm tổng kết
 - In thông tin sinh viên
  Ví dụ nhập thông tin cho 1 sinh viên

[Code Turbo C++]

#include<iostream.h>
#include<stdio.h>
#include<conio.h>
#include<string.h>

// Dinh nghia cau truc SV
struct SV{
 char ht[30],dc[50];
 int tuoi;
 float dT,dL, dH;
};

// Khai bao bien cau truc
SV a;

// Ham nhap thong tin
void NhapTT(){
  fflush(stdin); // xu ly bo dem cho viec nhap mot xau
  cout<<"\n NHAP THONG TIN CHO SINH VIEN ";
  cout<<"\n - Ho ten: "; gets(a.ht);
  cout<<"\n - Dia chi: "; gets(a.dc);
  cout<<"\n - Tuoi: "; cin>>a.tuoi;
  cout<<"\n - Diem toan: "; cin>>a.dT;
  cout<<"\n - Diem ly: "; cin>>a.dL;
  cout<<"\n - Diem hoa: "; cin>>a.dH;
 }

// Ham Tinh diem
float TinhDiem(){
 return (a.dT+a.dL+a.dH)/3;
}

// Ham In thong tin
void InTT(){
 // tim xep loai
 char xepLoai[10];
 float dtk=TinhDiem();
 if (dtk<5) strcpy(xepLoai,"Truot");
  else if (dtk<6) strcpy(xepLoai,"TB");
   else if (dtk<7) strcpy(xepLoai,"TBK");
    else if (dtk<8) strcpy(xepLoai,"Kha");
      else if (dtk<9) strcpy(xepLoai,"Gioi");
       else if (dtk<=10) strcpy(xepLoai,"XS");
         else strcpy(xepLoai,"");
 cout<<"\n IN THONG TIN SINH VIEN ";
 cout<<"\n - Ho ten: "<<a.ht;
 cout<<"\n - Dia chi: "<<a.dc;
 cout<<"\n - Tuoi: "<<a.tuoi;
 cout<<"\n - Diem tong ket: "<<dtk;
 cout<<"\n - Xep loai: "<<xepLoai;
}

// Ham main
void main(){
  NhapTT();
  InTT(); // ham InTT() da goi den ham TinhDiem
  getch();
}

>> [Tải code chương trình tại đây - Lưu ý: Sau 5s, Click Bỏ qua quảng cáo (Skin Ad)]

[C\C++] Tính Định thức của ma trận [Xử lý ma trận - mảng 2 chiều]

Ý tưởng thuật toán: ta tiến hành phân rã ma trận A = L.U .

Ta có: Det(A)=Det(L)*Det(U) Det(L) = 1 nên Det(A) = Det(U).

Ví dụ ma trận:



[Code Turbo C++]

#include "conio.h"
#include "iostream.h"
#define max 100

/*Nhap ma tran*/
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];
   }
}

/*Xuat ma tran*/
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(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];
  }
}

//dinh thuc ma tran tam giac
double DinhThucMaTranTamGiac(float A[max][max], int n) {
  double temp = 1;
  for(int i = 0; i<n; i++)
    temp*=A[i][i];
    return temp;
}

/*chuong trinh chinh*/
void main() {
  int n;
  float A[max][max],L[max][max],U[max][max];
  clrscr();
  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);
  cout<<"\nDet(A) = Det(L)*Det(U) = "<<DinhThucMaTranTamGiac(U,n);
  getch();
}


[Tải code chương trình tại đây - Lưu ý: Sau 5s, Click Bỏ qua quảng cáo (Skin Ad)]

[C\C++] Giải hệ phương trình tuyến tính dựa vào phân rã LU [Xử lý ma trận - mảng 2 chiều]

Ý tưởng giải thuật: cho hệ phương trình tuyến tính tổng quát A.X = B . Ta tiến hành phân rã A = L.U . Trong đó, L là ma trận tam giác dưới và U là ma trận tam giác trên.
Khi đó,
[Code Turbo C++]

#include "conio.h"
#include "iostream.h"
#define max 100

/*Nhap ma tran he so*/
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];
  }
}

/*Nhap ma tran he so tu do*/
void Nhap(float B[max],int n) {
  for(int i = 0; i<n; i++) {
   cout<<"b["<<i<<"] = ";
   cin>>B[i];
 }
}

/*Xuat ma tran he so tu do*/
void Xuat(float B[max],int n) {
    cout<<"(";
    for(int i = 0; i<n-1; i++)
     cout<<B[i]<<",";
   cout<<B[n-1]<<")";
}

/*Xuat ma tran*/
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++)
    cout<<A[i][j]<<"\t";
 }
}

/*Xuat nghiem*/
void XuatNghiem(float X[], int n, char * s) {
 cout<<"\nNghiem cua he PTTT";
 for(int i=0; i<n; i++)
   cout<<s<<i+1<<"="<<X[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;
}

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;
}

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(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];
  }
}

/*Giai he phuong trinh tong quat LUX=B*/
void GiaiHePTTT(float A[max][max], float X[max], float B[max], int n) {
  float L[max][max],U[max][max], Y[max];
  cout<<"Phan ra A = L.U\n";
  PhanRaLU(A,L,U,n);
  cout<<"Ma tran L";
  Xuat(L,n);
  cout<<"\nMa tran U";
  Xuat(U,n);
  cout<<"\nGiai LY = B. Nghiem Y";
  if(HeTamGiacDuoi(L,Y,B,n)) {
    XuatNghiem(Y,n,"\ny");
    cout<<"\nGiai UX = Y. Nghiem X";
    if(HeTamGiacTren(U,X,Y,n))
      XuatNghiem(X,n,"\nx");
    else
      cout<<"\nHe pttt k co nghiem duy nhat";
   } else
     cout<<"\nHe pttt k co nghiem duy nhat";
  }
//////////////////////////
void main() {
 int n;
 float A[max][max], B[max], X[max];
 clrscr();
 cout<<"Nhap so he phuong trinh n = ";
 cin>>n;
 cout<<"Nhap ma tran he so A\n";
 Nhap(A,n);
 cout<<"Nhap ma tran he so tu do B\n";
 Nhap(B,n);
 GiaiHePTTT(A,X,B,n);
 getch();
}


[Tải code chương trình tại đây - Lưu ý: Sau 5s, Click Bỏ qua quảng cáo (Skin Ad)]

[C\C++] Thuật toán phân rã ma trận A = LU [Xử lý ma trận - mảng 2 chiều]

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


[Code Turbo C++]

#include "iostream.h"
#define max 100

// ham nhap ma tran
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];
  }
}

// ham xuat ma tran
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(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];
  }
}

// ham chinh
void main() {
 int n;
 float A[max][max],L[max][max],U[max][max];
 clrscr();
 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();

}

[Tải code chương trình tại đây - Lưu ý: Sau 5s, Click Bỏ qua quảng cáo (Skin Ad)]

[C\C++] Giải hệ phương trình tuyến tính dạng tam giác dưới [Xử lý ma trận - mảng 2 chiều]

Bài toán: Viết chương trình giải hệ phương trình tuyến trính dạng tam giác dưới



[Code Turbo C++]

#include "conio.h"
#include "iostream.h"
#define max 100
//Nhap ma tran tam giac duoi
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];
}
}
/*Nhap ma tran he so tu do*/
void Nhap(float B[max],int n) {
for(int i = 0; i<n; i++) {
cout<<"b["<<i<<"] = ";
cin>>B[i];
}
}
/*Xuat ma tran he so tu do*/
void Xuat(float B[max],int n) {
cout<<"(";
for(int i = 0; i<n-1; i++)
cout<<B[i]<<",";
cout<<B[n-1]<<")";
}
/*Xuat ma tran*/
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";
}
}
/*Xuat nghiem*/
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;
}
/*He tam giac duoi*/
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;
}
/*Chuong trinh chinh*/
void main() {
int n;
float A[max][max],B[max],X[max];
clrscr();
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);
clrscr();
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();
}

[Tải code chương trình tại đây - Lưu ý: Sau 5s, Click Bỏ qua quảng cáo (Skin Ad)]

[C\C++] Giải hệ phương trình tuyến tính dạng tam giác trên [Xử lý ma trận - mảng 2 chiều]

Bài toán: Viết chương trình giải hệ phương trình tuyến tính dạng tam giác trên



[Code Turbo C++ 3.0]
#include "conio.h"
#include "iostream.h"
#define max 100
//Nhap ma tran tam giac tren
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];
}
}
/*Nhap ma tran he so tu do*/
void Nhap(float B[max],int n) {
for(int i = 0; i<n; i++) {
cout<<"b["<<i<<"] = ";
cin>>B[i];
}
}
/*Xuat ma tran he so tu do*/
void Xuat(float B[max],int n) {
cout<<"(";
for(int i = 0; i<n-1; i++)
cout<<B[i]<<",";
cout<<B[n-1]<<")";
}
/*Xuat ma tran*/
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";
}
}
/*Xuat nghiem*/
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;
}
/*He tam giac tren*/
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;
}
/*Chuong trinh chinh*/
void main() {
int n;
float A[max][max],B[max],X[max];
clrscr();
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);
clrscr();
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();
}

[Tải code chương trình tại đây - Lưu ý: Sau 5s, Click Bỏ qua quảng cáo (Skin Ad)]

[C\C++] Một số phép toán cơ bản trên ma trận [Xử lý ma trận - mảng 2 chiều]

Bài toán: Viết chương trình thực hiện các phép toán trên ma trận:

[Code Turbo C++ 3.0]

#include "conio.h"
#include "iostream.h"
#define max 100
/*Nhap ma tran he so*/
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];
}
}
/*Xuat ma tran*/
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*/
void main() {
int m,n,p;
float A[max][max],B[max][max],C[max][max],D[max][max];
clrscr();
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');
clrscr();
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();
}

[Tải code chương trình tại đây - Lưu ý: Sau 5s, Click Bỏ qua quảng cáo (Skin Ad)]

** Đề nghị độc giả thực hiện các phép toán còn lại.

[C\C++] Nhập xuất ma trân [Xử lý ma trận - mảng 2 chiều]

Bài toán: Viết chương trình nhập vào ma trận chứa các số thực có kích thức không quá 100. In ma trận (theo dạng bảng số) ra màn hình.
Ví dụ: 

[Code Turbo C++]


#include <conio.h>
#include <iostream.h>
#define max 100
float A[max][max];  // khai bao ma tran A
/*Nhap ma tran he so*/
void NhapMaTran(int m, int n) {
 for(int i = 0; i<m; i++)
  for(int j = 0; j<n; j++) {
    cout<<"a["<<i<<"]["<<j<<"] = ";
    cin>>A[i][j];
  }
}
/*Xuat ma tran*/
void XuatMaTran(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";
  }
}
/*Chuong trinh chinh*/
void main() {
  int m, n;
  clrscr();
// nhap kich thuoc ma tran
  do{
  cout<<"Nhap so dong m = ";
  cin>>m;
  if (m<1||m>max) cout<<"\n nhap lai m";
 }while(m<1||m>max);
do{
  cout<<"Nhap so dong n = ";
  cin>>n;
  if (n<1||n>max) cout<<"\n nhap lai n";
 }while(n<1||n>max);
  cout<<"\nNhap ma tran A cap "<<m<<"x"<<n<<endl;
  NhapMaTran(m,n);
  cout<<"\nXuat ma tran A";
  XuatMaTran(m,n);
getch();
}


[Tải code chương trình tại đây - Lưu ý: Sau 5s, Click Bỏ qua quảng cáo (Skin Ad)]

[ Search ] Tìm kiếm nhị phân [Code C++]

Thuật toán tìm kiếm nhị phân - Binary sort 

Ý tưởng của thuật toán: 
Phép tìm kiếm nhị phân được thực hiện trên dãy khoá có thứ tự (xét dãy tăng dần):
 a[0]<=a[1]<=a[2]<=...<=a[n-1]. Giá trị cần tìm x.

Chia đôi dãy khoá cần tìm kiếm. So sánh khoá giữa dãy với x, có 3 trường hợp xãy ra:
-  Giá trị khoá này bằng x, tìm kiếm thành công
-  Giá trị khoá này lớn hơn x, thì ta tiến hành tìm x với nữa bên trái của khoá này
-  Giá trị khoá này nhỏ hơn x, thì ta tiến hành tìm x với nữa bên phải của khoá này

Trường hợp tìm kiếm thất bại khi dãy khoá cần tìm không có phần tử nào.

Cài đặt Thuật toán [code Turbo C\C++]:

/*Thuật toán tìm kiếm nhị phân không đệ quy*/

int BinarySearch(int x, int a[],int n) // Tìm khoá x trong dãy a1,a2…,an
{

 int  left =0; //Left trỏ về chỉ số đầu dãy
 int right =n-1; //right trỏ về vị trí cuối dãy
 int mid; // mid trỏ vào giữa dãy
 int found = 0; //dùng để xác tìm thành công hay không (0: không tìm thấy, 1: tìm thấy)

 while (left <= right && found==0){
    mid = (left + right) / 2;//mid ở giữa dãy
    if (a[mid]== x) //trường hợp tìm thấy dừng thuật toán
       found = 1;
     else
          if (a[mid]<x)
              left = mid +1; //xác định lại đoạn tìm tiếp theo là bên phải
          else
              right = mid -1; //xác định lại đoạn tìm tiếp theo là bên trái
  }

return found;
}

/*Thuật toán tìm kiếm nhị phân đệ quy*/

int BinSearch(int[] a, int gt, int dau, int cuoi)
{
    int i, j;
    i = dau; j = cuoi;
    if (i > j)
   {
        return -1; // không tìm thấy
    }
    int giua = (i + j) / 2;
    if (gt == a[giua])
      {
          return giua; // tìm thấy
       }
    else if (gt < a[giua])
      {
          j = giua - 1;
          return BinSearch(a, gt, dau, j);
       }
    else
      {
          i = giua + 1;
          return BinSearch(a, gt, i, cuoi);
       }
   }

// Đề nghị độc giả chuyể hàm cài trên sang đệ quy và viết đầy đủ chương trình để mo phỏng thuật toán.


--------------------------------------------
Xem thêm các thuật toán khác: 

[ Search ] Tìm kiếm tuần tự [Code C++]

Thuật toán tìm kiếm tuần tự - Sequential search

Ý tưởng thuật toán: xét dãy số cần tìm có n phần tử: a[0], a[1], a[2], ... , a[n-1]. Giá trị cần tìm là x.
 - Bắt đầu từ khoá đầu tiên, lần lượt so sánh khoá x với khoá tương ứng trong dãy.
 - Quá trình tìm kiếm kết thúc khi tìm được khoá thoả mãn hoặc đi đến hết dãy hoặc gặp điều kiện dừng vòng lặp.

Ví dụ: Cho dãy số a[]={1,25,6,5,2,37,40}; tìm phần tử x=37
Kết quả là tìm thấy x trong dãy.

Cài đặt thuật toán:
Có 2 thuật toán tìm tuần tự trên dãy khoá đầu vào khác nhau. 

[Code Turbo C++]

+ Trên dãy khoá chưa sắp xếp

int SequentialSearch(int x, int a[],int  n){
 int i =1;
  while (i <n &&a[i]!=x)
    i = i+1;
  return (i);  // nếu giá trị trả về là i<=n-1 (tìm thấy), i=n (không tìm thấy)
}

+ Trên dãy khoá đã được sắp xếp

int SequentialSearch (int x, int a[], int n){
  int i =1;
  while (i <=n && a[i]<x) i = i+1;

  if (a[i]==x) return 1;
  else return 0; // giá trị trả về là 1 (tìm thấy), 0 (không tìm thấy)
}

// Đề nghị độc giả viết tiếp các hàm còn lại để thực thi các thuật toán trên.

[ Sort ] Thuật toán Insert-Sort [Code C++]

 Thuật toán Insert-Sort

Ý tưởng thuật toán: xét dãy n phần tử a[0], a[1], a[2] ,..., a[n-1].
- Xem dãy gồm 1 phần tử a[0] là dãy có thứ tự.
- Thêm a[1] vào dãy có thứ tự a[0] sao cho dãy mới a[0], a[1] là dãy có thứ tự. Nếu a[1] < a[0] ta đổi chỗ a[1] với a[0].
- Thêm a[2] vào dãy có thứ tự a[0], a[1] sao cho dãy mới a[0], a[1], a[2] là dãy có thứ tự.
- Tương tự, tiếp tục như thế đến n – 1 bước ta sẽ có dãy có thứ tự.

Ví dụ: sử dụng thuật toán Insertion Sort sắp xếp dãy {3,7,22,3,1,5,8,4,3,9} theo thứ tự tăng dần.


Kết quả sau khi đã thực hiện thuật toán: {1,3,3,3,4,5,7,9,22}

Cài đặt thuật toán:

[Code Turbo C++]

#include <iostream.h>
#include <conio.h>
#define max 100
//nhap day
void NhapDay(int a[],int n) {
   for(int i=0; i<n; i++) {
    cout<<"\n a["<<i<<"] =";
    cin>>a[i];
   }
}
//xuat day
void XuatDay(int a[],int n) {
   cout<<"\n IN DAY: ";
   for(int i=0; i<n; i++)
     cout<<a[i]<<"\t";
}
//hoan vi 2 phan tu
void Swap(int &a,int &b) {
   int t = a;
   a = b;
   b = t;
}
//thu tuc Insertion Sort
void InsertionSort(int a[],int n) {
   for(int i=1; i<n; i++)
     for(int j=i; j>0; j--)
       if(a[j]<a[j-1])
        Swap(a[j],a[j-1]);
}
//chuong trinh chinh
void main() {
  int a[max],n;
  clrscr();
  cout<<"Nhap so phan tu:";
  cin>>n;
  NhapDay(a,n);
  cout<<"\n Day vua nhap la:";
  XuatDay(a,n);
  cout<<endl;
  InsertionSort (a,n);
  cout<<"\n Day vua sap xep la:";
  XuatDay(a,n);
  getch();
}

// Đề nghị độc giả chuyển code trên sang các ngôn ngữ lập trình khác

[ Sort ] Thuật toán Selection-Sort [Code C++]

 Thuật toán Selection-Sort

Ý tưởng thuật toán: xét dãy n phần tử a[0], a[1], a[2] ,..., a[n-1].
 - Chọn trong dãy a[0], a[1], a[2] ,..., a[n-1] ra phần tử có khỏa nhỏ nhất và đổi chỗ nó với a[0].
 - Chọn trong dãy a[1], a[1], a[2] ,..., a[n-1] ra phần tử có khỏa nhỏ nhất và đổi chỗ nó với a[1].
 - Tương tự, tiếp tục như thế sau n – 1 bước ta thu được danh sách có thứ tự.

Ví dụ: Sau 9 bước lặp ta thu được dãy đã được sắp xếp: {2, 3, 4, 5, 6, 6, 7, 7, 8, 9}.
[Mô phỏng]

Kết quả sau 9 bước lặp ta thu được dãy đã được sắp xếp: {2, 3, 4, 5, 6, 6, 7, 7, 8, 9}.

Cài đặt thuật toán:

[Code Turbo C++]

#include <iostream.h>
#include <conio.h>
#define max 100
//nhap day
void NhapDay(int a[],int n) {
  for(int i=0; i<n; i++) {
    cout<<"\n a["<<i<<"] =";
    cin>>a[i];
  }
}
//xuat day
void XuatDay(int a[],int n) {
  cout<<"\n IN DAY: ";
  for(int i=0; i<n; i++)
    cout<<a[i]<<"\t";
}
//hoan vi 2 phan tu
void Swap(int &a,int &b) {
   int t = a;
   a = b;
   b = t;
}
//thuat toan Selection Sort
void SelectionSort(int a[],int n) {
   int min; // chi so phan tu nho nhat trong day hien hanh
   for(int i=0; i<n-1; i++) {
      min = i;
      for(int j=i+1; j<n; j++)
         if(a[min]>a[j])
            min = j; //ghi nhan vi tri phan tu nho nhat
      if(min!= i)
           Swap(a[i],a[min]); // doi chu 2 phan tu
   }
}
//chuong trinh chinh
void main() {
  int a[max],n;
  clrscr();
  cout<<"Nhap so phan tu:";
  cin>>n;
  NhapDay(a,n);
  cout<<"\n Day vua nhap la:";
  XuatDay(a,n);
  cout<<endl;

  SelectionSort (a,n);
  cout<<"\n Day vua sap xep la:";
  XuatDay(a,n);

  getch();
}
// Đề nghị độc giả chuyển code trên sang các ngôn ngữ lập trình khác



--------------------------------------------
Xem thêm các thuật toán khác: 

[ Sort ] Thuật toán Bubble-Sort [Code C++]

Thuật toán Bubble-Sort

Ý tưởng thuật toán: 
 - Xuất phát từ phần tử cuối danh sách ta tiến hành so sánh với phần tử bên trái của nó.
 - Nếu phần tử đang xét có khóa nhỏ hơn phần tử bên trái của nó ta tiến đưa nó về bên trái của dãy bằng cách hoán vị với phần tử bên trái của nó.
 - Tiếp tục thực hiện như thế đối với bài toán có n phần tử thì sau n – 1 bước ta thu được danh
sách tăng dần.

Ví dụ: sử dụng thuật toán Bubble Sort sắp xếp dãy số {3, 10, 4, 6, 2, 6, 15, 3, 9,7} theo thứ tự tăng dần.


Sau 9 bước lặp ta thu được dãy đã được sắp xếp: {2, 3, 3, 4, 6, 6, 7, 9, 10, 15}.

Cài đặt thuật toán:
[ Code Turbo C++]

#include <iostream.h>
#include <conio.h>
#define max 100
//nhap day
void NhapDay(int a[],int n) {
  for(int i=0; i<n; i++) {
   cout<<"\n a["<<i<<"] =";
   cin>>a[i];
  }
}
//xuat day
void XuatDay(int a[],int n) {
  cout<<"\n IN DAY: ";
  for(int i=0; i<n; i++)
cout<<a[i]<<"\t";
}
//hoan vi 2 phan tu
void Swap(int &a,int &b) {
  int t = a;
  a = b;
  b = t;
}
//sap xep cac phan tu
void BubbleSort(int a[],int n) {
  for(int i = 0; i < n-1; i++)
    for(int j = n-1; j > i; j--)
      if(a[j]<a[j-1])
        Swap(a[j-1],a[j]);
}
//chuong trinh chinh
void main() {
 int a[max],n;
 clrscr();
 cout<<"\n Nhap so phan tu:";
 cin>>n;
 NhapDay(a,n);

  XuatDay(a,n);
  cout<<"\n Sap xep Bubble-Sort: \n";
  BubbleSort(a,n);
  cout<<"\n Day vua sap xep la:";
  XuatDay(a,n);
  getch();
}
// Đề nghị độc giả chuyển code trên sang các ngôn ngữ lập trình khác


--------------------------------------------
Xem thêm các thuật toán khác: 

Danh mục bài viết