CH NG I:ƯƠ
THU T TOÁNẬ
1.1. KHÁI NI M THU T TOÁN.Ệ Ậ
1.1.1. M đ u:ở ầ
Có nhi u l p bài toán t ng quát xu t hi n trong toán h c r i r c. Ch ng h n,ề ớ ổ ấ ệ ọ ờ ạ ẳ ạ
cho m t dãy các s nguyên, tìm s l n nh t; cho m t t p h p, li t kê các t p con c aộ ố ố ớ ấ ộ ậ ợ ệ ậ ủ
nó; cho t p h p các s nguyên, x p chúng theo th t tăng d n; cho m t m ng, tìmậ ợ ố ế ứ ự ầ ộ ạ
đ ng đi ng n nh t gi a hai đ nh c a nó. Khi đ c giao cho m t bài toán nh v y thìườ ắ ấ ữ ỉ ủ ượ ộ ư ậ
vi c đ u tiên ph i làm là xây d ng m t mô hình d ch bài toán đó thành ng c nh toánệ ầ ả ự ộ ị ữ ả
h c. Các c u trúc r i r c đ c dùng trong các mô hình này là t p h p, dãy, hàm, hoánọ ấ ờ ạ ượ ậ ợ
v , quan h , cùng v i các c u trúc khác nh đ th , cây, m ng - nh ng khái ni m sị ệ ớ ấ ư ồ ị ạ ữ ệ ẽ
đ c nghiên c u các ch ng sau.ượ ứ ở ươ
L p đ c m t mô hình toán h c thích h p ch là m t ph n c a quá trình gi i.ậ ượ ộ ọ ợ ỉ ộ ầ ủ ả
Đ hoàn t t quá trình gi i, còn c n ph i có m t ph ng pháp dùng mô hình đ gi i bàiể ấ ả ầ ả ộ ươ ể ả
toán t ng quát. Nói m t cách lý t ng, cái đ c đòi h i là m t th t c, đó là dãy cácổ ộ ưở ượ ỏ ộ ủ ụ
b c d n t i đáp s mong mu n. M t dãy các b c nh v y, đ c g i là m t thu tướ ẫ ớ ố ố ộ ướ ư ậ ượ ọ ộ ậ
toán.
Khi thi t k và cài đ t m t ph n m m tin h c cho m t v n đ nào đó, ta c nế ế ặ ộ ầ ề ọ ộ ấ ề ầ
ph i đ a ra ph ng pháp gi i quy t mà th c ch t đó là thu t toán gi i quy t v n đả ư ươ ả ế ự ấ ậ ả ế ấ ề
này. Rõ ràng r ng, n u không tìm đ c m t ph ng pháp gi i quy t thì không th l pằ ế ượ ộ ươ ả ế ể ậ
trình đ c. Chính vì th , thu t toán là khái ni m n n t ng c a h u h t các lĩnh v cượ ế ậ ệ ề ả ủ ầ ế ự
c a tin h c.ủ ọ
1.1.2. Đ nh nghĩa:ị Thu t toán là m t b ng li t kê các ch d n (hay quy t c) c n th cậ ộ ả ệ ỉ ẫ ắ ầ ự
hi n theo t ng b c xác đ nh nh m gi i m t bài toán đã cho.ệ ừ ướ ị ằ ả ộ
Thu t ng “Algorithm” (thu t toán) là xu t phát t tên nhà toán h c R p Al-ậ ữ ậ ấ ừ ọ Ả ậ
Khowarizmi. Ban đ u, t algorism đ c dùng đ ch các quy t c th c hi n các phépầ ừ ượ ể ỉ ắ ự ệ
tính s h c trên các s th p phân. Sau đó, algorism chuy n thành algorithm vào th kố ọ ố ậ ể ế ỷ
19. V i s quan tâm ngày càng tăng đ i v i các máy tính, khái ni m thu t toán đã đ cớ ự ố ớ ệ ậ ượ
cho m t ý nghĩa chung h n, bao hàm c các th t c xác đ nh đ gi i các bài toán, chộ ơ ả ủ ụ ị ể ả ứ
không ph i ch là th t c đ th c hi n các phép tính s h c.ả ỉ ủ ụ ể ự ệ ố ọ
Có nhi u cách trình bày thu t toán: dùng ngôn ng t nhiên, ngôn ng l u đề ậ ữ ự ữ ư ồ
(s đ kh i), ngôn ng l p trình. Tuy nhiên, m t khi dùng ngôn ng l p trình thì chơ ồ ố ữ ậ ộ ữ ậ ỉ
nh ng l nh đ c phép trong ngôn ng đó m i có th dùng đ c và đi u này th ngữ ệ ượ ữ ớ ể ượ ề ườ
làm cho s mô t các thu t toán tr nên r i r m và khó hi u. H n n a, vì nhi u ngônự ả ậ ở ố ắ ể ơ ữ ề
ng l p trình đ u đ c dùng r ng rãi, nên ch n m t ngôn ng đ c bi t nào đó là đi uữ ậ ề ượ ộ ọ ộ ữ ặ ệ ề
ng i ta không mu n. Vì v y đây các thu t toán ngoài vi c đ c trình bày b ngườ ố ậ ở ậ ệ ượ ằ
4
ngôn ng t nhiên cùng v i nh ng ký hi u toán h c quen thu c còn dùng m t d ng giữ ự ớ ữ ệ ọ ộ ộ ạ ả
mã đ mô t thu t toán. Gi mã t o ra b c trung gian gi a s mô t m t thu t toánể ả ậ ả ạ ướ ữ ự ả ộ ậ
b ng ngôn ng thông th ng và s th c hi n thu t toán đó trong ngôn ng l p trình.ằ ữ ườ ự ự ệ ậ ữ ậ
Các b c c a thu t toán đ c ch rõ b ng cách dùng các l nh gi ng nh trong cácướ ủ ậ ượ ỉ ằ ệ ố ư
ngôn ng l p trình.ữ ậ
Thí d 1:ụ Mô t thu t toán tìm ph n t l n nh t trong m t dãy h u h n các sả ậ ầ ử ớ ấ ộ ữ ạ ố
nguyên.
a) Dùng ngôn ng t nhiên đ mô t các b c c n ph i th c hi nữ ự ể ả ướ ầ ả ự ệ :
1. Đ t giá tr c c đ i t m th i b ng s nguyên đ u tiên trong dãy. (C c đ i t mặ ị ự ạ ạ ờ ằ ố ầ ự ạ ạ
th i s là s nguyên l n nh t đã đ c ki m tra m t giai đo n nào đó c a th t c.)ờ ẽ ố ớ ấ ượ ể ở ộ ạ ủ ủ ụ
2. So sánh s nguyên ti p sau v i giá tr c c đ i t m th i, n u nó l n h n giá trố ế ớ ị ự ạ ạ ờ ế ớ ơ ị
c c đ i t m th i thì đ t c c đ i t m th i b ng s nguyên đó.ự ạ ạ ờ ặ ự ạ ạ ờ ằ ố
3. L p l i b c tr c n u còn các s nguyên trong dãy.ặ ạ ướ ướ ế ố
4. D ng khi không còn s nguyên nào n a trong dãy. C c đ i t m th i đi mừ ố ữ ự ạ ạ ờ ở ể
này chính là s nguyên l n nh t c a dãy.ố ớ ấ ủ
b) Dùng đo n gi mãạ ả :
procedure max (a1, a2, ..., an: integers)
max:= a1
for i:= 2 to n
if max <ai then max:= ai
{max là ph n t l n nh t}ầ ử ớ ấ
Thu t toán này tr c h t gán s h ng đ u tiên aậ ướ ế ố ạ ầ 1 c a dãy cho bi n max. Vòngủ ế
l p “for” đ c dùng đ ki m tra l n l t các s h ng c a dãy. N u m t s h ng l nặ ượ ể ể ầ ượ ố ạ ủ ế ộ ố ạ ớ
h n giá tr hi n th i c a max thì nó đ c gán làm giá tr m i c a max.ơ ị ệ ờ ủ ượ ị ớ ủ
1.1.3. Các đ c tr ng c a thu t toán:ặ ư ủ ậ
-- Đ u vào ầ(Input): M t thu t toán có các giá tr đ u vào t m t t p đã đ c ch rõ.ộ ậ ị ầ ừ ộ ậ ượ ỉ
-- Đ u raầ (Output): T m i t p các giá tr đ u vào, thu t toán s t o ra các giá tr đ uừ ỗ ậ ị ầ ậ ẽ ạ ị ầ
ra. Các giá tr đ u ra chính là nghi m c a bài toán.ị ầ ệ ủ
-- Tính d ng:ừ Sau m t s h u h n b c thu t toán ph i d ng.ộ ố ữ ạ ướ ậ ả ừ
-- Tính xác đ nh:ị m i b c, các b c thao tác ph i h t s c rõ ràng, không gây nênỞ ỗ ướ ướ ả ế ứ
s nh p nh ng. Nói rõ h n, trong cùng m t đi u ki n hai b x lý cùng th c hi n m tự ậ ằ ơ ộ ề ệ ộ ử ự ệ ộ
b c c a thu t toán ph i cho nh ng k t qu nh nhau.ướ ủ ậ ả ữ ế ả ư
-- Tính hi u qu :ệ ả Tr c h t thu t toán c n đúng đ n, nghĩa là sau khi đ a d li uướ ế ậ ầ ắ ư ữ ệ
vào thu t toán ho t đ ng và đ a ra k t qu nh ý mu n.ậ ạ ộ ư ế ả ư ố
-- Tính ph d ng:ổ ụ Thu t toán có th gi i b t kỳ m t bài toán nào trong l p các bàiậ ể ả ấ ộ ớ
toán. C th là thu t toán có th có các đ u vào là các b d li u khác nhau trong m tụ ể ậ ể ầ ộ ữ ệ ộ
mi n xác đ nh.ề ị
5
1.2. THU T TOÁN TÌM KI M.Ậ Ế
1.2.1. Bài toán tìm ki m:ế Bài toán xác đ nh v trí c a m t ph n t trong m t b ngị ị ủ ộ ầ ử ộ ả
li t kê s p th t th ng g p trong nhi u tr ng h p khác nhau. Ch ng h n ch ngệ ắ ứ ự ườ ặ ề ườ ợ ẳ ạ ươ
trình ki m tra chính t c a các t , tìm ki m các t này trong m t cu n t đi n, mà tể ả ủ ừ ế ừ ộ ố ừ ể ừ
đi n ch ng qua cũng là m t b ng li t kê s p th t c a các t . Các bài toán thu c lo iể ẳ ộ ả ệ ắ ứ ự ủ ừ ộ ạ
này đ c g i là các bài toán tìm ki m.ượ ọ ế
Bài toán tìm ki m t ng quát đ c mô t nh sau: xác đ nh v trí c a ph n t xế ổ ượ ả ư ị ị ủ ầ ử
trong m t b ng li t kê các ph n t phân bi t aộ ả ệ ầ ử ệ 1, a2, ..., an ho c xác đ nh r ng nó khôngặ ị ằ
có m t trong b ng li t kê đó. L i gi i c a bài toán trên là v trí c a s h ng c a b ngặ ả ệ ờ ả ủ ị ủ ố ạ ủ ả
li t kê có giá tr b ng x (t c là i s là nghi m n u x=aệ ị ằ ứ ẽ ệ ế i và là 0 n u x không có m tế ặ
trong b ng li t kê).ả ệ
1.2.2. Thu t toán tìm ki m tuy n tính:ậ ế ế Tìm ki m tuy n tính hay tìm ki m tu nế ế ế ầ
t là b t đ u b ng vi c so sánh x v i aự ắ ầ ằ ệ ớ 1; khi x=a1, nghi m là v trí aệ ị 1, t c là 1; khi xứ≠a1,
so sánh x v i aớ2. N u x=aế2, nghi m là v trí c a aệ ị ủ 2, t c là 2. Khi xứ≠a2, so sánh x v i aớ3.
Ti p t c quá trình này b ng cách tu n t so sánh x v i m i s h ng c a b ng li t kêế ụ ằ ầ ự ớ ỗ ố ạ ủ ả ệ
cho t i khi tìm đ c s h ng b ng x, khi đó nghi m là v trí c a s h ng đó. N u toànớ ượ ố ạ ằ ệ ị ủ ố ạ ế
b ng li t kê đã đ c ki m tra mà không xác đ nh đ c v trí c a x, thì nghi m là 0.ả ệ ượ ể ị ượ ị ủ ệ
Gi mã đ i v i thu t toán tìm ki m tuy n tính đ c cho d i đây:ả ố ớ ậ ế ế ượ ướ
procedure tìm ki m tuy n tính (x: integer, aế ế 1,a2,...,an: integers phân bi t)ệ
i := 1
while (i ≤ n and x ≠ ai)
i := i + 1
if i ≤ n then location := i
else location := 0
{location là ch s d i c a s h ng b ng x ho c là 0 n u không tìm đ c x}ỉ ố ướ ủ ố ạ ằ ặ ế ượ
1.2.3. Thu t toán tìm ki m nh phân:ậ ế ị Thu t toán này có th đ c dùng khi b ngậ ể ượ ả
li t kê có các s h ng đ c s p theo th t tăng d n. Ch ng h n, n u các s h ng làệ ố ạ ượ ắ ứ ự ầ ẳ ạ ế ố ạ
các s thì chúng đ c s p t s nh nh t đ n s l n nh t ho c n u chúng là các tố ượ ắ ừ ố ỏ ấ ế ố ớ ấ ặ ế ừ
hay xâu ký t thì chúng đ c s p theo th t t đi n. Thu t toán th hai này g i làự ượ ắ ứ ự ừ ể ậ ứ ọ
thu t toán tìm ki m nh phân. Nó đ c ti n hành b ng cách so sánh ph n t c n xácậ ế ị ượ ế ằ ầ ử ầ
đ nh v trí v i s h ng gi a b ng li t kê. Sau đó b ng này đ c tách làm hai b ng kêị ị ớ ố ạ ở ữ ả ệ ả ượ ả
con nh h n có kích th c nh nhau, ho c m t trong hai b ng con ít h n b ng con kiaỏ ơ ướ ư ặ ộ ả ơ ả
m t s h ng. S tìm ki m ti p t c b ng cách h n ch tìm ki m m t b ng kê conộ ố ạ ự ế ế ụ ằ ạ ế ế ở ộ ả
thích h p d a trên vi c so sánh ph n t c n xác đ nh v trí v i s h ng gi a b ng kê.ợ ự ệ ầ ử ầ ị ị ớ ố ạ ữ ả
Ta s th y r ng thu t toán tìm ki m nh phân hi u qu h n nhi u so v i thu t toánẽ ấ ằ ậ ế ị ệ ả ơ ề ớ ậ
tìm ki m tuy n tính.ế ế
6
Thí d 2. ụĐ tìm s 19 trong b ng li t kê 1,2,3,5,6,7,8,10,12,13,15,16,18,19,20,22 taể ố ả ệ
tách b ng li t kê g m 16 s h ng này thành hai b ng li t kê nh h n, m i b ng có 8ả ệ ồ ố ạ ả ệ ỏ ơ ỗ ả
s h ng, c th là: 1,2,3,5,6,7,8,10 và 12,13,15,16,18,19,20,22. Sau đó ta so sánh 19 v iố ạ ụ ể ớ
s h ng cu i cùng c a b ng con th nh t. Vì 10<19, vi c tìm ki m 19 ch gi i h nố ạ ố ủ ả ứ ấ ệ ế ỉ ớ ạ
trong b ng li t kê con th 2 t s h ng th 9 đ n 16 trong b ng li t kê ban đ u. Ti pả ệ ứ ừ ố ạ ứ ế ả ệ ầ ế
theo, ta l i tách b ng li t kê con g m 8 s h ng này làm hai b ng con, m i b ng có 4ạ ả ệ ồ ố ạ ả ỗ ả
s h ng, c th là 12,13,15,16 và 18,19,20,22. Vì 16<19, vi c tìm ki m l i đ c gi iố ạ ụ ể ệ ế ạ ượ ớ
h n ch trong b ng con th 2, t s h ng th 13 đ n 16 c a b ng li t kê ban đ u.ạ ỉ ả ứ ừ ố ạ ứ ế ủ ả ệ ầ
B ng li t kê th 2 này l i đ c tách làm hai, c th là: 18,19 và 20,22. Vì 19 không l nả ệ ứ ạ ượ ụ ể ớ
h n s h ng l n nh t c a b ng con th nh t nên vi c tìm ki m gi i h n ch b ngơ ố ạ ớ ấ ủ ả ứ ấ ệ ế ớ ạ ỉ ở ả
con th nh t g m các s 18,19, là s h ng th 13 và 14 c a b ng ban đ u. Ti p theoứ ấ ồ ố ố ạ ứ ủ ả ầ ế
b ng con ch a hai s h ng này l i đ c tách làm hai, m i b ng có m t s h ng 18 vàả ứ ố ạ ạ ượ ỗ ả ộ ố ạ
19. Vì 18<19, s tìm ki m gi i h n ch trong b ng con th 2, b ng li t kê ch ch a sự ế ớ ạ ỉ ả ứ ả ệ ỉ ứ ố
h ng th 14 c a b ng li t kê ban đ u, s h ng đó là s 19. Bây gi s tìm ki m đã thuạ ứ ủ ả ệ ầ ố ạ ố ờ ự ế
h p v ch còn m t s h ng, so sánh ti p cho th y19 là s h ng th 14 c a b ng li tẹ ề ỉ ộ ố ạ ế ấ ố ạ ứ ủ ả ệ
kê ban đ u.ầ
Bây gi ta có th ch rõ các b c trong thu t toán tìm ki m nh phân.ờ ể ỉ ướ ậ ế ị
Đ tìm s nguyên x trong b ng li t kê aể ố ả ệ 1,a2,...,an v i aớ1 < a2 < ... < an, ta b t đ uắ ầ
b ng vi c so sánh x v i s h ng aằ ệ ớ ố ạ m gi a c a dãy, v i m=[(n+1)/2]. N u x > aở ữ ủ ớ ế m, vi cệ
tìm ki m x gi i h n n a th hai c a dãy, g m aế ớ ạ ở ử ứ ủ ồ m+1,am+2,...,an. N u x không l n h nế ớ ơ
am, thì s tìm ki m gi i h n trong n a đ u c a dãy g m aự ế ớ ạ ử ầ ủ ồ 1,a2,...,am.
Bây gi s tìm ki m ch gi i h n trong b ng li t kê có không h n [n/2] ph n t .ờ ự ế ỉ ớ ạ ả ệ ơ ầ ử
Dùng chính th t c này, so sánh x v i s h ng gi a c a b ng li t kê đ c h n ch .ủ ụ ớ ố ạ ở ữ ủ ả ệ ượ ạ ế
Sau đó l i h n ch vi c tìm ki m n a th nh t ho c n a th hai c a b ng li t kê.ạ ạ ế ệ ế ở ử ứ ấ ặ ử ứ ủ ả ệ
L p l i quá trình này cho t i khi nh n đ c m t b ng li t kê ch có m t s h ng. Sauặ ạ ớ ậ ượ ộ ả ệ ỉ ộ ố ạ
đó, ch còn xác đ nh s h ng này có ph i là x hay không. Gi mã cho thu t toán tìmỉ ị ố ạ ả ả ậ
ki m nh phân đ c cho d i đây:ế ị ượ ướ
procedure tìm ki m nh phân (x: integer, aế ị 1,a2,...,an: integers tăng d n)ầ
i := 1 {i là đi m mút trái c a kho ng tìm ki m}ể ủ ả ế
j := n {j là đi m mút ph i c a kho ng tìm ki m}ể ả ủ ả ế
while i < j
begin
m:= [(i+j)/2]
if x>am then i:=m+1
else j := m
end
if x = ai then location := i
7
else location := 0
{location là ch s d i c a s h ng b ng x ho c 0 n u không tìm th y x}ỉ ố ướ ủ ố ạ ằ ặ ế ấ
1.3. Đ PH C T P C A THU T TOÁN.Ộ Ứ Ạ Ủ Ậ
1.3.1. Khái ni m v đ ph c t p c a m t thu t toánệ ề ộ ứ ạ ủ ộ ậ :
Th c đo hi u qu c a m t thu t toán là th i gian mà máy tính s d ng đ gi iướ ệ ả ủ ộ ậ ờ ử ụ ể ả
bài toán theo thu t toán đang xét, khi các giá tr đ u vào có m t kích th c xác đ nh.ậ ị ầ ộ ướ ị
M t th c đo th hai là dung l ng b nh đòi h i đ th c hi n thu t toán khi các giáộ ướ ứ ượ ộ ớ ỏ ể ự ệ ậ
tr đ u vào có kích th c xác đ nh. Các v n đ nh th liên quan đ n đ ph c t p tínhị ầ ướ ị ấ ề ư ế ế ộ ứ ạ
toán c a m t thu t toán. S phân tích th i gian c n thi t đ gi i m t bài toán có kíchủ ộ ậ ự ờ ầ ế ể ả ộ
th c đ c bi t nào đó liên quan đ n đ ph c t p th i gian c a thu t toán. S phân tíchướ ặ ệ ế ộ ứ ạ ờ ủ ậ ự
b nh c n thi t c a máy tính liên quan đ n đ ph c t p không gianộ ớ ầ ế ủ ế ộ ứ ạ c a thu t toán.ủ ậ
V c xem xét đ ph c t p th i gian và không gian c a m t thu t toán là m t v n đ r tệ ộ ứ ạ ờ ủ ộ ậ ộ ấ ề ấ
thi t y u khi các thu t toán đ c th c hi n. Bi t m t thu t toán s đ a ra đáp sế ế ậ ượ ự ệ ế ộ ậ ẽ ư ố
trong m t micro giây, trong m t phút ho c trong m t t năm, hi n nhiên là h t s c quanộ ộ ặ ộ ỉ ể ế ứ
tr ng. T ng t nh v y, dung l ng b nh đòi h i ph i là kh d ng đ gi i m tọ ươ ự ư ậ ượ ộ ớ ỏ ả ả ụ ể ả ộ
bài toán,vì v y đ ph c t p không gian cũng c n ph i tính đ n.Vì vi c xem xét đậ ộ ứ ạ ầ ả ế ệ ộ
ph c t p không gian g n li n v i các c u trúc d li u đ c bi t đ c dùng đ th cứ ạ ắ ề ớ ấ ữ ệ ặ ệ ượ ể ự
hi n thu t toán nên đây ta s t p trung xem xét đ ph c t p th i gian.ệ ậ ở ẽ ậ ộ ứ ạ ờ
Đ ph c t p th i gian c a m t thu t toán có th đ c bi u di n qua s cácộ ứ ạ ờ ủ ộ ậ ể ượ ể ễ ố
phép toán đ c dùng b i thu t toán đó khi các giá tr đ u vào có m t kích th c xácượ ở ậ ị ầ ộ ướ
đ nh. S dĩ đ ph c t p th i gian đ c mô t thông qua s các phép toán đòi h i thayị ở ộ ứ ạ ờ ượ ả ố ỏ
vì th i gian th c c a máy tính là b i vì các máy tính khác nhau th c hi n các phép tínhờ ự ủ ở ự ệ
s c p trong nh ng kho ng th i gian khác nhau. H n n a, phân tích t t c các phépơ ấ ữ ả ờ ơ ữ ấ ả
toán thành các phép tính bit s c p mà máy tính s d ng là đi u r t ph c t p.ơ ấ ử ụ ề ấ ứ ạ
Thí d 3:ụ Xét thu t toán tìm s l n nh t trong dãy n s aậ ố ớ ấ ố 1, a2, ..., an. Có th coi kíchể
th c c a d li u nh p là s l ng ph n t c a dãy s , t c là n. N u coi m i l n soướ ủ ữ ệ ậ ố ượ ầ ử ủ ố ứ ế ỗ ầ
sánh hai s c a thu t toán đòi h i m t đ n v th i gian (giây ch ng h n) thì th i gianố ủ ậ ỏ ộ ơ ị ờ ẳ ạ ờ
th c hi n thu t toán trong tr ng h p x u nh t là n-1 giây. V i dãy 64 s , th i gianự ệ ậ ườ ợ ấ ấ ớ ố ờ
th c hi n thu t toán nhi u l m là 63 giây.ự ệ ậ ề ắ
Thí d 4:ụThu t toán v trò ch i “Tháp Hà N i”ậ ề ơ ộ
Trò ch i “Tháp Hà N i” nh sau: Có ba c c A, B, C và 64 cái đĩa (có l đ đ tơ ộ ư ọ ỗ ể ặ
vào c c), các đĩa có đ ng kính đôi m t khác nhau. Nguyên t c đ t đĩa vào c c là: m iọ ườ ộ ắ ặ ọ ỗ
đĩa ch đ c ch ng lên đĩa l n h n nó. Ban đ u, c 64 đĩa đ c đ t ch ng lên nhau ỉ ượ ồ ớ ơ ầ ả ượ ặ ồ ở
c t A; hai c t B, C tr ng. V n đ là ph i chuy n c 64 đĩa đó sang c t B hay C, m iộ ộ ố ấ ề ả ể ả ộ ỗ
l n ch đ c di chuy n m t đĩa.ầ ỉ ượ ể ộ
Xét trò ch i v i n đĩa ban đ u c c A (c c B và C tr ng). G i Sơ ớ ầ ở ọ ọ ố ọ n là s l nố ầ
chuy n đĩa đ ch i xong trò ch i v i n đĩa.ể ể ơ ơ ớ
8