際際滷

際際滷Share a Scribd company logo
C畉U TRC D畛 LI畛U V GI畉I THU畉T Ch動董ng 5: 畛 qui
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
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)); }
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)
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
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畛
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
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 << &quot;Move disk &quot; << count << &quot; from &quot; << start << &quot; to &quot; << finish << &quot;.&quot; << endl; move(count  1, temp, finish, start); } }
Bi to叩n Th叩p H n畛i  Thi hnh
Bi to叩n Th叩p H n畛i  C但y 畛 qui
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.
C但y thi hnh v stack h畛 th畛ng C但y thi hnh
畛 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.
Kh畛 畛 qui u担i hm giai th畛a Gi畉i thu畉t: product=1 for  ( int  count=1; count < n; count++) product *= count;
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)); }
D達y s畛 Fibonacci  C但y thi hnh 達 t鱈nh r畛i
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; }
Bi to叩n 8 con H畉u
Bi to叩n 4 con H畉u
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
Bi to叩n 8 con H畉u  Thi畉t k畉 ph動董ng th畛c
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] ; } ;
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 ; }
Bi to叩n 8 con H畉u  G坦c nh狸n kh叩c
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 } ;
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++ ; }
Bi to叩n 8 con H畉u  叩nh gi叩 Thi畉t k畉 畉u Thi畉t k畉 m畛i

More Related Content

Ctdl C05

  • 1. C畉U TRC D畛 LI畛U V GI畉I THU畉T Ch動董ng 5: 畛 qui
  • 2. 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 << &quot;Move disk &quot; << count << &quot; from &quot; << start << &quot; to &quot; << finish << &quot;.&quot; << endl; move(count 1, temp, finish, start); } }
  • 9. Bi to叩n Th叩p H n畛i Thi hnh
  • 10. Bi to叩n Th叩p H n畛i C但y 畛 qui
  • 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.
  • 12. C但y thi hnh v stack h畛 th畛ng C但y 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)); }
  • 16. D達y s畛 Fibonacci C但y thi hnh 達 t鱈nh r畛i
  • 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; }
  • 18. Bi to叩n 8 con H畉u
  • 19. Bi to叩n 4 con H畉u
  • 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
  • 21. Bi to叩n 8 con H畉u Thi畉t k畉 ph動董ng th畛c
  • 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 ; }
  • 24. Bi to叩n 8 con H畉u G坦c nh狸n kh叩c
  • 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