Ctdl C052. Kh叩i ni畛m 畛 qui Kh叩i ni畛m (畛nh ngh挑a) 畛 qui c坦 d湛ng l畉i ch鱈nh n坦. V鱈 d畛: giai th畛a c畛a n l 1 n畉u n l 0 ho畉c l n nh但n cho giai th畛a c畛a n-1 n畉u n > 0 Qu叩 tr狸nh 畛 qui g畛m 2 ph畉n: Tr動畛ng h畛p c董 s畛 (base case) Tr動畛ng h畛p 畛 qui: c畛 g畉ng ti畉n v畛 tr動畛ng h畛p c董 s畛 V鱈 d畛 tr棚n: Giai th畛a c畛a n l 1 n畉u n l 0 Giai th畛a c畛a n l n * (giai th畛a c畛a n-1) n畉u n>0 3. T鱈nh giai th畛a 畛nh ngh挑a kh担ng 畛 qui: 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)); } 4. Thi hnh hm t鱈nh giai th畛a 1 1 6 2 n=2 2*factorial(1) factorial (2) n=1 1*factorial(0) factorial (1) n=0 return 1; factorial (0) n=3 3*factorial(2) factorial (3) 5. Tr畉ng th叩i h畛 th畛ng khi thi hnh hm 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 hm factorial(3) G畛i hm factorial(2) G畛i hm factorial(1) G畛i hm factorial(0) Tr畉 v畛 t畛 hm factorial(0) Tr畉 v畛 t畛 hm factorial(1) Tr畉 v畛 t畛 hm factorial(2) Tr畉 v畛 t畛 hm factorial(3) Stack h畛 th畛ng Th畛i gian h畛 th畛ng t 6. Bi 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畛 7. Bi to叩n Th叩p H n畛i Thi畉t k畉 hm Hm 畛 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 8. Bi 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. Thi畉t k畉 c叩c gi畉i thu畉t 畛 qui T狸m b動畛c ch鱈nh y畉u (b動畛c 畛 qui) T狸m qui t畉c ng畛ng Ph叩c th畉o gi畉i thu畉t D湛ng c但u l畛nh if 畛 l畛a ch畛n tr動畛ng h畛p. Ki畛m tra i畛u ki畛n ng畛ng 畉m b畉o l gi畉i thu畉t lu担n d畛ng l畉i. V畉 c但y 畛 qui Chi畛u cao c但y 畉nh h動畛ng l動畛ng b畛 nh畛 c畉n thi畉t. S畛 n炭t l s畛 l畉n b動畛c ch鱈nh y畉u 動畛c thi hnh. 13. 畛 qui u担i (tail recursion) 畛nh ngh挑a: c但u l畛nh th畛c thi cu畛i c湛ng l l畛i g畛i 畛 qui 畉n ch鱈nh n坦. Kh畛: chuy畛n thnh v嘆ng l畉p. 14. Kh畛 畛 qui u担i hm giai th畛a Gi畉i thu畉t: product=1 for ( int count=1; count < n; count++) product *= count; 15. D達y s畛 Fibonacci 畛nh ngh挑a: F 0 = 0 F 1 = 1 F n = F n-1 + F n-2 khi n>2 V鱈 d畛: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, Hm 畛 qui: int fibonacci ( int n) { if (n<=0) return 0; if (n==1) return 1; else return (fibonacci(n-1) + fibonacci(n-2)); } 17. D達y s畛 Fibonacci Kh畛 畛 qui Nguy棚n t畉c: D湛ng bi畉n l動u tr畛 gi叩 tr畛 達 t鱈nh c畛a F n-2 D湛ng bi畉n l動u tr畛 gi叩 tr畛 達 t鱈nh c畛a F n-1 T鱈nh F n = F n-1 + F n-2 v l動u l畉i 畛 d湛ng cho l畉n sau Gi畉i thu畉t: int Fn2=0, Fn1=1, Fn; for ( int i = 2; i <= n; i++) { Fn = Fn1 + Fn2; Fn2 = Fn1; Fn1 = Fn; } 20. Bi to叩n 8 con H畉u Gi畉i thu畉t Algorithm Solve Input tr畉ng th叩i bn c畛 Output 1. if tr畉ng th叩i bn c畛 ch畛a 畛 8 con h畉u 1.1. In tr畉ng th叩i ny ra mn h狸nh 2. else 2.1. for m畛i 担 tr棚n bn c畛 m c嘆n an ton 2.1.1. th棚m m畛t con h畉u vo 担 ny 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 担 ny End Solve V辿t c畉n 22. Bi 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] ; } ; 23. Bi 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 ; } 25. Bi 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 } ; 26. Bi 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++ ; } 27. Bi to叩n 8 con H畉u 叩nh gi叩 Thi畉t k畉 畉u Thi畉t k畉 m畛i