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á

Last update 9-2010 SE-SoICT KTLT 4-1. 1 Chương 4Mộ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) Last update 8-2010 SE-SoICT KTLT 4-1. 2 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. 3 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. 4 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) return 1; else 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. 5 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. 6 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. 7 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. 8 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. 9 Thi hành hàm tính giai thừa n=2 2*factorial(1) factorial (2) n=1 1*factorial(0) factorial (1) n=0 return 1; factorial (0) 1 1 6 2 n=3 3*factorial(2) factorial (3) Last update 8-2010 SE-SoICT KTLT 4-1. 10 Trạng thái hệ thống khi thi hành hàm tính giai thừa factorial(3) factorial(3) factorial(2) factorial(3) factorial(2) factorial(1) factorial(3) factorial(2) factorial(1) factorial(0) factorial(3) factorial(2) factorial(1) factorial(3) factorial(2) factorial(3) t Gọi hàm factorial(3) Gọi hàm factorial(2) Gọi hàm factorial(1) Gọi hàm factorial(0) Trả về từ hàm factorial(0) Trả về từ hàm factorial(1) Trả về từ hàm factorial(2) Trả về từ hàm factorial(3) Stack hệ thống Thời gian hệ thống t 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 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. 12 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 ( to ) { 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. 13 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. 14 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. 15 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. 16 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 n -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 . Last update 8-2010 SE-SoICT KTLT 4-1. 17 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. 18 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. 19 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. 20 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. 21 Last update 8-2010 SE-SoICT KTLT 4-1. 22 Bài toán chia phần thưởng Có 100 phần thưởng đem chia cho 12 học sinh giỏi đã được xếp hạng . Có bao nhiêu cách khác nhau để thực hiện cách chia? Tìm giải thuật giải bài toàn bằng phương pháp đệquy. Last update 8-2010 SE-SoICT KTLT 4-1. 23 Bài toán chia phần thưởng (tự đọc) Giải bài toán bằng đệ qui Nhìn góc độ bài toán tổng quát: Tìm số cách chia m vật (phần thưởng ) cho n đối tượng (học sinh ) có thứ tự. PART(m ,n ) N đối tượng đã được sắp xếp 1,2,,n Si là số phần thưởng mà i nhận được Si>= 0 S1>= S2>= >= Sn. S1+ S2+ ...+ Sn= m Vídụ: Với m = 5 , n = 3 ta có 5 cách chia sau : 5 0 0 ,4 1 0, 3 2 0 ,3 1 1 ,2 2 1 Tức là PART(5,3 ) = 5 Last update 8-2010 SE-SoICT KTLT 4-1. 24 Các trường hợp suy biến m = 0 : mọi học sinh đều nhận được 0 phần thưởng . PART(0 , n ) = 1 với mọi n n = 0 , m 0 : không có cách chia PART(m , 0 ) = 0 với mọi m 0 . Phân rã bài toán trong trường hợp tổng quát m < n : n -m học sinh xếp cuối sẽ luôn không nhận được gì cả trong mọi cách chia . Vậy: n > m thìPART(m , n ) = PART(m , m ) m>=n: là tổng Học sinh cuối cùng không có phần thưởng PART(m , n -1 ) Học sinh cuối cùng có ít nhất 1 PART(m -n , n ) Vậy: m > n => PART(m , n ) = PART(m , n -1 ) + PART(m -n , n ) Last update 8-2010 SE-SoICT KTLT 4-1. 25 Dạng hàm PART trong NN LT C++ int PART( int m , int n ) { if ((m == 0 ) || (n == 0) ) return 1 ; else if(m < n ) retrun ( PART(m , m )) ; else return ( PART(m , n -1 ) + PART( m -n , n ) ) ; } Last update 8-2010 SE-SoICT KTLT 4-1. 26 Bài toán tìm tất cả hoán vị của một dãy các phần tử (giảng lướt) Thông số hóa bài toán. Gọi HV(v, m ) v : array[1 . . N ] of T m :integer ; m <= N T là một kiểu dữ liệu Vídụ: N = 4 , A[1] = 1 , A[2] = 2 , A[3] = 3 , A[4] = 4 thì lời gọi HV(A ,3 ) xuất tất cả hoán vị của A có được bằng cách hoán vị 3 phần tử đầu (có 6 h vị) : 1 2 3 4 1 3 2 4 3 2 1 4 2 1 3 4 3 1 2 4 2 3 1 4 Trường hợp neo Với m = 1 : HV(v,1): xuất v HV(v,1) ≡Display(v) //for (k= 1 to N do) Display(v[k]) Last update 8-2010 SE-SoICT KTLT 4-1. 27 Phân rã bài toán Giữ nguyên các phần tử cuối V[m] , . . . ,V[N] hoán vị m-1 phần tử đầu gọi đệquy HV(V ,m -1) Đổi chổ V[m] cho V[m-1] ,giữ nguyên các phần tử cuối V[m],... ,V[N] hoán vị m-1 phần tử đầu gọi đệquy HV(V ,m -1) Đổi chổV[m] cho V[m-2] ,giữ nguyên các phần tử cuối V[m],. ,V[N] hoán vị m-1 phần tử đầu gọi đệquy HV(V ,m -1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . .. . . . . . . . . . . Đổi chổ V[m] cho V[2] ,giữ nguyên các phần tử cuối V[m], . .. ,V[N] hoán vị m-1 phần tử đầu gọi đệquy HV(V ,m -1) . - Đổi chổV[m] cho V[1] ,giữ nguyên các phần tử cuối V[m], . . . ,V[N] hoán vị m-1 phần tử đầu gọi đệquy HV(V ,m -1) . Last update 8-2010 SE-SoICT KTLT 4-1. 28 Bài toán tìm tất cả hoán vị của một dãy các phần tử HV(V,m) ≡{ SWAP( V[m],V[m] ) ; HV(V,m –1) ; SWAP( V[m],v[m-1] ) ; HV(V,m –1) ; SWAP( V[m],v[m-2 ] ) ; HV(V,m –1) ; . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . SWAP (V[m],v[2] ) ; HV(V,m –1) ; SWAP( V[m],v[1] ) ; HV(V,m –1) ; } SWAP(x , y ) là thủ tục hoán đổi giá trị của 2 đối tượng dữ liệu x ,y ) Vậy :HV(V , m ) ≡ for (k = m;k>0; k--) { SWAP( V[m], V[k] ) ; HV(V,m –1) ; } ; Last update 8-2010 SE-SoICT KTLT 4-1. 29 const size = Val ; // Val là hằng gía trị typedef typebase vector[size] ; // typebase là một kiểu dữ liệu có thứ tự void Swap( typebase &x , typebase &y) { typebase t ; t = x ; x = y ; y = t ; } void print( const vector &A) { for(int j= 0 ; j <size ; j++ ) cout<< A[j] ; cout << “.”; } void HV( const vector &V , int m) { if (m == 1 ) print( V ); else for(int k = m-1 ; k > = 0 ; k--) { swap(V[m-1] ,V[k] ) ; HV(V,m-1) ; } } Last update 8-2010 SE-SoICT KTLT 4-1. 30 #include #include #include #define STOP 27 // phim esc const MAX =100; int a[MAX]; char b[MAX];// mang danh dau int shv, n; Hoanvi (int k) { int i,j; for (i=1;i<=n;i++) if (b[i]) { a[k] = i; b[i] = 0; if (k==n) { // Da chon du n so => 1 hoan vi shv ++; printf("\n Hoan vi %2d la : ", shv); for (j=1; j <=n;j++) printf("%d", a[j]); } else // goi tang len 1 so Hoanvi (k+1); b[i] = 1; } return 0; } Lời giảiĐệ qui khác của bài toán Hoán vị (giảng cho SV) Last update 8-2010 SE-SoICT KTLT 4-1. 31 main () { char ch; int i; do { // danh dau mang b for (i=1;i <= MAX;i++) b[i] = 1; clrscr(); printf("\n n="); scanf("%d", &n); shv = 0; if ( n > 0) Hoanvi(1); printf("\n Lam tiep :Y Thoat: ESC>"); ch = getch(); } while (ch !=STOP); } Lời giả không đệ qui của bài toán Hoán vị (tiếp) Last update 8-2010 SE-SoICT KTLT 4-1. 32 KHỬ ĐỆ QUI 1 Cơ chế thực hiện đệ qui 2 Tổng quan về khử đệ qui 3 Các trường hợp khử đệ qui đơn giản Last update 8-2010 SE-SoICT KTLT 4-1. 33 Cơ chế thực hiện đệ qui • Trạng thái của tiến trình xử lý một giải thuật: nội dung các biến và lệnh cần thực hiện kế tiếp. • Với tiến trình xử lý một giải thuật đệ qui ở từng thời điểm thực hiện, cần lưu trữ cả các trạng thái xử lý đang còn dang dở . Last update 8-2010 SE-SoICT KTLT 4-1. 34 Xét giải thuật giai thừa –Giải thuật FAC ( n ) ≡if(n = 0 ) retrun 1; else retrun ( n * FAC (n –1)); –Sơ đồ thực hiện Last update 8-2010 SE-SoICT KTLT 4-1. 35 Xét thủ tục đệ qui tháp HàNội THN (n , X , Y , Z) Chuyển n đĩa từ X->Y lấy Z là trung gian – Giải thuật : THN (n, X ,Y , Z) { if (n > 0 ) { THN(n-1,X ,Z ,Y) ; Move(X, Y) THN(n-1,Z,Y,X) ; } } – Sơ đồ thực hiện THN(3,A,B,C) Last update 8-2010 SE-SoICT KTLT 4-1. 36 Last update 8-2010 SE-SoICT KTLT 4-1. 37 Nhận xét –Lời gọi đệ qui sinh ra lời gọi đệ qui mới cho đến khi gặp trường hợp suy biến (neo ) –Ở mỗi lần gọi phải lưu trữ thông tin trạng thái con dang dở của tiến trình xử lý ở thời điểm gọi. Số trạng thái này bằng số lần gọi chưa được hoàn tất . –Khi thực hiện xong (hoàn tất) một lần gọi, cần khôi phục lại toàn bộ thông tin trạng thái trước khi gọi . –Lệnh gọi cuối cùng (ứng với trương hợp neo) sẽ được hoàn tất đầu tiên. –Cấu trúc dữ liệu sử dụng: cấu trúc Stack (LIFO) Last update 8-2010 SE-SoICT KTLT 4-1. 38 Tạo ngăn xếp S –Thủ tục Creatstack(S) : Tạo S rỗng . –Thủ tục Push(x,S) : thêm x vào đỉnh stack S •( x là dữ liệu kiểu đơn giản giản hoặc có cấu trúc ) –Thủ tục Pop(x,S) : Lấy giá trị đang lưu ở đỉnh S •Lưu trữ vào x •Loại bỏ giá trị này khỏi S ( lùi đỉnh S xuống một mức ) –Hàm Empty(S): (kiểu boolean) Kiểm tra tính rỗng của S : cho giá trị đúng nếu S rỗng , sai nếu không. Last update 8-2010 SE-SoICT KTLT 4-1. 39 Cai dat stack : #define MAX 100 typedef struct { int top; int nodes(MAX); } stack; int Empty(stack *ps) { if (ps->top == - 1) return (true); return(false); } Last update 8-2010 SE-SoICT KTLT 4-1. 40 void Push(stack *ps , int x) { if (ps->top ==MAX -1) { printf(“\n stack full”); return; } ps->top +=1 ; ps->nodes[ps->top] =x; } int Pop(stack *ps) { if(Empty(ps) { printf(“\n stack is empty”); return (0); } return(ps->nodes[ps->top--]); } Last update 8-2010 SE-SoICT KTLT 4-1. 41 Tổng quan về khử đệ qui •Ưu điểm : gọn gàng, dễ hiểu ,dễ viết code •Nhược điểm: tốn không gian nhớ và thời gian xử lý. •Mọi giải thuật đệ qui đều có thể thay thế bằng một giải thuật không đệ qui. •Sơ đồ xây dựng chương trình cho một bài toán khó khi ta không tìm được giải thuật không đệ qui thường là: i) Dùng quan niệm đệ qui để tìm giải thuật cho bài toán . ii) Mã hóa giải thuật đệ qui . ii) Khử đệ qui để có được một chương trình không đệ qui . •Tuy nhiên : khử đệ qui không phải bao giờ cũng dễ => trong nhiều trường hợp ta cũng phải chấp nhận sử dụng chương trình đệ qui. Last update 8-2010 SE-SoICT KTLT 4-1. 42 1.Khử đệ qui bằng vòng lặp A. Hàm tính gía trị của dãy dữ liệu mô tả bằng hồi qui •Ý tưởng –Xét một vòng lặp trong đó sử dụng 1 tập hợp biến W = (V , U ) i) Tập hợp U các biến bị thay đổi ii) V là các biến còn lại. –Dạng tổng quát của vòng lặp là: W = Wo ; { Wo = ( Uo,Vo) } while C(U) do U := g(W) –Gọi U o là trạng thái của U ngay trước vòng lặp –U k với k >0 là trạng thái của U sau lần lặp thứ k (giả sử còn lặp đến lần k ) Uo mang các giá trị được gán ban đầu U k = g(W) = g(U k-1 , V o ) = f(U k-1 ) với k = 1 .. n Với n là lần lặp cuối cùng , tức C(U k ) đúng với mọi k < n , C(U n ) sai –Sau vòng lặp W mang nội dung (U n ,V o ) . Last update 8-2010 SE-SoICT KTLT 4-1. 43 Giải thuât hồi qui thường gặp f(n) = C khi n = n o ( C là một hằng ) = g(n,f(n -1)) khi n > n o •Vídụ: -Hàm giai thừa FAC (n) = n ! = 1 khi n = 0 = n * FAC(n -1) khi n > 0 –Tổng n số đầu tiên của dãy đan dấu sau : Sn = 1 -3 + 5 -7 .. + (-1)n+1 * (2n-1) 1 khi k =1 S(k-1) + (-1)k+1*(2*k-1) với k > 1 S(k) = Last update 8-2010 SE-SoICT KTLT 4-1. 44 .Giải thuật đệqui tính giá trị f(n) f(n) = if(n = n o ) return C ; else return (g(n,f(n -1)) ; •Giải thuật lặp tính giá tri f(n) k := n o ; F := C ; { F = f(n o ) } while( k < n ) { k := k +1 ; F := g(k,F ) ; } return F; •Trong trường hợp này : W = U = ( k ,F ) Wo = Uo = ( no,C ) C(U) = ( k < n) f(W) = f(U) = f(k,F) = (k+1,g(k,F))) Last update 8-2010 SE-SoICT KTLT 4-1. 45 Khử đệ qui với hàm tính giai thừa long int FAC ( int n ) { int k = 0 ; long int F = 1 ; while ( k < n ) F = ++k * F ; return (F) ; } Với hàm tính S(n) int S ( int n ) { int k = 1 , tg = 1 ; while ( k < n ) { k ++ ; if (k%2) tg + = 2 * k +1 ; else tg -= 2 * k + 1 ; } return ( tg ) ; } Last update 8-2010 SE-SoICT KTLT 4-1. 46 2.Các thủ tục đệ qui dạng đệ qui đuôi •Xét thủ tục P dạng : P(X) ≡ if B(X) then D(X) else { A(X) ; P(f(X)) ; } •Trong đó: X là tập biến (một hoặc một bộ nhiều biến ). •P(X) là thủ tục đệ qui phụ thuộc X •A(X) ; D(X) là các thao tác không đệ qui •f(X) là hàm biến đổi X Last update 8-2010 SE-SoICT KTLT 4-1. 47 •Xét qúa trình thi hành P(X) : –gọi Po là lần gọi P thứ 0 (đầu tiên ) P(X) –P1 là lần gọi P thứ1 (lần 2) P(f(X)) –Pi là lần gọi P thứ i ( lần i + 1) P(f(f(...f(X)...) –( P(fi(X)) hợp i lần hàm f ) •Gọi Pi nếu B(fi(X)) –(false) { A và gọi Pi+1 } –(true) { D } •Giả sử P được gọi đúng n +1 lần . Khi đó ở trong lần gọi cuối cùng (thứ n ) Pn thì B(fn(X)) =true , lệnh D được thi hành và chấm dứt thao tác gọi thủ tục P . Sơ đồ thực hiện giải thuật trên bằng vòng lặp: while ( ! B(X) ) { A(X) ; X = f(X) ; } D(X) ; Last update 8-2010 SE-SoICT KTLT 4-1. 48 Vídụ: Để đổi 1 số nguyên không âm Y ở cơ số10 sang dạng cơ số k ( 2 <= k <= 9 ) –Dùng mảng A [n] –Convert(x,m) để tạo dãy gía trị: A[0] , A[1] , . . . , A[m] –Giải thuật Convert(n,m) ≡if n != 0 { A[m] = n % k ; Convert(n/k , m -1) ; } –Trong ví dụ này ta có •X là( n, m ) ; •B(X) là biểu thức boolean not( n 0 ) •A(X) là lệnh gán A[m] := n%k ; •f(X) là hàm f(n,m ) = ( n/k , m -1 ) ; •D(X) là lệnh rỗng –Đoan lệnh lặp tương ứng với thủ tục Convert(x,m) là: while (n != 0) { A[m] = n % k ; //A(X) n = n / k ; // X := f(X) m = m -1 ; } Last update 8-2010 SE-SoICT KTLT 4-1. 49 Vídụ: Tìm ước số chung lớn nhất của hai số • Giải thuật đệ qui USCLN(m , n , var us) ≡if ( n = 0 ) then us := m else USCLN(n , m mod n , us ) ; => Cài đặt trên c unsigned USCLN2(int a, int b) { // Dùng đệ qui theo định nghĩa của USCLN if ((a % b)== 0) return b; else return USCLN2(b, a % b); } Last update 8-2010 SE-SoICT KTLT 4-1. 50 Cài đặt không đệ qui unsigned USCLN1(int a, int b) {// Dùng vòng lặp theo thuật toán Ơclide while (a !=b) { if (a > b) a-=b; else b-=a; } return b; } Last update 8-2010 SE-SoICT KTLT 4-1. 51 3 Khử đệ qui bằng Stack – Để thực hiện một chương trình con đệ qui thì hệ thống phải tổ chức vùng lưu trữ thỏa qui tắc LIFO (Stack).=> So sánh với gọi CTC thông thường. – Vậy ta chủ động tạo ra cấu trúc dữ liệu stack đặc dụng cho từng chương trình con đệ qui cụ thể phù hợp cơ chế LIFO. Last update 8-2010 SE-SoICT KTLT 4-1. 52 A. Đệ qui chỉ có một lệnh gọi trực tiếp •Đệ qui có dạng sau: P(X) ≡ if C(X) D(X) else { A(X) ; P(f(X)) ; B(X) ; } X là một biến đơn hoặc biến véc tơ. C(X) là một biểu thức boolean của X . A(X) , B(X) , D(X):không đệ qui f(X) là hàm của X (hàm đơn điệu giảm) Last update 8-2010 SE-SoICT KTLT 4-1. 53 Giải thuật thực hiện P(X) với việc sử dụng Stack có dạng : P(X) ≡{ Create_Stack (S) ; ( tạo stack S ) while(not(C(X)) { A(X) ; Push(S,X) ; X := f(X) ; } D(X) ; while (not Empty(S)) { POP(S,X) ; B(X) ; } } Last update 8-2010 SE-SoICT KTLT 4-1. 54 •Ví dụ:Thủ tục đệ qui chuyển biểu diễn số từ cơ số thập phân sang nhị phân có dạng : Binary(m) ≡if ( m > 0 ) { Binary( m div 2 ) ; write( m mod 2 ) ; } •Trong trường hợp này : X là m . P(X) là Binary(m) . A(X) ; D(X) là lệnh rỗng . B(X) là lệnh Write(m mod 2 ) ; C(X) là ( m <= 0 ) . f(X) = f(m) = m div 2 Last update 8-2010 SE-SoICT KTLT 4-1. 55 Giái thuật thực hiện Binary(m) không đệ qui là: Binary (m ) { Create_Stack (S) ; while ( m > 0 ) { sdu := m mod 2 ; Push(S,sdu) ; m := m div 2 ; } while ( not Empty(S)) { POP(S,sdu) ; Display(sdu) ; } } Last update 8-2010 SE-SoICT KTLT 4-1. 56 B. Thủ tục đệ qui với hai lần gọi đệ qui –Đệ qui có dạng sau P(X) ≡if C(X) D(X) ; else { A(X) ; P(f(X)) ; B(X) ; P(g(X)) ; } -Thuật toán khử đệ qui tương ứng với thủ tục đệquy P(X) là:{ Creat_Stack (S) : Push (S, (X,1)) ; do { while ( not C(X) ) { A(X) ; Push (S, (X,2)) ; X := f(X) ; } D(X) ; POP (S, (X,k)) ; if ( k 1) { B(X) ; X := g(X) ; } } while ( k = 1 ) ; } Last update 8-2010 SE-SoICT KTLT 4-1. 57 Khử đệ qui thủ tục Tháp Hà Nội . •Dạng đệ qui void THN(n , X , Y, Z ) { if( n > 0 ) { THN ( n -1 , X , Z , Y ) ; Move ( X , Y ) ; THN ( n -1 , Z , Y , X ) ; } } Last update 8-2010 SE-SoICT KTLT 4-1. 58 •Giải thuật không đệ qui tương đương là: THN (n, X, Y, Z) { Creat_Stack (S) ; Push (S ,(n,X,Y,Z,1)) ; do while ( n > 0 ) { Push (S ,(n,X,Y,Z,2)) ; n := n -1 ; Swap (Y,Z ) ; } POP (S,(n,X,Y,Z,k)) ; if ( k 1 ) { Move (X ,Z ) ; n := n -1 ; Swap (X ,Y ) ; } } while ( k = 1 ) ; } Last update 8-2010 SE-SoICT KTLT 4-1. 59 Bài tập Liệt kê mọi tập con củaa tập 1,2,3,n, với n nhập từ bàn phím Liệt kê mọi hoán vị của Từ COMPUTER ( mở rộng, 1 từ bất kỳ nhập từ bàn phím ) Một nhà thám hiểm đem theo 1 cái túi với trọng lượng tối đa là B. Có n đò vật cần mang theo, mỗi đò vật có trọng lượng a i và giá trị c i tương ứng.Hãy viết CT tìm cách bỏ vào túi các đò vật sao cho giá trị sử dụng là lớn nhất. Bài toán Người du lịch : 1 người du lịch muốn đi thăm các thành phố khác nhau. Xuất phát tại 1 thành phố nào đó, họ muốn lần lượt qua tất cả các thành phố ( 1 lân) rồi trở lại thành phố ban đầu.Biết chi phi đi lại từ thành phố I đến J là Cij . Hãy tìm hành trình với tổng chi phí thấp nhất Liệt kê tất cả các cách sắp xếp N con hậu trên bàn cờ 8 x 8 sao cho chúng không ăn được nhau. Last update 8-2010 SE-SoICT KTLT 4-1. 60 Bài toán 8 con Hậu – Giải thuật Algorithm Solve Input trạng thái bàn cờ Output 1. if trạng thái bàn cờ chứa đủ 8 con hậu 1.1. In trạng thái này ra màn hình 2. else 2.1. for mỗi ô trên bàn cờ mà còn an toàn 2.1.1. thêm một con hậu vào ô này 2.1.2. dùng lại giải thuật Solve với trạng thái mới 2.1.3. bỏ con hậu ra khỏi ô này End Solve Vét cạn Last update 8-2010 SE-SoICT KTLT 4-1. 61 Bài toán 8 con Hậu – Thiết kế phương thức Last update 8-2010 SE-SoICT KTLT 4-1. 62 Bài toán 8 con Hậu – Thiết kế dữ liệu đơn giản const int max_board = 30 ; class Queens { public: Queens( int size) ; bool is_solved( ) const; void print( ) const; bool unguarded( int col) const; void insert( int col) ; void remove( int col) ; int board_size ; // dimension of board = maximum number of queens private: int count ; // current number of queens = first unoccupied row bool queen_square[max_board][max_board] ; } ; Last update 8-2010 SE-SoICT KTLT 4-1. 63 Bài toán 8 con Hậu – Mã C++ void Queens :: insert( int col) { queen_square[count++][col] = true; } bool Queens :: unguarded( int col) const { int i ; bool ok = true; for (i = 0 ; ok && i < count ; i++) //kiểm tra tại một cột ok = !queen_square[i][col] ; //kiểm tra trên đường chéo lên for (i = 1 ; ok && count − i >= 0 && col − i >= 0 ; i++) ok = !queen_square[count − i][col − i] ; //kiểm tra trên đường chéo xuống for (i = 1 ; ok && count − i >= 0 && col + i < board_size ; i++) ok = !queen_square[count − i][col + i] ; return ok ; } Last update 8-2010 SE-SoICT KTLT 4-1. 64 Bài toán 8 con Hậu – Góc nhìn khác Last update 8-2010 SE-SoICT KTLT 4-1. 65 Bài toán 8 con Hậu – Thiết kế mới const int max_board = 30 ; class Queens { public: Queens( int size) ; bool is_solved( ) const; void print( ) const; bool unguarded( int col) const; void insert( int col) ; void remove( int col) ; int board size ; private: int count ; bool col_free[max board] ; bool upward_free[2 * max board − 1] ; bool downward_free[2 * max board − 1] ; int queen_in_row[max board] ; // column number of queen in each row } ; Last update 8-2010 SE-SoICT KTLT 4-1. 66 Bài toán 8 con Hậu – Mã C++ mới Queens :: Queens( int size) { board size = size ; count = 0 ; for ( int i = 0 ; i < board_size ; i++) col_free[i] = true; for ( int j = 0 ; j < (2 * board_size − 1) ; j++) upward_free[j] = true; for ( int k = 0 ; k < (2 * board_size − 1) ; k++) downward_free[k] = true; } void Queens :: insert( int col) { queen_in_row[count] = col ; col_free[col] = false; upward_free[count + col] = false; downward_free[count − col + board size − 1] = false; count++ ; }