Ch¬ng 1: LËp t×nh híng ®èi tîng - Ph¬ng ph¸p gi¶i quyÕt bµi
to¸n míi
Ch ng 1ươ
L p trình h ng đ i t ngậ ướ ố ượ
ph ng pháp gi i quy t bài toán m iươ ả ế ớ
1. Ph ng pháp l p trìnhươ ậ
T nhi u năm nay chúng ta đã nghe nhi u đ n thu t ng “L p trìnhừ ề ề ế ậ ữ ậ
h ng đ i t ng” (OOP - Object Oriented Programming). V y th c ch t nó làướ ố ượ ậ ự ấ
gì? Đ hi u đ c v n đ này chúng ta b t đ u nhìn l i m t chút l ch s phátể ể ượ ấ ề ắ ầ ạ ộ ị ử
tri n các ph ng pháp l p trình. Vào nh ng ngày đ u phát tri n c a máy tính,ể ươ ậ ữ ầ ể ủ
khi các ph n m m còn r t đ n gi n ch c vài ch c dòng l nh, ch ng trìnhầ ề ấ ơ ả ỉ ỡ ụ ệ ươ
đ c vi t tu n t v i các câu l nh th c hi n t đ u đ n cu i. Cách vi tượ ế ầ ự ớ ệ ự ệ ừ ầ ế ố ế
ch ng trình nh th này g i là ph ng pháp ươ ư ế ọ ươ l p trình tuy n tínhậ ế . Khoa h cọ
máy tính ngày càng phát tri n, các ph n m m đòi h i ngày càng ph c t p vàể ầ ề ỏ ứ ạ
l n h n r t nhi u. Đ n lúc này ph ng pháp l p trình tuy n tính t ra kémớ ơ ấ ề ế ươ ậ ế ỏ
hi u qu và có nh ng tr ng h p ng i l p trình không th ki m soát đ cệ ả ữ ườ ợ ườ ậ ể ể ượ
ch ng trình. Th là ph ng pháp ươ ế ươ l p trình c u trúcậ ấ (LTCT) ra đ i. Theoờ
cách ti p c n này, ch ng trình đ c t ch c thành các ch ng trình con.ế ậ ươ ượ ổ ứ ươ
M i ch ng trình con đ m nh n x lý m t công vi c nh trong toàn b hỗ ươ ả ậ ử ộ ệ ỏ ộ ệ
th ng. M i ch ng trình con này l i có th chia nh thành các ch ng trìnhố ỗ ươ ạ ể ỏ ươ
con nh h n. Quá trình phân chia nh v y ti p t c di n ra cho đ n cácỏ ơ ư ậ ế ụ ễ ế
ch ng trình con nh nh n đ c đ đ n gi n. Ng i ta g i đó là quá trìnhươ ỏ ậ ượ ủ ơ ả ườ ọ
làm m n d n. Các ch ng trình con t ng đ i đ c l p v i nhau, do đó có thị ầ ươ ươ ố ộ ậ ớ ể
phân công cho t ng nhóm đ m nh n vi t các ch ng trình con khác nhau.ừ ả ậ ế ươ
Ngôn ng l p trình th hi n rõ nét nh t ph ng pháp l p trình c u trúc chínhữ ậ ể ệ ấ ươ ậ ấ
là Pascal. Tuy nhiên, khi s d ng ph ng pháp l p trình này v n còn g p m tử ụ ươ ậ ẫ ặ ộ
khó khăn l n là t ch c d li u c a h th ng nh th nào trong máy tính. B iớ ổ ứ ữ ệ ủ ệ ố ư ế ở
vì theo quan đi m c a LTCT thì ể ủ Ch ng trình = C u trúc d li u + Gi iươ ấ ữ ệ ả
thu tậ. Đ làm đ c vi c này đòi h i ng i l p trình ph i có ki n r t v ngể ượ ệ ỏ ườ ậ ả ế ấ ữ
v c u trúc d li u. M t khó khăn n a g p ph i là gi i thu t c a ch ngề ấ ữ ệ ộ ữ ặ ả ả ậ ủ ươ
trình ph thu c r t ch t ch vào c u trúc d li u, do v y ch c n m t s thayụ ộ ấ ặ ẽ ấ ữ ệ ậ ỉ ầ ộ ự
đ i nh c u trúc d li u cũng có th làm thay đ i gi i thu t và nh v yổ ỏ ở ấ ữ ệ ể ổ ả ậ ư ậ
ph i vi t l i ch ng trình. Đi u này rõ ràng không th thích h p khi ph i xâyả ế ạ ươ ề ể ợ ả
d ng m t d án ph n m m r t l n. M t ph ng pháp l p trình m i ra đ i đự ộ ự ầ ề ấ ớ ộ ươ ậ ớ ờ ể
kh c ph c nh c đi m này và đó chính là ph ng pháp ắ ụ ượ ể ươ l p trình h ng đ iậ ướ ố
t ng ượ (LTHĐT). Đi m căn b n c a ph ng pháp này là thi t k ch ngể ả ủ ươ ế ế ươ
trình xoay quanh d li u c a h th ng. Nghĩa là lúc này các thao tác x lý c aữ ệ ủ ệ ố ử ủ
h th ng đ c g n li n v i d li u và nh v y m t s thay đ i nh c a dệ ố ượ ắ ề ớ ữ ệ ư ậ ộ ự ổ ỏ ủ ữ
li u ch nh h ng đ n các m t s nh các hàm x lý liên quan. S g n k tệ ỉ ả ưở ế ộ ố ỏ ử ự ắ ế
gi a d li u và các hàm x lý trên chúng t o ra đ i t ng. M t u đi m n aữ ữ ệ ử ạ ố ượ ộ ư ể ữ
có ph ng pháp LTHĐT là cách ti p c n bài toán tr nên g n gũi v i th cở ươ ế ậ ở ầ ớ ự
t h n. Đ hi u rõ h n v ph ng pháp l p trình này, không gì t t h n làế ơ ể ể ơ ề ươ ậ ố ơ
- 5 -
Ch¬ng 1: LËp t×nh híng ®èi tîng - Ph¬ng ph¸p gi¶i quyÕt bµi
to¸n míi
chúng ta đi vào m t bài toán c th , ch ng h n bài toán quan h gia đình. ộ ụ ể ẳ ạ ệ ở
đây yêu c u làm th nào đ th hi n đ c các m i quan h gi a các thànhầ ế ể ể ệ ượ ố ệ ữ
viên trong m t gia đình trên máy tính và có th tr l i đ c câu h i d ng kháộ ể ả ờ ượ ỏ ạ
t ng quát: “A và B có quan h nh th nào trong gia đình ?” v i A và B là haiổ ệ ư ế ớ
cá th b t kỳ. Chúng ta s phân tích xem cách gi i quy t bài toán này nh thể ấ ẽ ả ế ư ế
nào.
2. Bài toán quan h gia đìnhệ
Trong xã h i, m i ng i đ u có m t gia đình, trong đó t n t i nhi u m iộ ỗ ườ ề ộ ồ ạ ề ố
quan h gia đình khá ph c t p nh ông, bà, cha, m , cô, chú, bác, v.v. Thôngệ ứ ạ ư ẹ
th ng, đ th hi n các m i quan h này ng i ta bi u di n b ng m t s đườ ể ể ệ ố ệ ườ ể ễ ằ ộ ơ ồ
cây quan h . D i đây là m t ví d bi u di n m t gia đình ba th h b ngệ ướ ộ ụ ể ễ ộ ế ệ ằ
hình 1.1.
Đ gi i quy t bài toán này theo ph ng pháp LTCT, công vi c đ u tiên làể ả ế ươ ệ ầ
ph i xây d ng m t c u trúc d li u th hi n đ c cây quan h trên. Trôngả ự ộ ấ ữ ệ ể ệ ượ ệ
qua có v là đ n gi n nh ng n u th làm xem s th y không đ n gi n chútẻ ơ ả ư ế ử ẽ ấ ơ ả
nào, th m chí còn khó. B i vì nó đòi h i ng i l p trình ph i r t thành th oậ ở ỏ ườ ậ ả ấ ạ
s d ng con tr , ph i xây d ng đ c gi i thu t c p nh t thông tin trên câyử ụ ỏ ả ự ượ ả ậ ậ ậ
quan h . Các gi i thu t này t ng đ i ph c t p đ i v i m t c u trúc d li uệ ả ậ ươ ố ứ ạ ố ớ ộ ấ ữ ệ
nh trong bài toán. Yêu c u c a bài toán là tr l i đ c câu h i d ng như ầ ủ ả ờ ượ ỏ ạ ư
“H ng và Mai có quan h nh th nào ?”. Câu tr l i c a ch ng trình ph iư ệ ư ế ả ờ ủ ươ ả
là “H ng là anh h c a Mai”. Đ có th th c hi n đ c nh v y, rõ ràngư ọ ủ ể ể ự ệ ượ ư ậ
chúng ta ph i xây d ng đ c gi i thu t tìm đ c m i quan h gi a hai nútả ự ượ ả ậ ượ ố ệ ữ
trên cây quan h . M t v n đ ph c t p và t nh h n là tên g i cho các m iệ ộ ấ ề ứ ạ ế ị ơ ọ ố
quan h gia đình Vi t nam r t phong phú! M t khó khăn là ph i vét c n h tệ ở ệ ấ ộ ả ạ ế
các m i quan h có th có trên m t cây quan h . M t khó khăn n a g p ph iố ệ ể ộ ệ ộ ữ ặ ả
- 6 -
Mr. Th ngắMs. Nga
Mr. Quang
Mr. H ngư
Ms. Vân
Miss. MaiMiss. Trang
Mr. Tu nấMs. H ngằ
Hình 1.1 Cây quan h trong m tệ ộ
gia đình
Ch¬ng 1: LËp t×nh híng ®èi tîng - Ph¬ng ph¸p gi¶i quyÕt bµi
to¸n míi
là khi c n phát tri n, ch ng trình ph i qu n lý đ c nhi u gia đình cùng m tầ ể ươ ả ả ượ ề ộ
lúc và các gia đình này có m i quan h thông gia v i nhau. Hình 1.2 là s đố ệ ớ ơ ồ
quan h đ c phát tri n t s đ ví d trên minh ho cho v n đ này.ệ ượ ể ừ ơ ồ ụ ạ ấ ề
M t câu h i đ t ra: “Li u v i c u trúc d li u cũ có đ m b o gi i quy tộ ỏ ặ ệ ớ ấ ữ ệ ả ả ả ế
đ c v n đ này không ?”. Rõ ràng câu tr l i là không. S đ quan h trênượ ấ ề ả ờ ơ ồ ệ
hình v s ph i mô t quan h c a m t gia đình. Ch v i chút ít s thay đ iẽ ẽ ả ả ệ ủ ộ ỉ ớ ự ổ
v c u trúc d li u cũng d n đ n m t lo t v n đ đòi h i ph i vi t l i cácề ấ ữ ệ ẫ ế ộ ạ ấ ề ỏ ả ế ạ
gi i thu t c a ch ng trình. Ph ng pháp l p trình m i h ng đ i t ng choả ậ ủ ươ ươ ậ ớ ướ ố ượ
phép chúng ta kh c ph c đ c các v n đ đã nêu ra. Trong su t các trình bàyắ ụ ượ ấ ề ố
c a cu n sách này s c g ng nêu b t đ c cách gi i quy t v n đ nhủ ố ẽ ố ắ ậ ượ ả ế ấ ề ờ
LTHĐT.
Theo cách ti p c n LTHĐT, bài toán quan h gia đình đ c xem xét d iế ậ ệ ượ ướ
góc đ qu n lý t p các đ i t ng ộ ả ậ ố ượ Con ng iườ . Đ bi t m i quan h gia đìnhể ế ố ệ
c a m i cá th , c n th hi n m t s quan h c b n nh cha, m , anh em,ủ ỗ ể ầ ể ệ ộ ố ệ ơ ả ư ẹ
con cái, v ch ng c a cá th đó. Nh v y, m i đ i t ng con ng i c a bàiợ ồ ủ ể ư ậ ỗ ố ượ ườ ủ
toán có các thu c tính riêng, nói lên r ng cha m , anh em, v.v.. c a h là ai.ộ ằ ẹ ủ ọ
Ngoài ra cũng c n có m t thu c tính n a cho bi t tên cá th là gì. Có th môầ ộ ộ ữ ế ể ể
t m t l p các đ i t ng con ng i nh hình 1.3.ả ộ ớ ố ượ ườ ư
- 7 -
Con ng iườ
Tên ?
Cha ?
M ?ẹ
Anh em ?
Con cái ?
V / Ch ng ?ợ ồ
Hình 1.3 Mô t m t l p các đ i t ng ả ộ ớ ố ượ
con ng iườ
Mr. Th ngắMs. Nga
Mr. Quang
Mr. H ngư
Ms. Vân
Miss. Mai
Miss.
Trang
Mr. Tu nấMs. H ngằ
Mr. Thành Ms. Lan
- - -
- -
- - -
- -
- - -
- -
- -
-
Hình 1.2 M r ng quan h gi a ở ộ ệ ữ
các gia đình
Ch¬ng 1: LËp t×nh híng ®èi tîng - Ph¬ng ph¸p gi¶i quyÕt bµi
to¸n míi
N u ch có nh v y thì ch ng khác gì m t c u trúc hay b n ghi trong c uế ỉ ư ậ ẳ ộ ấ ả ấ
trúc d di u đ c s d ng ph ng pháp LTCT. V n đ đây là ph ngữ ệ ượ ử ụ ở ươ ấ ề ở ươ
pháp LTHĐT xem các m i quan h trong gia đình đ c hình thành m t cáchố ệ ượ ộ
t nhiên do các s ki n c th trong cu c s ng t o nên. Ví d , khi ng i phự ự ệ ụ ể ộ ố ạ ụ ườ ụ
n sinh con, đ a con cô ta sinh ra s có m là cô ta và cha là ch ng cô ta, đ ngữ ứ ẽ ẹ ồ ồ
th i anh ch ng ph i đ c c p nh t đ có thêm đ a con này. Nh ng đ a conờ ồ ả ượ ậ ậ ể ứ ữ ứ
tr c c a cô ta s có thêm đ a em này và đ a bé có thêm nh ng ng i anhướ ủ ẽ ứ ứ ữ ườ
ho c ng i ch đó. D dàng th y r ng có hai s ki n chính tác đ ng đ n m iặ ườ ị ễ ấ ằ ự ệ ộ ế ố
quan h gia đình là s sinh con c a ng i ph n và hôn nhân gi a hai cá thệ ự ủ ườ ụ ữ ữ ể
khác gi i trong xã h i. Các s ki n này g n li n v i t ng con ng i trong bàiớ ộ ự ệ ắ ề ớ ừ ườ
toán. Đi u này có nghĩa là khi nói đ n m t s ki n nào thì ph i ch ra nó đ cề ế ộ ự ệ ả ỉ ượ
phát sinh b i ng i nào. Ví d , khi nói s ki n sinh con thì ph i bi t ng iở ườ ụ ự ệ ả ế ườ
nào sinh. Khi m t s ki n c a m t con ng i nào đó x y ra (ví d nh sinhộ ự ệ ủ ộ ườ ả ụ ư
con) thì các thu c tính c a chính anh ta s b thay đ i, đ ng th i thu c tínhộ ủ ẽ ị ổ ồ ờ ộ
c a m t s đ i t ng liên quan cũng có th thay đ i theo. Quá trình đóng góiủ ộ ố ố ượ ể ổ
gi a các s ki n và thu c tính s t o ra ữ ự ệ ộ ẽ ạ Đ i t ng,ố ượ khái ni m c b n c aệ ơ ả ủ
ph ng pháp LTHĐT. M t mô t chung cho các đ i t ng con ng i c a bàiươ ộ ả ố ượ ườ ủ
toán đ c g i là m t ượ ọ ộ L pớ. Hình 1.4 minh ho m t l p Con ng i có thêm cácạ ộ ớ ườ
s ki n c a bài toán.ự ệ ủ
Sau khi đã g n k t các s ki n vào đ i t ng nh trên, v n đ là t o m tắ ế ự ệ ố ượ ư ấ ề ạ ộ
s đ quan h gia đình nh th nào. D i đây là m t ví d minh ho vi c t oơ ồ ệ ư ế ướ ộ ụ ạ ệ ạ
ra m t quan h gia đình d a trên các s ki n cu c s ng. Gi thi t là đã có haiộ ệ ự ự ệ ộ ố ả ế
đ i t ng là ông Th ng và bà Mai.ố ượ ắ
- 8 -
Con ng iườ
Tên ?
Cha ?
M ?ẹ
Anh em ?
Con cái ?
V / Ch ng ?ợ ồ
Sinh con
C iướ
Hình 1.4 Các s ki n b sung g n v i ự ệ ổ ắ ớ
con ng i.ườ
Ch¬ng 1: LËp t×nh híng ®èi tîng - Ph¬ng ph¸p gi¶i quyÕt bµi
to¸n míi
Các s ki n đ t o ra cây quan h trên có th vi t theo tr t t nh sau:ự ệ ể ạ ệ ể ế ậ ự ư
Th ng.C i (Mai)ắ ướ
Mai.Sinh con (gái, Nga)
Mai.Sinh con (trai,Tu n)ấ
Các s ki n vi t theo cú pháp: ự ệ ế
Nh v y các b n đã th y r ng chúng ta không c n ph i quan tâm đ nư ậ ạ ấ ằ ầ ả ế
cách t o m t c u trúc cây quan h nh th nào bên trong d li u c a ch ngạ ộ ấ ệ ư ế ữ ệ ủ ươ
trình mà v n có th cung c p d li u bài toán cho ch ng trình thông qua cácẫ ể ấ ữ ệ ươ
s ki n nh trên. Chúng ta quay l i v n đ chính c a bài toán là tr l i cácự ệ ư ạ ấ ề ủ ả ờ
câu h i v m i quan h gia đình nh th nào khi ti p c n bài toán theoỏ ề ố ệ ư ế ế ậ
ph ng pháp này. Đ tr l i đ c câu h i t ng quát “X và Y có quan h giaươ ể ả ờ ượ ỏ ổ ệ
đình nh th nào ?” ta c n ph i tr l i các câu h i nh nh “X có ph i là anhư ế ầ ả ả ờ ỏ ỏ ư ả
c a Y không ?”, “X có ph i là ông n i c a Y không ?”, v.v.. Câu h i có thủ ả ộ ủ ỏ ể
nhìn t góc đ đ i t ng X nh : “Đ i t ng có ph i là anh c a Y không ?”,ừ ộ ố ượ ư ố ượ ả ủ
“có ph i là ông n i c a Y không ?”, v.v.. Nh v y câu h i lúc này đã giao vả ộ ủ ư ậ ỏ ề
cho đ i t ng đ tr l i. Các đ i t ng lúc này c n ph i có các ph ng th cố ượ ể ả ờ ố ượ ầ ả ươ ứ
đ tr l i các câu h i nh v y. Và bây gi m t l p đ i t ng Con ng iể ả ờ ỏ ư ậ ờ ộ ớ ố ượ ườ
đ c minh ho nh hình 1.5.ượ ạ ư
- 9 -
Ms. MaiMr. Th ngắ
Mr. Tu nấMiss. Nga
Đ i t ng t o s ki n . S ki n ( thông s kèmố ượ ạ ự ệ ự ệ ố
ự ệ