Data Structures and Algorithms

Nguồn: www.e-ptit.edu.vn


Cấu trúc dữ liệu và giải thuật:

Chương trình đệ quy:

Đặc điểm chung của chương trình đệ quy là:

1)      Chương trình này có thể gọi đến chính nó.

2)      Khi chương trình gọi đến chính nó, mục đích để giải quyết 1 vấn đề tương tự nhưng nhỏ hơn

3)      Vấn đề nhỏ hơn  này đến một lúc nào đó có thể đơn giản đến  mức mà chương trình có thể tự giải quyết mà không cần  gọi đến chính nó nữa

Khi chương trình gọi tới chính nó , các tham số hoặc khoảng  tham số  thường trở nên nhỏ hơn phản ánh một thực tế là vấn đề đã trở nên nhỏ hơn, dễ hơn.

Khi tham số tới mức cực tiểu, một điều kiện so sánh được kiểm tra và chương trình kết thúc, chấm dứt việc gọi tới chính nó.

ƯU ĐIỂM:

1)      Có thể thực hiện một số lượng lớn các thao tác thông qua một đoạn chương trình ngắn gọn

2)      Định nghĩa một tập hợp vô hạn các đối tượng thông qua một số hữu hạn lời phát biểu.

NHƯỢC ĐIỂM:

1)      Khi một thủ tục đệ quy gọi đến chính nó, một bản sao của tập các đối tượng được sử dụng trong thử tục này như các biến, hằng,  các thủ tục con, …. cũng được tạo  ra.  Do vậy nên hạn chế việc khai báo và  sử dụng các đối tượng này  trong thủ tục đệ quy nếu không cần thiết nhằm tránh lãng phí bộ nhớ , đặc biệt đối với các lời gọi đệ quy được gọi đi gọi lại nhiều lần.  Các đối tượng cục bộ  của 1 thủ tục đệ quy  khi được tạo ra nhiều lần, mặc dù có cùng tên , nhưng do khác phạm vi  nên không ảnh hưởng gì đến chương trình . Các đối tượng sẽ được giải phóng khi  thủ tục chứa nó kết thúc.

2)       Trong nhiều trường hợp, một chương trình có thể viết dưới dạng đệ qui. Tuy nhiên đệ qui không hẳn đã là giải pháp tốt cho vấn đề.  Nhìn chung khi chương trình có thể viết dưới dạng lặp hoặc các cấu trúc lệnh khác thì  không nên sử dụng đệ qui.

a)      Lý do thứ nhất:

Như đã nói ở trên, khi một thủ tục đề qui gọi đến chính nó, tập các đối tượng được sử dụng trong thủ tục này như các biến, hằng, cấu trúc,… sẽ được tạo ra.  Ngoài ra, việc chuyển giao điều khiển giữa các thủ tục cũng cần lưu trữ các thông số  dùng cho việc trả lại điều khiển  cho thủ tục ban đầu.

b)      Lý do thứ 2: Việc sử dụng đệ qui đôi khi gây ra sự tính toán thừa, không cần thiết do tính chất gọi tự động thực hiện thủ tục khi chưa gặp điều kiện dừng của đệ

THIẾT KẾ GIẢI THUẬT  ĐÊ QUI

Chương trình tính hàm n!

Ta có:

n! = 1 nếu n =0

ngược lại: n! = (n-1)!*n;

int giaithua( int n){

if ( n=0) return 1;

else return (giaithua(n-1)*n);

}

Code implementation:

// Tinh n! su dung phuong phap de qui



#include"iostream"

using namespace std;



// ham de qui tinh n!

int giaithua( int n)

{

    if( n == 0) return 1;

    else return (giaithua(n-1)*n);

}



int main()

{

    int n;

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

    cout<<"\n n! = " << giaithua(n)<< endl;

    system("pause");

    return 0;

}

Thuật toán Euclide tính ước chung lớn nhất của 2 số nguyên dương.
Cơ sở:
USCLN(m,n) = USCLN(m mod n, n )
r = m mod n;
Nếu r = 0: USCLN(m,n) = n;
Ngược lại: USCLN(m,n) = USCLN(n, r)

// Tinh uoc so chung lon nhat cua 2 so nguyen duong bang thuat toan Euclid

#include"iostream"

using namespace std;



int tim( int m, int n)

{

    if ( m% n == 0) return n;

    else return ( tim(n,m%n));

}



int main()

{

    int m,n;

    cout<<" Nhap vao 2 so can tim uoc chung lon nhat: ";

    cout<<" \nNhap m = "; cin >> m;

    cout<<" \nNhap n = "; cin >> n;

    cout<<" \nUoc chung lon nhat cua m va n la : ";

    cout<< tim(m,n)<< endl;

    system("pause");

    return 0;

}

Các giải thuật đệ qui chia để trị.
Ý tưởng của các dạng thuật toán chia để trị là phân chia bài toán ban đầu thành 2 hay nhiều bài toán con có dạng tương tự và lần lượt giải quyết từng bài toán con này.
Các bài toán này được coi là dạng đơn giản hơn của bài toán ban đầu , do vậy có thể sử dụng lời gọi đệ qui để giải quyết.
Thông thường các thuật toán chia để trị chia bộ dữ liệu đầu vào thành 2 phần riêng rẽ , sau đó gọi 2 thủ tục đệ qui với bộ dữ liệu đầu vào là các phần vừa được chia.
Bài toán tháp Hà Nội:
Có 3 chiếc cọc và một bộ n đĩa. Các đĩa này có kích thước khác nhau và mỗi đĩa có một lỗ ở giữa để có thể xuyên chúng vào các cọc. Ban đầu tất cả các đĩa đều nằm trên một chiếc cọc, trong đó đĩa nhỏ hơn bao giờ cũng nằm trên đĩa lớn hơn.
Yêu cầu:
Chuyển bộ n đĩa từ cọc A sang cọc đích trung gian ( có thể lấy cọc B làm cọc trung gian) với các điều kiện:
+ Mỗi lần chuyển một đĩa
+ Trong mọi trường hợp, đĩa có kích thước nhỏ hơn bao giờ cũng nằm trên đĩa có kích thước lơn hơn
Với n =1: Chuyển trực tiếp đĩa 1 từ cọc A sang cọc C
Bước 1: Chuyển n-1 đĩa từ cọc A sang cọc B lấy cọc C làm cọc trung gian
Bước 2: Chuyển đĩa dưới cùng ( đĩa n) từ cọc A sang cọc C
Bước 3: Chuyển n-1 đĩa từ cọc B sang cọc C lấy cọc A làm cọc trung gian
Như vậy: Bài toán chuyển n đĩa đã chuyển thành một bài toán đơn gián hơn là n-1 đĩa.
Điểm dừng của bài toán đệ qui là khi n =1, ta chuyển thẳng đĩa từ cọc này sang cọc đích.
Bài toán gồm 2 hàm:

void chuyen ( int n, char a, char c);

// Thuc hien viec chuyen dia thu n tu coc A sang cọc C

Void thaphn(int n, char a, char c, char b);

//Hàm đệ qui thực hiện việc chuyển n đĩa từ cọc A sang cọc C lấy cọc B làm cọc trung gian

Code implemantation:

// Bai toan thap Ha Noi

#include"iostream"

#include"conio.h"

using namespace std;



// Chuyen dia thu n tu coc a sang coc c

void chuyen( int n, char a, char c)

{

     cout<<"Chuyen dia thu "<< n << " tu coc " << a << " sang coc " << c << endl;

     return ;

}





void thaphn(int n, char a, char c, char b)

{

     if( n==1) chuyen(1,a,c);

     else

     {

         //Chuyen n-1 dia tu coc a sang cac b ( c la coc trung gian)

         thaphn( n-1,a,b,c);

         // Chuyen dia thu n tu coc a sang coc c

         chuyen(n,a,c);

         //Chuyen n-1 dia tu coc b sang coc c ( a = coc trung gian)

         thaphn(n-1,b,c,a);

     }

     return;

}



int main()

{

    int sodia;

    cout<<"Cho biet so dia can chuyen: "; cin >> sodia;

    cout<<"\nCac buoc chuyen nhu sau: \n\n";

    thaphn(sodia,'a','c','b');

    system("pause");

    return 0;

}

     

THUẬT TOÁN QUAY LUI (BACKTRACKING ALGORITHMS)
Bài toán mã đi tuần:
Cho bàn cờ có kích thước nxn ( có n^2 ô). Một quân mã được đặt tại tọa độ đầu tiên (x0,y0) và được phép dịch chuyển theo luật cờ thông thường.
Bài toán đặt ra là từ ô ban đầu , tìm một chuỗi các nước đi của quân mã , sao cho quân mã này đi qua tất cả các ô của bàn cờ và mỗi ô chỉ đi một lần.
Xây dựng ý tưởng:
Nhiệm vụ: Tìm kiếm nước đi tiếp theo của quân mã hoặc kết luận là không còn nước đi kế tiếp thỏa mãn.
Tại mỗi bước, nếu tìm được nước đi kế tiếp, ta tiến hành ghi lại bước đi này và chuỗi các nước đi trước đó và tiếp tục quá trình tìm kiếm nước đi.
Nếu tại nước đi nào đó ta không thể tìm kiếm nước đi kế tiếp thỏa mãn yêu cầu, ta quay lại bước trước và hủy bỏ nước đã lưu trước đó và thử sang một nước đi mới.
Quá trình có thể thử rồi quay lại nhiều lần cho đến khi tìm ra giải pháp hoặc đã thử hết các phương án mà không tìm ra giải pháp.
Giải thuật:
void thunuoctieptheo{
khởi tạo danh sách các nước đi kế tiếp;
do{
lựa chọn một nước đi kế tiếp từ danh sách;
if Chấp nhận được{
ghi lại nước đi;


if bàn cờ còn trống{
thử nước đi tiếp theo;
if nước đi không thành công{
hủy bỏ nước đi đã lưu ở phía trước;
}
}while( nước đi không thành công && vẫn còn nước đi)

//bai toan ma di tuan.cpp

#include

using namespace std;

#define maxn 10

//void ThuNuocTiepTheo( int i, int x, int y, int &q);

//void InBanco ( int n);

//void XoaBanco(int n);



int Banco[maxn][maxn];

int dx[8] = { 2, 1,-1,-2,-2,-1,1,2};

int dy[8] = {-1,-2,-2,-1, 1, 2,2,1};

int n = 8;



void ThuNuocTiepTheo( int i, int x, int y, int &q)

{

     int k,u,v, q1;

     k = 0;

     do{

         q1 = 0;

         u = x + dx[k];

         //cout<< "\n u = " << u;

         v = y + dy[k];

         //cout<< " v = " << v;

         

         

         if((0<=u)&&(u<n)&&(0<=v)&&(v<n)&&Banco[u][v]==0)

         {

         Banco[u][v] = i;

         //cout<<"\n Banco " << u << " " << v << " = " << i;

         

         

          if(i<n*n)

          {

                   ThuNuocTiepTheo(i+1,u,v,q1);

                   if(q1 == 0)Banco[u][v]=0;

            //       cout<< "\n Ban co " << u << " " << v << "  " << Banco[u][v];

          }else q1 = 1;

         }

     

     k++;

     }while (( q1 == 0) && (k<8));

     

     q = q1;

     //cout<< " q1 = " << q1;

     //system("pause");

     

     

}



void InBanco( int n)

{

     cout<<"\n";

     int i,j;

     for(i=0;i<= n-1;i++){

       for( j =0;j<=n-1;j++)

         if(Banco[i][j]<10) cout<< " " <<Banco[i][j];

         else cout<< " " << Banco[i][j];

       cout<<"\n";

       }

}



void XoaBanco(int n)

{

     int i,j;

     for( i =0;i<= n-1; i++)

       for(j =0;j<= n-1;j++) Banco[i][j] =0;

}



int main()

{

    int q = 0;

    cout<<" Cho kich thuoc ban co:";

    cin >> n;

    XoaBanco(n);

    Banco[0][0]= 1;

    ThuNuocTiepTheo(2,0,0,q);

    cout<<"\nKet qua : \n\n";

    InBanco(n);

    system("pause");

    return 0;

}