Bài giảng 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 - Vũ Đức Vượng

Nội dung text: Bài giảng 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 - Vũ Đức Vượng

1. 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
2. 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ả đệ 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.
3. 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
4. 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 )) ; }
5. 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ừ Trả về từ Trả về từ Gọi hàm Gọi hàm Gọi hàm Gọi hàm hàm hàm hàm hàm factorial(3) factorial(2) factorial(1) factorial(0) factorial(0) factorial(1) factorial(2) factorial(3) t
6. 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 ( 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 đệ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 ) ; }
7. 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] )
8. 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 .
9. 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) ≡{ φ}
10. 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); } }
11. Bài toán Tháp Hà nội – Cây đệ qui
12. Bài toán chia phần thưởng 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
13. 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 ) ) ; }
14. 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) .
15. 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 = 0 ; k ) { swap(V[m-1] ,V[k] ) ; HV(V,m-1) ; } }
16. 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ở
17. Xét thủ tục đệ quy tháp HàNội THN (n , X , Y , Z) –Giải thuật THN (n : integer ; X ,Y , Z : char) ≡{ if (n > 0 ) then { THN(n-1,X ,Z ,Y) ; Move(X, Z) ; THN(n-1,Y,X,Z) ;} } –Sơ đồ thực hiện THN(3,A,B,C)
18. Nhận xét –Lời gọi đệquy sinh ra lời gọi đệquy 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 cho phép lưu trữdãy thông tin thỏa 3 yêu cầu trên là cấu trúc lưữ thỏa mãn LIFO (Last In Firt Out => do chinh la cau truc Stack)
19. 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); }
20. Tổng quan về khử đệqui •Uu diem : gọn gàng, dễ hiểu ,dễ viet code •Nhưoc diem :tốn không gian nhớ và thời gian xử lý. •Mọi giải thuật đệ quy đều có thể thay thế bằng một giải thuật không đệ quy. •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 đệ quy thường là: –Dùng quan niệm đệ quy để tìm giải thuật cho bài toán . –Mã hóa giải thuật đệ quy . –Khử đệ quy để có được một chương trình không đệquy . •Tuy nhiên : khử đệ quy 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 đệquy
21. Giải thuât hồi qui thường gặp f(n) = C khi n = no ( C là một hằng ) = g(n,f(n -1)) khi n > no •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) S(k) = 1 khi k =1 = S(k-1) + (-1)k+1*(2*k-1) với k > 1
22. 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 ) ; }
23. •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) ;
24. 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 ) ; – X là( m , n , us ) P(X) là USCLN(m ,n ,us) B(X) là n = 0 D(X) là lệnh gán us := m A(X) là lệnh rỗng f(X ) là f(m,n,us) = ( n , m mod n ,us )
25. 3 Khử đệ qui bang Stack –Để thực hiện một chương trình con đệ quy thì hệ thống phải tổ chức vùng lưu trữ thỏa quy tắc LIFO (vùng Stack). –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 đệ quy cụ thể.
26. Giải thuật thực hiện P(X) với việc sử dụng Stack có dạng : P(X) ≡{ Creat_Stack (S) ; ( tạo stack S ) While(not(C(X)) do begin A(X) ; Push(S,X) ; ( cất gía trị X vào stack S ) X := f(X) ; end ; D(X) ; While(not(EmptyS(S))) do begin POP(S,X) ; ( lấy dữ liệu từ S ) B(X) ; end ; }
27. Giái thuật thực hiện Binary(m) không đệ quy là: Binary (m ) ≡{ Creat_Stack (S) ; While ( m > 0 ) do begin sdu := m mod 2 ; Push(S,sdu) ; m := m div 2 ; end; While( not(EmptyS(S)) do begin POP(S,sdu) ; Write(sdu) ; end; }
28. Khử đệ quy thủ tục Tháp Hà Nội . •Dạng đệ qui THN(n , X , Y, Z ) ≡if( n > 0 ) then begin THN ( n -1 , X , Z , Y ) ; Move ( X , Z ) ; THN ( n -1 , Y , X , Z ) ; end ;
29. Bài tập Liệt kê mọi tập con cua 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 ai và giá trị ci 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ơ N x N sao cho chúng không ăn được nhau
30. Cây thi hành và stack hệ thống Cây thi hành
31. Khử đệ qui đuôi hàm giai thừa Giải thuật: product=1 for (int count=1; count < n; count++) product *= count;
32. Dãy số Fibonacci – Cây thi hành Đã tính rồi
33. Bài toán 8 con Hậu
34. 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
35. 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]; };
36. Bài toán 8 con Hậu – Góc nhìn khác
37. 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++; }