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

Chương 4

Một số cấu trúc dữ liệu và

giải thuật căn bản

Phần 4.1 Đệ qui (4LT – 2BT)

SE-SoICT

KTLT 4-1.1

Last update 9-2010

1. Đệ 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

Last update 8-2010

SE-SoICT

KTLT 4-1.2

Khái niệm Đ/n đệ qui

Một mô tả/định nghĩa về một đối tượng gọi là đệ

qui nếu trong mô tả/định nghĩa đó ta lại sử dụng

chí nh đối tượng này.

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

Mô tả đệ qui 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ả đệ qui 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ả đệ qui 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ẹ

Last update 8-2010

SE-SoICT

KTLT 4-1.3

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ả đệ qui 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.

Last update 8-2010

SE-SoICT

KTLT 4-1.4

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

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

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

1,…

Phần qui 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

Last update 8-2010

SE-SoICT

KTLT 4-1.5

Giải thuật đệ qui

Nếu ta có 1 lời giải S cho bài toán P, ta lại sử dụng lời

giải ấy cho bài toán P’ giống P nhưng kích cỡ nhỏ hơn

thì lời giải S đó gọi là lời giải đệ qui.

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 P[ S , P ]

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

Chương trình con đệ qui: Khi ta cài đặt giải thuật đệ qui,

ta có chương trình đệ qui (tự nó gọi lại chính nó: P

=>P’)

–Hàm đệ qui

–Thủ tục đệ qui

Last update 8-2010

SE-SoICT

KTLT 4-1.6

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 đệ qui tính FIBO ( n ) là:

FIBO(n)

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

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

Last update 8-2010

SE-SoICT

KTLT 4-1.7

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 đệqui .

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

}

Last update 8-2010

SE-SoICT

KTLT 4-1.8

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

Last update 8-2010

SE-SoICT

KTLT 4-1.9

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)

Last update 8-2010

SE-SoICT

KTLT 4-1.10

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 đệ qui .

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

Last update 8-2010

SE-SoICT

KTLT 4-1.11

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

Đệqui phi tuyến: là đệ qui trực tiếp mà lời gọi đệ qui đượ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 đệqui .

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 đệ qui 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 ) ;

}

Last update 8-2010

SE-SoICT

KTLT 4-1.12

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

Tham 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

hoặc các bài toán chứa bài toán cần giải )

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

Các tham số điều khiển: các tham 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 (“Trivial”) 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,b) = b nếu a chia hết cho b

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 đệ qui.

Last update 8-2010

SE-SoICT

KTLT 4-1.13

3 bước (tiếp)

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

đệ qui

Phân rã bài toán thành các bài toán giống BT ban

đầu (ĐQ) song có kích thước nhỏ hơn và các BT

khác (có thể có hoặc không). Đây là trường hợp đặc

biệt của phương pháp Thiết kế Top-Down!

Vídụ

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

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

Last update 8-2010

SE-SoICT

KTLT 4-1.14

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ị

Last update 8-2010

SE-SoICT

KTLT 4-1.15

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 2ⁿ-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⁶⁴-1) * t = 1.84 1019 t

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

Last update 8-2010

SE-SoICT

KTLT 4-1.16

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

Hàm đệ qui:

Chuyển (n-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 n-1 đĩa từ cột temp sang cột finish

magic

Last update 8-2010

SE-SoICT

KTLT 4-1.17

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 B lấy cột C 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 B (ký hiệu là Move (A , B) ) .

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

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

Last update 8-2010

SE-SoICT

KTLT 4-1.18

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 B lấy cột C 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 C lấy cột B 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 B : Move ( A, B ) (thao tác cơ bản ).

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

THN( k -1,C,B,A) ( 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,A,B,C)

{

THN (n -1,A,C,B) ;

Move ( A, B ) ;

THN (n -1,C,B,A) ;

}

Last update 8-2010

SE-SoICT

KTLT 4-1.19

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

}

Last update 8-2010

SE-SoICT

KTLT 4-1.20

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 - Lương Mạnh Bá