- 1 Trá chìi th¡p H Nëi 7. - 1.1 Làch sû ph¡t triºn trá chìi Th¡p H nëi. - 1.2.2 B i to¡n Th¡p H Nëi vîi nhi·u cåc. - 1.2.3 C¡c c£i bi¶n cõa b i to¡n Th¡p H Nëi. - 1.3 C¡c cæng cö gi£i b i to¡n th¡p H Nëi v c¡c v§n · li¶n quan. - 1.3.4 Thuªt to¡n gi£i trá chìi Th¡p H Nëi. - 1.3.5 B i to¡n Th¡p H Nëi v mët sè v§n · kh¡c li¶n quan. - 37 2 C¡c ph÷ìng ph¡p gi£i b i to¡n Th¡p H Nëi 39. - 2.1 Trá chìi th¡p H Nëi v thuªt gi£i » qui. - 2.2 Gi£i b i to¡n th¡p H Nëi b¬ng biºu di¹n trong h» ¸m cì sè 2. - 2.3.4 Gi£i b i to¡n Th¡p H Nëi. - Têng quan v· làch sû ph¡t triºn trá chìi Th¡p H Nëi.. - C¡c ph÷ìng ph¡p gi£i b i to¡n Th¡p H Nëi.. - Trá chìi th¡p H Nëi. - H¼nh 1.1: B¼a cuèn s¡ch giîi thi»u v· trá chìi Th¡p H Nëi cõa E. - Eduard Lucas, t¡c gi£ cõa trá chìi th¡p H Nëi. - C¡c hëp üng trá chìi Th¡p H nëi R§t câ thº, theo E. - Cët cí H Nëi x¥y n«m hìn 70 n«m tr÷îc khi trá chìi th¡p H Nëi. - Lucas °t t¶n cho trá chìi cõa m¼nh l trá chìi Th¡p H Nëi?. - H¼nh 1.4: B¼a cõa hëp üng trá chìi Th¡p H Nëi. - D÷îi ¥y l tí h÷îng d¨n thù nh§t giîi thi»u trá chìi Th¡p H Nëi. - H¼nh 1.5: Tí giîi thi»u trá chìi Th¡p H Nëi. - H¼nh 1.6: Tí h÷îng d¨n luªt trá chìi Th¡p H Nëi. - D÷îi ¥y l c¡c trang 152-156 cõa cuèn s¡ch [18] vi¸t v· trá chìi Th¡p H nëi.. - H¼nh 1.8: Líi giîi thi»u trá chìi th¡p H Nëi trong B i to¡n 89:. - Th¡p H Nëi - B i to¡n Bc k¼. - Æng ¢ vi¸t v· b i to¡n n y trá chìi th¡p H Nëi vîi bèn cåc (d÷îi d¤ng c¡c qu¥n cí v gåi l The Reve's puzzle-c¥u è cõa Reve).. - 1.2.1 B i to¡n Th¡p H Nëi cê iºn. - H¼nh 1.11: Líi gi£i b i to¡n th¡p H nëi vîi 4 cåc cõa H. - º gi£i b i to¡n th¡p H Nëi vîi p cåc, ta thüc hi»n c¡c b÷îc sau.. - xu§t thuªt to¡n gi£i cho b i to¡n Th¡p H Nëi vîi sè cåc b§t k¼. - (presumed-optimal solution) cho ph²p lªp tr¼nh gi£i b i to¡n th¡p H Nëi vîi sè cåc b§t k¼. - B i to¡n Th¡p H Nëi câ kh¡ nhi·u c£i bi¶n r§t thó và. - B i to¡n th¡p H Nëi vîi c§u h¼nh ban ¦u b§t k¼. - B i to¡n th¡p H Nëi vîi ba cåc v n ¾a ¢ ÷ñc E. - â l trá chìi Th¡p H Nëi vîi c§u h¼nh ban ¦u b§t k¼ : Ngay khi bt ¦u chìi (ho°c ti¸p töc sau khi trá chìi bà gi¡n o¤n), câ thº coi c¡c ¾a ð và tr½ b§t k¼ (khæng nh§t thi¸t ph£i t§t c£ c¡c ¾a n¬m tr¶n mët cåc, m câ thº ð tr¶n c¡c cåc kh¡c nhau, mi¹n l tu¥n theo qui tc ¾a ð tr¶n nhä, ¾a n¬m d÷îi to). - B i to¡n Th¡p H Nëi vîi nhi·u ¾a gièng nhau (Multi-disk Hanoi). - x²t hai c£i bi¶n sau ¥y cõa b i to¡n th¡p H Nëi. - B i to¡n th¡p H Nëi vîi c¡c h¤n ch¸ tr¶n chuyºn ëng cõa c¡c. - B i to¡n th¡p H Nëi xoay váng (Cyclic Tower of Hanoi). - Atkinson [9] l ng÷íi ¦u ti¶n (1981) nghi¶n cùu b i to¡n th¡p H Nëi xoay váng.. - Trá chìi th¡p H Nëi vîi ba cåc v c¡c ¾a hai m u. - giîi thi»u mët sè trá chìi th¡p H Nëi vîi c¡c ¾a m u nh÷ sau.. - B i to¡n Th¡p H Nëi vîi chuyºn ëng song song (Parallel Moves of the Tower of Hanoi Problem). - Trá chìi Th¡p H Nëi vîi chuyºn ëng song song tu¥n theo hai qui tc:. - Câ thº sû döng h» ¸m (cì sè 2) º mæ t£ líi gi£i cõa b i to¡n th¡p H Nëi. - C¡c ph÷ìng ph¡p gi£i b i to¡n Th¡p H Nëi. - B i to¡n th¡p H Nëi vîi sè. - qui cõa b i to¡n Th¡p H Nëi vîi ba cåc v sè ¾a b§t k¼.. - L¦n 2 : Chuyºn ¾a sè 2 tø cåc A sang cåc C.. - L¦n 3 : Chuyºn ¾a sè 1 tø cåc B sang cåc C (l¶n tr¶n ¾a sè 2).. - L¦n 1 : Chuyºn ¾a sè 1 tø cåc A sang cåc C.. - L¦n 2 : Chuyºn ¾a sè 2 tø cåc A sang cåc B.. - L¦n 3 : Chuyºn ¾a sè 1 tø cåc C sang cåc B (l¶n tr¶n ¾a sè 2). - L¦n 4 : Chuyºn ¾a sè 3 tø cåc A sang cåc C. - L¤i chuyºn hai ¾a ¦u tø cåc B sang cåc C (ba l¦n chuyºn):. - L¦n 5 : Chuyºn ¾a sè 1 tø cåc B sang cåc A.. - L¦n 6 : Chuyºn ¾a sè 2 tø cåc B sang cåc C (chçng l¶n tr¶n ¾a sè 3).. - L¦n 7 : Chuyºn ¾a sè 1 tø cåc B sang cåc C (chçng l¶n ¾a sè 2).. - L¦n 1 (dáng 2 cët 1): Chuyºn ¾a tr¶n còng (sè 1) tø cåc A sang cåc C.. - L¦n 2 (dáng 3 cët 1): Chuyºn ¾a sè 2 tø cåc A sang cåc B.. - L¦n 4 (dáng 5 cët 1): Chuyºn ¾a sè 3 tø cåc A sang cåc B.. - L¦n 5 (dáng 6 cët 1): Chuyºn ¾a sè 1 tø cåc C sang cåc A.. - L¦n 7 (dáng 8 cët 1): Chuyºn ¾a sè 1 tø cåc A sang cåc B.. - L¦n 8 (dáng 1 cët 2): Chuyºn ¾a sè 4 tø cåc A sang cåc C.. - L¦n 9 (dáng 2 cët 2): Chuyºn ¾a sè 1 tø cåc B sang cåc C.. - L¦n 10 (dáng 3 cët 2): Chuyºn ¾a sè 2 tø cåc B sang cåc A.. - L¦n 11 (dáng 4 cët 2): Chuyºn ¾a sè 1 tø cåc C sang cåc A.. - L¦n 13 (dáng 6 cët 2): Chuyºn ¾a sè 1 tø cåc A sang cåc B.. - Tr÷îc ti¶n ta gi£i b i to¡n Th¡p H Nëi cho ba ¾a:. - Chuyºn ¾a sè 1 tø cåc A sang cåc B. - chuyºn ¾a sè 2 tø cåc A sang cåc C. - chuyºn ¾a sè 1 tø cåc B sang cåc C. - Chuyºn ¾a sè 3 tø cåc A sang cåc B. - Thuªt gi£i » qui b i to¡n th¡p H Nëi.. - Chuyºn n − 1 ¾a tr¶n còng tø cåc A sang cåc B (theo gi£ thi¸t ¢ bi¸t c¡ch gi£i).. - Chuyºn n − 1 ¾a tø cåc B sang cåc C (theo gi£ thi¸t ¢ bi¸t c¡ch gi£i).. - K½ hi»u L(n) l sè l¦n chuyºn ¾a tèi ÷u trong b i to¡n th¡p H Nëi vîi n ¾a v ba cåc. - Cuèi còng, l¤i chuyºn n − 1 ¾a tø cåc B sang cåc C. - Thuªt to¡n » qui gi£i b i to¡n Th¡p H Nëi n¶u tr¶n l thuªt to¡n tèi ÷u (sè l¦n chuyºn ¾a ½t nh§t). - Ta câ thº sû döng h» ¸m cì sè 2 º gi£i b i to¡n Th¡p H Nëi cho ba cåc vîi n ¾a nh÷ sau.. - B÷îc 3 : Chuyºn ¾a sè 1 tø cåc B sang cåc C, k½ hi»u l (11) 2. - ÷ñc chuyºn tø cåc A sang cåc C . - B÷îc 3 : Chuyºn ¾a sè 1 tø cåc C sang cåc B, k½ hi»u l (011) 2 . - B÷îc 4 : Chuyºn ¾a sè 3 tø cåc A sang cåc C, k½ hi»u l (100) 2 . - B÷îc 5 : Chuyºn ¾a sè 1 tø cåc B sang cåc A, k½ hi»u l (101) 2 . - B÷îc 6 : Chuyºn ¾a sè 2 tø cåc B sang cåc C, k½ hi»u l (110) 2 . - B÷îc 7 : Chuyºn ¾a 1 tø cåc A sang cåc C (chçng l¶n ¾a 2), k½ hi»u l (111) 2. - Gi£i b i to¡n Th¡p H Nëi vîi bèn ¾a nhí h» ¸m cì sè 2. - 1 00001 ÷a ¾a sè 1 tø cåc A sang cåc trèng B.. - 2 00010 ÷a ¾a sè 1 tø cåc A sang cåc trèng C.. - 8 01000 ÷a ¾a 4 tø cåc A sang cåc trèng C.. - 26 11010 ¾a 2 tø cåc A sang cåc C (KHÆNG chçng l¶n 4).. - Nh÷ vªy, câ thº gi£i b i to¡n Th¡p H Nëi nhí sû döng h» ¸m cì sè 2.. - R§t nhi·u b i to¡n trong Trá chìi Th¡p H Nëi câ thº ph¡t biºu nh÷. - B i to¡n Th¡p H Nëi vîi c§u h¼nh b§t k¼. - Th½ dö d÷îi ¥y têng qu¡t hâa trá chìi Th¡p H Nëi. - th nh trá chìi Th¡p H Nëi vîi c¡c ¾a m u. - Th¡p H Nëi suy rëng v c£i bi¶n. - Ch÷ìng 2 tr¼nh b y chi ti¸t c¡c líi gi£i b i to¡n th¡p H Nëi vîi ba cåc (thuªt gi£i » qui, sû döng h» ¸m cì sè 2, sû döng ç thà H Nëi).