Bài giảng Kỹ thuật lập trình - Chương 4, Phần 1: Một số cấu trúc dữ liệu và giải thuật căn bản

Kỹ thuật lập trình

Chương 4:

Một số cấu trúc dữ liệu và giải thuật căn bản

1.Đệ qui

1. Mô tả đệ qui

1.1 Khái niệm về đệqui

1.2 Các loại đệqui

1.3 Mô tả đệqui các cấu trúc dữliệu

1.4 Mô tả đệqui các giải thuật

1.5 Các dạng đệ qui đơn giản thường gặp

Khái niệm đệ qui

Mô tả mang tính đệ qui về một đối tượng là mô tả theo

cách phân tích đối tượng thành nhiều thành phần mà

trong số các thành phần có thành phần mang tính chất

của chính đối tượng được mô tả.

Tức là mô tả đối tượng qua chính nó.

Mô tả đệ quy tập sốtựnhiên N :

Số1 là sốtựnhiên ( 1 -N).

Sốtựnhiên bằng sốtựnhiên cộng 1.

Mô tả đệ quy cấu trúc ds(list) kiểu T :

Cấu trúc rỗng là một ds kiểu T.

Ghép nối một thành phần kiểu T(nút kiểu T ) với một ds kiểu T ta

có một ds kiểu T.

Mô tả đệquy cây gia phả: Gia phả của một người bao gồm

người đó và gia phả của cha và gia phả của mẹ

Ví dụ

Định nghĩa không đệ qui n!:

n! = n * (n-1) * … * 1

Định nghĩa đệ qui:

n! = 1

nếu n=0

n * (n-1)!nếu n>0

Mã C++:

int factorial(int n) {

if (n==0)

else

return 1;

return (n * factorial(n - 1));

}

Mô tả đệ quy thủ tục sắp tăng dãy

a[m:n] ( dãy a[m], a[m+1], . . . , a[n] ) bằng phương pháp Sort_Merge (SM):

SM (a[m:n]) ≡Merge ( SM(a[m : (n+m) div 2]) , SM (a[(n+m) div 2 +1 : n] )

Với : SM (a[x : x]) làthao tác rỗng (không làm gìcả).

Merge (a[x : y] , a[(y+1) : z]) làthủtục trộn 2 dãy tăng a [x : y] , a[(y+1) : z] để

được một dãy a[x : z] tăng.

Mô tả đệqui gồm hai phần

Phần neo:trường hợp suy biến của đối tượng

Vídụ: 1 là sốtựnhiên, cấu trúc rỗng là ds kiểu T, 0 ! = 1 ,

SM

(a[x:x]) là thao tác rỗng.

Phần quy nạp: mô tả đối tượng (giải thuật) thông qua chính đối

tượng (giải thuật ) đó một cách trực tiếp hoặc gián tiếp.

Vídụ:

n! = n * (n –1) !

SM (a[m:n]) ≡Merge (SM (a[m:( m+n) div 2] , SM (a[(m+n) div 2 +1

: n]) )

Đệ qui gồm hai loại

Đệqui trực tiếp

Đệqui gián tiếp

Giải thuật đệ qui

Giải thuật đệquy là giải thuật có chứa thao tác gọi đến nó

Đặc điểm: mô tả một dãy lớn các thao tác bằng một số ít các thao

tác trong đó có chứa thao tác gọi lại giải thuật (gọi đệquy)

Biểu diễn giải thuật đệqui

P

P[ S , P ]

Điều kiện dừng

Biểu diễn tổng quát

P

if B then P[ S , P ]

hoặc P P[ S , if B then P ]

Chương trình con đệqui

–Hàm đệqui

–Thủtục đệqui

Mô tả đệqui các giải thuật

Dãy sốFibonaci(FIBO) :{ FIBO (n) } ≡1 ,1 , 2 , 3 ,

5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , 233 , 377 , . . .

FIBO(0 ) = FIBO (1 ) = 1 ;

FIBO(n ) = FIBO (n -1 ) + FIBO ( n -2 ) ; với n > = 2

Giải thuật đệquy tính FIBO ( n ) là:

FIBO(n)

if ((n = 0 ) or ( n = 1 )) then return 1 ;

else return ( FIBO (n -1) + FIBO (n -2)) ;

Các dạng đệ qui đơn giản thường gặp

Đệqui tuyến tính: là dạng đệqui trực tiếp đơn giản nhất códạng

P Ù {

If (B) thực hiện S;

else { thực hiện S* ; gọi P }

}

Với S , S* là các thao tác không đệquy .

Vídụ:Hàm FAC(n) tính số hạng n của dãy n!

Dạng hàm trong ngôn ngữmã giả:

{ Nếu n = 0 thì FAC = 1 ; /* trường hợp neo*/

Ngược lại FAC = n*FAC(n-1) }

Dạng hàm trong C++ :

int FAC( int n )

{

if ( n == 0 ) return 1 ;

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

}

Thi hành hàm tính giai thừa

factorial (3)

n=3

factorial (2)

…

n=2

3*factorial(2)

…

factorial (1)

6

n=1

2*factorial(1)

…

2

factorial (0)

n=0

1*factorial(0)

…

1

return 1;

1

Trạng thái hệ thống khi thi hành hàm

tính giai thừa

Stack hệ thống

factorial(0)

factorial(1) factorial(1) factorial(1)

factorial(2) factorial(2) factorial(2) factorial(2) factorial(2)

factorial(3) factorial(3) factorial(3) factorial(3) factorial(3) factorial(3) factorial(3)

t

Thời gian hệ thống

Trả về từ Trả về từ

hàm hàm

Trả về từ

hàm

Trả về từ

hàm

Gọi hàm

factorial(3) factorial(2) factorial(1) factorial(0)

factorial(0) factorial(1) factorial(2) factorial(3)

Các dạng đệ qui đơn giản thường gặp (tiếp)

Đệ qui nhị phân: là đệqui trực tiếp có dạng như sau

P Ù {

If (B) thực hiện S;

else { thực hiện S* ; gọi P ; gọi P}

}

Với S , S* làcác thao tác không đệquy .

Vídụ: Hàm FIBO(n) tính sốhạng n của dãy FIBONACCI

Dạng hàm trong C++ :

int F(int n)

{ if ( n < 2 ) return 1 ;

else return (F(n -1) + F(n -2)) ; }

Các dạng đệ qui đơn giản thường gặp (tiếp)

Đệqui phi tuyến: là đệquy trực tiếp mà lời gọi đệ quy được thực hiện bên

trong vòng lặp.

P Ù {

for (<giá tri đầu> to <giátrịcuối>)

{

thực hiện S ;

if ( thỏa điều kiện dừng ) then thực hiện S*;

else gọi P;}

}

Với S , S* làcác thao tác không đệquy .

Vídụ: Cho dãy { An } xác định theo công thức truy hồi :

A0= 1 ; An = n2A0+(n-1)2A1+ . . . + 22An-2+ 12An-1

Dạng hàm đệquy tính An trên ngôn ngữC++ là:

int A( int n ) {

if ( n == 0 ) return 1 ;

else {

int tg = 0 ;

for (int i = 0 ; i<n ; i++ ) tg = tg + sqr(n-i) *A(i);

return ( tg ) ;

}

3 bước để tìm giải thuật đệqui

Thông số hóa bài toán .

Tổng quát hóa bài toán cụthểcần giải thành bài toán tổng quát (một

họcác bài toán chứa bài toán cần giải )

Tìm ra các thông sốcho bài toán tổng quát

các thông số điều khiển: các thông sốmà độlớn của chúng đặc trưng cho

độphức tạp của bài toán , vàgiảm đi qua mỗi lần gọi đệqui.

Vídụ

n trong hàm FAC(n) ;

a , b trong hàm USCLN(a,b) .

Tìm các trường hợp neo cùng giải thuật giải tương ứng

trường hợp suy biến của bài toán tổng quát

các trường hợp tương ứng với các gía trịbiên của các biến điều khiển

Vd :

FAC(1) =1

USCLN(a,0) = a

Tìm giải thuật giải trong trường hợp tổng quát bằng phân rã bài

toán theo kiểu đệquy

3 bước (tt)

Phân rã bài toán tổng quát theo phương thức

đệqui

Tìm phương án (giải thuật ) giải bài toán trong

trường hợp tổng quát phân chia nó thành các thành

phần

giải thuật không đệquy

bài toán trên nhưng có kích thước nhỏ hơn.

Vídụ

FAC(n) = n * FAC(n -1) .

Tmax(a[1:n]) = max(Tmax(a[1:(n-1)]) , a[n] )

Một số bài toán giải bằng đệqui

Bài toán tháp HàNội

Bài toán chia phần thưởng

Bài toán hoán vị

Bài toán Tháp Hà nội

Luật:

Di chuyển mỗi lần một đĩa

Không được đặt đĩa lớn lên trên đĩa nhỏ

Với chồng gồm n đĩa cần 2n-1 lần chuyển

–Giả sử thời gian để chuyển 1 đỉa là t giây thì thời gian để chuyển

xong chồng 64 đĩa sẽ là:

–T = ( 2^64-1) * t = 1.84 1019 t

–Với t = 1/100 s thì T = 5.8*109 năm = 5.8 tỷ năm .

Bài toán Tháp Hà nội

Hàm đệ qui:

Chuyển (count-1) đĩa trên đỉnh của cột start sang cột

temp

Chuyển 1 đĩa (cuối cùng) của cột start sang cột finish

Chuyển count-1 đĩa từ cột temp sang cột finish

magic

Bài toán Tháp Hà nội

Giải bài toán bằng đệqui

Thông số hóa bài toán

Xét bài toán ở mức tổng quát nhất : chuyển n (n>=0) đĩa từ

cột A sang cột C lấy cột B làm trung gian .

THN(n ,A ,B,C) -> với 64 đĩa gọi THN(64,A ,B,C)

n sẽ là thông số quyết định bài toán –n là tham số điều khiển

Trường hợp suy biến vàcách giải

Với n =1 : THN (1,A,B,C)

Giải thuật giải bt THN (1,A,B,C) là thực hiện chỉ 1 thao tác cơ

bản : Chuyển 1 đĩa từ A sang C (ký hiệu là Move (A , C) ) .

THN(1,A,B,C) ≡{ Move( A, C ) } .

THN(0, A,B,C) ≡{ φ}

Bài toán Tháp Hà nội

Phâ n rã bài toá n

Ta có thể phần rã bài toán TH N (k,A,B,C) : chuyển k đĩa từ cột A

sang cột C lấy cột B làm trung gian thành dãy tuần tự 3 công việc

sau :

Chuyển (k -1) đĩa từ cột A sang cột B lấy cột C làm trung gian :

THN (k -1,A,C,B) (bài toán THN với n = k-1,A= A , B = C , C = B )

Chuyển 1 đĩa từ cột A sang cột C : Move ( A, C ) (thao tác cơ bản ).

Chuyển (k - 1 ) đĩa từ cột B sang cột C lấy cột A làm trung gian :

THN( k -1,B,A,C) ( bài toán THN với n = k-1 , A = B , B = A , C = C ) .

Vậy giải thuật trong trường hợp tổng quát (n > 1) là:

THN(n,X,Y,Z) ≡{

THN (n -1,X,Z,Y) ;

Move ( X, Z ) ;

THN (n -1,Y,X,Z) ;

}

Bài toán Tháp Hà nội – Mã C++

void move(int count, int start, int finish, int temp) {

if (count > 0) {

move(count − 1, start, temp, finish);

cout << "Move disk " << count << " from " << start

<< " to " << finish << "." << endl;

move(count − 1, temp, finish, start);

}

Bài giảng Kỹ thuật lập trình - Chương 4, Phần 1: Một số cấu trúc dữ liệu và giải thuật căn bản - Vũ Đức Vượng